Nombre de selfies palindromes

Un nombre est considéré comme un « numéro de selfie » s'il peut être représenté en utilisant uniquement ses propres chiffres et quelques opérations mathématiques.

Par exemple, 936 est un numéro de selfie.

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

Vous pouvez voir ici qu'une série d'opérations sont effectuées sur le numéro d'origine et que le résultat est égal au numéro d'origine.

Un numéro de selfie palindrome est un numéro de selfie spécial. Ils satisfont à la règle de multiplication du selfie.

• Considérez un nombre x.

• Supposons que le nombre numériquement inversé de x soit $mathrm{x^prime}$.

• Soit y un nombre composé des chiffres de x dans des ordres différents.

• Supposons que le nombre inversé de y soit $mathrm{y^prime}$.

Le nombre de selfies palindromiques satisfait l'équation suivante -

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

Énoncé du problème

Pour un nombre x donné, trouvez son numéro de selfie palindrome selon la règle de multiplication du selfie.

Exemple

Input: 1224
Output: 2142

Instructions -

Étant donné x = 1224

Donc $mathrm{x^prime}$ = 4221 est obtenu en inversant le nombre de x

Soit y = 2142. y est formé en utilisant les nombres de x dans un ordre différent

Donc $mathrm{y^prime}$ = 2412 est obtenu en inversant le nombre de y

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

Puisquex× x' = y × y', y est le nombre de selfies palindromes de x.

Input 4669:
Output: 6496

Instructions -

Étant donné x = 4669

Donc $mathrm{x^prime}$ = 9664 est obtenu en inversant le nombre de x

Soit y = 6496. y est formé en utilisant les nombres de x dans un ordre différent

Donc $mathrm{y^prime}$ = 6946 est obtenu en inversant le nombre de y

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

Puisque x× x' = y × y', y est le numéro de selfie palindrome de x.

Input: 456
Output: No palindromic selfie number exists

Instructions -

Étant donné x = 456

Donc $mathrm{x^prime}$ = 654 est obtenu en inversant le nombre de x

Soit y = 546. y est formé en utilisant les nombres de x dans un ordre différent

Donc $mathrm{y^prime}$ = 645 est obtenu en inversant le nombre de y

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

Puisque $mathrm{x:×:x^prime}$ ≠ $mathrm{y:×:y^prime}$, y n'est pas le nombre palindromique de selfie de x. p>

Aucune autre permutation de 456 ne satisfait également à la règle de multiplication du selfie.

Solution

La solution pour trouver le numéro de selfie palindrome d'un numéro donné est assez intuitive et facile à comprendre.

La méthode comprend les étapes suivantes -

• Définir une fonction "inverse"

• Accepte un entier en entrée

• Convertissez-le en chaîne

• Chaîne inversée

• Convertissez-le en un entier.

• Définir une fonction "Swap"

• Prendre les entiers i et j comme entrée

• Convertir un entier en chaîne

• Échangez les i-ème et j-ème caractères dans la chaîne

• Convertissez la chaîne en entier.

• Définir une fonction "permutation"

• Prend en entrée un entier, l, r et un ensemble de "permutations".

• Il génère récursivement toutes les permutations possibles de nombres entiers

• Il les stocke dans l'ensemble "permutations".

• Définir une fonction "palindromic_selfie"

• Prend en entrée un entier "num" et un ensemble de "permutations".

• Il utilise la fonction "permute" pour générer toutes les permutations possibles de l'entier "num"

• Il vérifie ensuite si l'une de ces permutations satisfait la propriété palindromique du selfie en comparant le produit du nombre et son ordre inverse avec le produit de la permutation et son ordre inverse.

• Si une telle permutation est trouvée, renvoyez ce numéro. Sinon, -1 est renvoyé.

• Dans la fonction principale, définissez un nombre "n" et un ensemble vide pour stocker la permutation.

• Appelez la fonction "palindromic_selfie" avec "n" et l'ensemble vide, et stockez le résultat renvoyé.

• Si le résultat de retour est -1, imprimez "Il n'y a pas de numéro de selfie palindrome". Sinon, imprimez le résultat renvoyé.

Exemple : programme C++

Le programme C++ suivant trouve le numéro de selfie palindrome d'un entier donné (s'il existe) et le renvoie. Pour ce faire, il utilise la fonction permute() pour trouver toutes les permutations possibles d'un nombre donné, puis en utilisant la fonction reverse() pour déterminer si le nombre donné et toutes les permutations de ce nombre satisfont aux règles de multiplication de selfie dans palindrome_selfie(). fonction. Si aucun numéro de ce type n’existe, « Aucun numéro de selfie Palindrome n’existe » est imprimé.

#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!) 的排列集合主导了整个代码的空间复杂度。

结论

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!