如果一個數字可以只使用自己的數字和某些數學運算來表示,則該數字被視為「自拍數字」。
例如,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 p>
Sincex× 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 p>
由於 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 p>
由於 $\mathrm{x\:×\:x^\prime}$ ≠ $\mathrm{y\:×\:y^\prime}$,因此 y 不是 x 的回文自拍照數。 p>
沒有其他 456 的排列也符合自拍乘法規則。
找到給定數字的回文自拍照數字的解決方法相當直觀且易於理解。
該方法包括以下步驟 -
定義一個「反向」函數
接受一個整數作為輸入
將其轉換為字串
#反轉字串
#將其轉換回整數。
定義一個函數「Swap」
採用整數 i 和 j 作為輸入
將整數轉換為字串
交換字串中的第 i 個和第 j 個字元
#將字串轉換回整數。
定義一個函數「置換」
採用整數、l、r 和一組「排列」作為輸入。
它遞歸地產生整數數字的所有可能排列
#它將它們儲存在「排列」集中。
定義一個函數「palindromic_selfie」
#採用整數「num」和一組「permutations」作為輸入。
它使用「permute」函數產生整數「num」的所有可能的排列
#然後,它透過將數字及其逆序的乘積與排列及其逆序的乘積進行比較,檢查這些排列中的任何一個是否滿足回文自拍屬性。
如果找到這樣的排列,則傳回該數字。否則,返回-1。
在主函數中,設定一個數字「n」和一個用於儲存排列的空集合。
使用「n」和空集合呼叫「palindromic_selfie」函數,並儲存回傳結果。
如果傳回結果為-1,則列印「不存在回文自拍數」。否則,列印返回結果。
以下 C 程式尋找給定整數的回文自拍編號(如果存在)並傳回它。它透過使用 permute() 函數找到給定數字的所有可能的排列,然後使用 reverse() 函數確定給定數字和該數字的任何排列是否滿足 palindrome_selfie() 函數中的自拍乘法規則來實現此目的。如果不存在這樣的數字,則會列印「No Palindrome Selfie Number Exists」。
#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!),其中 n 是输入数字的位数。这是因为有 n! n 位数字的排列,并且 permute() 方法生成数字的所有潜在排列。
由于集合“排列”包含所有可能的数字组合,等于 n!,因此该代码的空间复杂度为 O(n!)。 verse() 和 Swap() 函数的空间复杂度为 O(n),因为它们还生成长度为 n 的临时字符串。空间复杂度为 O(n!) 的排列集合主导了整个代码的空间复杂度。
回文自拍數是数学中一个有趣的概念。它们满足自拍乘法方程。本文讨论了一种方法来查找一个数字是否具有回文自拍号码,如果是,则返回它。对问题的概念、解决方法、C++程序以及程序的时间和空间复杂度进行了深入分析。
以上是回文自拍數的詳細內容。更多資訊請關注PHP中文網其他相關文章!