Anzahl der Palindrom-Selfies-C++-php.cn

Anzahl der Palindrom-Selfies

Eine Zahl gilt als „Selfie-Zahl“, wenn sie nur mit ihren eigenen Ziffern und einigen mathematischen Operationen dargestellt werden kann.

Zum Beispiel ist 936 eine Selfie-Nummer.

$$mathrm{936:=:(sqrt{9})!^{3}:+:6!:=:216:+:720:=:Kapitel 936

Hier können Sie sehen, dass eine Reihe von Operationen an der ursprünglichen Zahl ausgeführt werden und das Ergebnis der ursprünglichen Zahl entspricht.

Eine Palindrom-Selfie-Nummer ist eine besondere Selfie-Nummer. Sie erfüllen die Selfie-Multiplikationsregel.

Betrachten Sie eine Zahl x.
Angenommen, die numerisch umgekehrte Zahl von x ist $mathrm{x^prime}$.
Sei y eine Zahl, die aus den Ziffern von x in unterschiedlicher Reihenfolge besteht.
Angenommen, die invertierte Zahl von y ist $mathrm{y^prime}$.

Die Anzahl der palindromischen Selfies erfüllt die folgende Gleichung –

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

Problemstellung

Ermitteln Sie für eine gegebene Zahl x ihre Palindrom-Selfie-Zahl gemäß der Selfie-Multiplikationsregel.

Beispiel

Input: 1224
Output: 2142

Nach dem Login kopieren

Anleitung -

Gegebenes x = 1224

Also erhält man $mathrm{x^prime}$ = 4221 durch Umkehren der Anzahl von x

Sei y = 2142. y wird aus den Zahlen von x in unterschiedlicher Reihenfolge gebildet

Also erhält man $mathrm{y^prime}$ = 2412 durch Umkehren der Zahl von y

$mathrm{x:×:x^prime}$ = 1224 × 4221 = 5166504 und $mathrm{y:×:y^prime}$ = 2142 × 2412 = 5166504

Sincex× x' = y × y', y ist die Anzahl der Palindrom-Selfies von x.

Input 4669:
Output: 6496

Nach dem Login kopieren

Anleitung -

Gegebenes x = 4669

Also erhält man $mathrm{x^prime}$ = 9664 durch Umkehren der Anzahl von x

Sei y = 6496. y wird aus den Zahlen von x in unterschiedlicher Reihenfolge gebildet

Also erhält man $mathrm{y^prime}$ = 6946 durch Umkehren der Zahl von y

$mathrm{x:×:x^prime}$ = 4669 × 9664 = 45121216 und $mathrm{y:×:y^prime}$ = 6496× 6946= 45121216

Da x× x' = y × y' ist, ist y die Palindrom-Selfie-Zahl von x.

Input: 456
Output: No palindromic selfie number exists

Nach dem Login kopieren

Anleitung -

Gegebenes x = 456

Also erhält man $mathrm{x^prime}$ = 654 durch Umkehren der Anzahl von x

Sei y = 546. y wird aus den Zahlen von x in unterschiedlicher Reihenfolge gebildet

Also erhält man $mathrm{y^prime}$ = 645 durch Umkehren der Zahl von y

$mathrm{x:×:x^prime}$ = 456 × 654 = 298224 und $mathrm{y:×:y^prime}$ = 546× 645= 352170

Da $mathrm{x:×:x^prime}$ ≠ $mathrm{y:×:y^prime}$ ist, ist y nicht die palindromische Selfie-Zahl von x.

Keine andere Permutation von 456 erfüllt auch die Selfie-Multiplikationsregel.

Lösung

Die Lösung zum Ermitteln der Palindrom-Selfie-Nummer einer bestimmten Nummer ist recht intuitiv und leicht zu verstehen.

Die Methode umfasst die folgenden Schritte –

Definieren Sie eine „Umkehr“-Funktion

Akzeptiert eine Ganzzahl als Eingabe
Konvertieren Sie es in einen String
Umgekehrte Zeichenfolge
Konvertieren Sie es zurück in eine Ganzzahl.

Definieren Sie eine Funktion „Swap“

Nehmen Sie die ganzen Zahlen i und j als Eingabe
Integer in String umwandeln
Vertauschen Sie die i-ten und j-ten Zeichen in der Zeichenfolge
Konvertieren Sie die Zeichenfolge zurück in eine Ganzzahl.

Definieren Sie eine Funktion „Permutation“

Nimmt als Eingabe eine Ganzzahl, l, r und eine Reihe von „Permutationen“.
Es generiert rekursiv alle möglichen Permutationen ganzer Zahlen
Es speichert sie im Satz „Permutationen“.

Definieren Sie eine Funktion „palindromic_selfie“

Nimmt als Eingabe eine ganze Zahl „num“ und eine Reihe von „Permutationen“.
Es verwendet die Funktion „permute“, um alle möglichen Permutationen der ganzen Zahl „num“ zu generieren
Es prüft dann, ob eine dieser Permutationen die palindromische Selfie-Eigenschaft erfüllt, indem es das Produkt aus der Zahl und ihrer umgekehrten Reihenfolge mit dem Produkt der Permutation und ihrer umgekehrten Reihenfolge vergleicht.
Wenn eine solche Permutation gefunden wird, geben Sie diese Zahl zurück. Andernfalls wird -1 zurückgegeben.

Legen Sie in der Hauptfunktion eine Zahl „n“ und eine leere Menge fest, um die Permutation zu speichern.
Rufen Sie die Funktion „palindromic_selfie“ mit „n“ und der leeren Menge auf und speichern Sie das Rückgabeergebnis.
Wenn das Rückgabeergebnis -1 ist, geben Sie „Es gibt keine Palindrom-Selfie-Nummer“ aus. Andernfalls drucken Sie das zurückgegebene Ergebnis aus.

Beispiel: C++-Programm

Das folgende C++-Programm findet die Palindrom-Selfie-Nummer einer bestimmten Ganzzahl (falls vorhanden) und gibt sie zurück. Dazu verwendet es die Funktion permute(), um alle möglichen Permutationen einer bestimmten Zahl zu finden, und verwendet dann die Funktion reverse(), um zu bestimmen, ob die angegebene Zahl und etwaige Permutationen dieser Zahl den Selfie-Multiplikationsregeln im palindrome_selfie() genügen. Funktion. Wenn keine solche Nummer vorhanden ist, wird „No Palindrome Selfie Number Exists“ gedruckt.

#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;
}

Nach dem Login kopieren

输出

n: 1234
No Palindromic Selfie Number Exists

Nach dem Login kopieren

时间和空间复杂度分析

时间复杂度：O(n!)

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

空间复杂度：O(n!)

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

结论

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

Das obige ist der detaillierte Inhalt vonAnzahl der Palindrom-Selfies. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!