ホームページ >バックエンド開発 >C++ >回文セルフィーの数

回文セルフィーの数

WBOY
WBOY転載
2023-09-09 20:37:09616ブラウズ

回文セルフィーの数

数値は、その数字といくつかの数学的演算のみを使用して表現できる場合、「自撮り番号」とみなされます。

たとえば、936 は自撮り番号です。

$$\mathrm{936\:=\:(\sqrt{9})!^{3}\: \:6!\:=\:216\: \:720\:=\:いいえ。 936章

ここでは、元の数値に対して一連の操作が実行され、結果が元の数値と等しいことがわかります。

回文セルフィー番号は特別なセルフィー番号です。これらは自撮り乗算ルールを満たします。

  • 数値 x について考えてみましょう。

  • x の数値を反転した数が $\mathrm{x^\prime}$ であるとします。

  • y を、x の桁を異なる順序で組み合わせた数値とします。

  • y をデジタル反転した後の数値が $\mathrm{y^\prime}$ であるとします。

回文セルフィーの数は次の式を満たします -

$$\mathrm{x\:×\:x^\prime\:=\:y\:×\:y^\prime}$$

###問題文###

与えられた数値 x について、自撮り乗算ルールに従ってその回文自撮り番号を見つけます。

###例### リーリー

イラスト

-

与えられた x = 1224 $\mathrm{x^\prime}$ = 4221 は、x

の数を逆にすると得られます。

y = 2142 とします。 y は、x の数字を異なる順序で使用して形成されます

したがって、y の数を逆にすると、$\mathrm{y^\prime}$ = 2412 が得られます。

$\mathrm{x\:×\:x^\prime}$ = 1224 × 4221 = 5166504 および $\mathrm{y\:×\:y^\prime}$ = 2142 × 2412 = 5166504

Sincex× x' = y × y'、y は x の回文セルフィーの数です。

リーリー

イラスト p> -

与えられた x = 4669

$\mathrm{x^\prime}$ = 9664 は x の数を逆にすると得られます。

y = 6496 とします。 y は、x の数字を異なる順序で使用して形成されます

したがって、y の数を逆にすると、$\mathrm{y^\prime}$ = 6946 が得られます。

$\mathrm{x\:×\:x^\prime}$ = 4669 × 9664 = 45121216 および $\mathrm{y\:×\:y^\prime}$ = 6496× 6946= 45121216

x× x' = y × y' なので、y は x の回文自撮り番号になります。

リーリー

イラスト

- p>

与えられた x = 456

したがって、$\mathrm{x^\prime}$ = 654 は、x の数を逆にすることによって得られます。 y = 546 とします。 y は、x の数字を異なる順序で使用して形成されます

したがって、y の数を逆にすると、$\mathrm{y^\prime}$ = 645 が得られます。

$\mathrm{x\:×\:x^\prime}$ = 456 × 654 = 298224 および $\mathrm{y\:×\:y^\prime}$ = 546× 645= 352170

$\mathrm{x\:×\:x^\prime}$ ≠ $\mathrm{y\:×\:y^\prime}$ であるため、y は x の回文自撮り写真の数ではありません。

456 の他の順列も自撮り乗算ルールを満たすものはありません。

###解決###

指定された番号の回文自撮り番号を見つける解決策は非常に直感的で理解しやすいです。

p>この方法には次の手順が含まれます -

p>

「リバース」関数を定義する

整数を入力として受け入れます

  • 文字列に変換します

    • 逆文字列

    • これを整数に戻します。

    • 関数「Swap」を定義します

    • 整数 i と j を入力として受け取る
  • 整数を文字列に変換

    • 文字列の i 番目と j 番目の文字を交換します

    • 文字列を整数に変換します。

    • 関数「変位」を定義します

    • 整数 l、r、および「順列」のセットを入力として受け取ります。
  • これは、整数の可能なすべての順列を再帰的に生成します

    • それらは「順列」セットに保存されます。

    • 関数「palindromic_selfie」を定義します

    • 整数「num」と一連の「順列」を入力として受け取ります。
  • 「permute」関数を使用して、整数「num」の可能なすべての置換を生成します。

    • 次に、数値とその逆順の積を順列とその逆順の積と比較することで、これらの順列のいずれかが回文セルフィー特性を満たすかどうかをチェックします。

    • そのような順列が見つかった場合は、その数値が返されます。それ以外の場合は、-1 が返されます。

    • main 関数で、数値「n」と順列を格納する空のセットを設定します。

    • 「n」と空のセットを使用して「palindromic_selfie」関数を呼び出し、返された結果を保存します。

  • 戻り結果が -1 の場合は、「回文自撮り番号がありません」と出力します。それ以外の場合は、返された結果を出力します。

  • 例: C プログラム

    次の C プログラムは、指定された整数の回文自撮り番号 (存在する場合) を検索し、それを返します。これは、 permute() 関数を使用して指定された数値の考えられるすべての順列を検索し、次に reverse() 関数を使用して指定された数値とその数値の任意の順列が palindrome_selfie() の自撮り乗算ルールを満たすかどうかを判断することによって行われます。関数。そのような番号が存在しない場合は、「回文セルフィー番号が存在しません」と表示されます。
  • #include <bits/stdc++.h>
    using namespace std;
    
    // Function to reverse the digits of a number
    int reverse(int num){
       
       // converting number to string
       string str = to_string(num);
       reverse(str.begin(), str.end());
       
       // converting string to integer
       num = stoi(str);
       return num;
    }
    
    // Function that Swaps the digits i and j in the num
    int Swap(int num, int i, int j){
       char temp;
       
       // converting number to string
       string s = to_string(num);
       
       // Swap the ith and jth character
       temp = s[i];
       s[i] = s[j];
       s[j] = temp;
       
       // Convert the string back to int and return
       return stoi(s);
    }
    
    // Function to get all possible permutations of the digits in num
    void permute(int num, int l, int r, set<int> &permutations){
       
       // Adds the new permutation obtained in the set
       if (l == r)
          permutations.insert(num);
       else{
          for (int i = l; i <= r; i++){
             
             // Swap digits to get a different ordering
             int num_copy = Swap(num, l, i);
             
             // Recurse to next pair of digits
             permute(num_copy, l + 1, r, permutations);
          }
       }
    }
    
    // Function to check for palindrome selfie number
    int palindromic_selfie(int num, set<int>& permutations) {
       
       // Length of the number required for calculating all permutations of the digits
       int l = to_string(num).length() - 1;
       permute(num, 0, l, permutations); // Calculate all permutations
       
       //Remove the number and its reverse from the obtained set as this is the LHS of multiplicative equation
       auto n1 = permutations.find(reverse(num));
       auto n2 = permutations.find(num);
       if (n1 != permutations.end())
          permutations.erase(n1);
       if (n2 != permutations.end())
          permutations.erase(n2);
       
       // Go through all other permutations of the number
       for (set<int>::iterator it = permutations.begin(); it != permutations.end(); it++) {
          int num2 = *it;
          
          // Check if selfie multiplicative rule holds i.e. x * reverse(x) = y * reverse(y)
          if (num * reverse(num) == num2 * reverse(num2)) {
             return num2;
          }
       }
       
       // If no such number found
       return -1;
    }
    int main(){
       int n = 1234;
       cout << "n: " << n << endl;
       set<int> permutations;
       int ans = palindromic_selfie(n, permutations);
       if (ans == -1) {
          cout << "No Palindromic Selfie Number Exists" << endl;
       }
       else{
          cout << ans << endl;
       }
       return 0;
    }
    

    输出

    n: 1234
    No Palindromic Selfie Number Exists
    

    时间和空间复杂度分析

    时间复杂度:O(n!)

    此代码的时间复杂度为 O(n!),其中 n 是输入数字的位数。这是因为有 n! n 位数字的排列,并且 permute() 方法生成数字的所有潜在排列。

    空间复杂度:O(n!)

    由于集合“排列”包含所有可能的数字组合,等于 n!,因此该代码的空间复杂度为 O(n!)。 verse() 和 Swap() 函数的空间复杂度为 O(n),因为它们还生成长度为 n 的临时字符串。空间复杂度为 O(n!) 的排列集合主导了整个代码的空间复杂度。

    结论

    回文セルフィーの数是数学中一个有趣的概念。它们满足自拍乘法方程。本文讨论了一种方法来查找一个数字是否具有回文自拍号码,如果是,则返回它。对问题的概念、解决方法、C++程序以及程序的时间和空间复杂度进行了深入分析。

以上が回文セルフィーの数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はtutorialspoint.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。