迴文自拍數

---

如果一個數字可以使用它自身的數字和某些數學運算來表示，則認為該數字是“自拍數”。

例如，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，根據自拍乘法規則找到其迴文自拍數。

示例

Input: 1224
Output: 2142

說明 -

給定 x = 1224

所以 $\mathrm{x^\prime}$ = 4221 是透過反轉 x 的數字形成的

令 y = 2142。y 是使用 x 的數字以不同順序形成的

所以 $\mathrm{y^\prime}$ = 2412 是透過反轉 y 的數字形成的

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

由於 x× x' = y × y'，所以 y 是 x 的迴文自拍數。

Input 4669:
Output: 6496

說明 -

給定 x = 4669

所以 $\mathrm{x^\prime}$ = 9664 是透過反轉 x 的數字形成的

令 y = 6496。y 是使用 x 的數字以不同順序形成的

所以 $\mathrm{y^\prime}$ = 6946 是透過反轉 y 的數字形成的

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

由於 x× x' = y × y'，所以 y 是 x 的迴文自拍數。

Input: 456
Output: No palindromic selfie number exists

說明 -

給定 x = 456

所以 $\mathrm{x^\prime}$ = 654 是透過反轉 x 的數字形成的

令 y = 546。y 是使用 x 的數字以不同順序形成的

所以 $\mathrm{y^\prime}$ = 645 是透過反轉 y 的數字形成的

$\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 的其他排列也不滿足自拍乘法規則。

解決方案方法

找到給定數字的迴文自拍數的解決方案方法非常直觀且易於理解。

該方法包括以下步驟 -

• 定義一個函式“reverse”，該函式

• 以整數作為輸入

• 將其轉換為字串

• 反轉字串

• 將其轉換回整數。

• 定義一個函式“Swap”，該函式

• 以整數 i 和 j 作為輸入

• 將整數轉換為字串

• 交換字串中第 i 個和第 j 個字元

• 將字串轉換回整數。

• 定義一個函式“permute”，該函式

• 以整數 l、r 和集合“permutations”作為輸入。

• 它遞迴地生成整數的所有可能的數字排列

• 它將它們儲存在集合“permutations”中。

• 定義一個函式“palindromic_selfie”，該函式

• 以整數“num”和集合“permutations”作為輸入。

• 它使用“permute”函式生成整數“num”的所有可能的數字排列

• 然後，它透過將數字及其反轉的乘積與排列及其反轉的乘積進行比較，檢查這些排列中是否有任何一個滿足迴文自拍屬性。

• 如果找到這樣的排列，則返回該數字。否則，返回 -1。

• 在主函式中，設定一個數字“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!)

由於集合“permutations”包含數字的所有可能組合，等於 n!，因此此程式碼的空間複雜度為 O(n!)。reverse() 和 Swap() 函式的空間複雜度為 O(n)，因為它們也會生成長度為 n 的臨時字串。包含 O(n!) 空間複雜度的排列集合主導了整個程式碼的空間複雜度。

結論

迴文自拍數是數學中一個有趣的概念。它們滿足自拍乘法方程。本文討論了一種方法來查詢一個數字是否具有迴文自拍數，如果存在，則返回它。對問題的概念、解決方案方法、C++ 程式以及程式的時間和空間複雜度進行了徹底的分析。