Bilangan swafoto palindrom

Sesuatu nombor dianggap sebagai "nombor swafoto" jika ia boleh diwakili hanya menggunakan digitnya sendiri dan beberapa operasi matematik.

Sebagai contoh, 936 ialah nombor selfie.

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

Anda boleh lihat di sini bahawa satu siri operasi dilakukan pada nombor asal, dan hasilnya adalah sama dengan nombor asal.

Nombor selfie palindrom ialah nombor selfie khas. Mereka memenuhi peraturan pendaraban swafoto.

• Pertimbangkan nombor x.

• Andaikan nombor x terbalik secara berangka ialah $mathrm{x^prime}$.

• Biarkan y ialah nombor yang terdiri daripada digit x dalam susunan yang berbeza.

• Katakan nombor terbalik bagi y ialah $mathrm{y^prime}$.

Bilangan swafoto palindromik memenuhi persamaan berikut -

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

Pernyataan Masalah

Untuk nombor x yang diberikan, cari nombor selfie palindromnya mengikut peraturan pendaraban swafoto.

Contoh

Input: 1224
Output: 2142

Arahan -

Diberi x = 1224

Jadi $mathrm{x^prime}$ = 4221 diperoleh dengan membalikkan nombor x

Misalkan y = 2142. y dibentuk menggunakan nombor x dalam susunan berbeza

Jadi $mathrm{y^prime}$ = 2412 diperoleh dengan membalikkan nombor y

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

Sejakx× x' = y × y', y ialah bilangan swafoto palindrom bagi x.

Input 4669:
Output: 6496

Arahan -

Diberi x = 4669

Jadi $mathrm{x^prime}$ = 9664 diperoleh dengan membalikkan nombor x

Misalkan y = 6496. y dibentuk menggunakan nombor x dalam susunan berbeza

Jadi $mathrm{y^prime}$ = 6946 diperoleh dengan membalikkan nombor y

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

Memandangkan x× x' = y × y', y ialah nombor selfie palindrom bagi x.

Input: 456
Output: No palindromic selfie number exists

Arahan -

Diberi x = 456

Jadi $mathrm{x^prime}$ = 654 diperoleh dengan membalikkan nombor x

Misalkan y = 546. y dibentuk menggunakan nombor x dalam susunan berbeza

Jadi $mathrm{y^prime}$ = 645 diperoleh dengan membalikkan nombor y

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

Memandangkan $mathrm{x:×:x^prime}$ ≠ $mathrm{y:×:y^prime}$, y bukanlah nombor selfie palindromik bagi x.

Tiada pilih atur lain 456 juga memenuhi peraturan pendaraban swafoto.

Penyelesaian

Penyelesaian untuk mencari nombor selfie palindrom bagi nombor tertentu adalah agak intuitif dan mudah difahami.

Kaedahnya merangkumi langkah-langkah berikut -

• Tentukan fungsi "terbalik"

• Menerima integer sebagai input

• Tukarkannya kepada rentetan

• Rentetan terbalik

• Tukarkannya semula kepada integer.

• Tentukan fungsi "Tukar"

• Ambil integer i dan j sebagai input

• Tukar integer kepada rentetan

• Tukar aksara ke-i dan ke-j dalam rentetan

• Tukar rentetan kembali kepada integer.

• Tentukan fungsi "permutasi"

• Mengambil sebagai input integer, l, r dan satu set "permutasi".

• Ia secara rekursif menjana semua pilih atur yang mungkin bagi nombor integer

• Ia menyimpannya dalam set "permutasi".

• Tentukan fungsi "palindromic_selfie"

• Mengambil sebagai input integer "num" dan set "permutasi".

• Ia menggunakan fungsi "permute" untuk menjana semua pilih atur yang mungkin bagi "num" integer

• Ia kemudian menyemak sama ada mana-mana pilih atur ini memenuhi sifat swafoto palindromik dengan membandingkan hasil darab nombor dan tertib terbaliknya dengan hasil pilih atur dan tertib terbaliknya.

• Jika pilih atur sedemikian ditemui, kembalikan nombor itu. Jika tidak, -1 dikembalikan.

• Dalam fungsi utama, tetapkan nombor "n" dan set kosong untuk menyimpan pilih atur.

• Panggil fungsi "palindromic_selfie" dengan "n" dan set kosong, dan simpan hasil pemulangan.

• Jika hasil pulangan ialah -1, cetak "Tiada nombor selfie palindrom". Jika tidak, cetak hasil yang dikembalikan.

Contoh: program C++

Program C++ berikut mencari nombor selfie palindrom bagi integer tertentu (jika wujud) dan mengembalikannya. Ia melakukan ini dengan menggunakan fungsi pilih atur() untuk mencari semua pilih atur yang mungkin bagi nombor tertentu, dan kemudian menggunakan fungsi reverse() untuk menentukan sama ada nombor yang diberikan dan sebarang pilih atur nombor itu memenuhi peraturan pendaraban swafoto dalam palindrome_selfie() fungsi. Jika tiada nombor sedemikian wujud, "Tiada Nombor Selfie Palindrome Wujud" dicetak.

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

结论

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

Atas ialah kandungan terperinci Bilangan swafoto palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!