회문 셀카 수-C++-php.cn

회문 셀카 수

WBOY

풀어 주다： 2023-09-09 20:37:09

앞으로

615명이 탐색했습니다.

회문 셀카 수

숫자 자체의 숫자와 일부 수학 연산을 사용하여 나타낼 수 있는 경우 "셀카 번호"로 간주됩니다.

예를 들어 936은 셀카 번호입니다.

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

원래 숫자에 대해 일련의 연산이 수행되고 결과가 원래 숫자와 동일하다는 것을 여기서 볼 수 있습니다.

회문 셀카 번호는 특별한 셀카 번호입니다. 셀카 곱셈 법칙을 만족합니다.

숫자 x를 생각해 보세요.
x의 역수 숫자가 $mathrm{x^prime}$이라고 가정합니다.
x의 숫자를 다른 순서로 조합한 숫자를 y라고 합니다.
y의 역수가 $mathrm{y^prime}$이라고 가정합니다.

회문형 셀카의 수는 다음 방정식을 만족합니다. -

$$mathrm{x:×:x^소수:=:y:×:y^소수}$$

문제 설명

주어진 숫자 x에 대해 셀카 곱셈 규칙에 따라 회문 셀카 번호를 찾습니다.

예

으아아아

지침 -

주어진 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의 회문 셀카 개수입니다.

으아아아

지침 -

주어진 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의 회문 셀카 번호입니다.

으아아아

지침 -

주어진 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의 다른 어떤 순열도 셀카 곱셈 규칙을 만족하지 않습니다.

솔루션

주어진 숫자의 회문 셀카 번호를 찾는 솔루션은 매우 직관적이고 이해하기 쉽습니다.

방법에는 다음 단계가 포함됩니다. -

"역방향" 기능 정의

정수를 입력으로 받아들입니다
문자열로 변환
역 문자열
다시 정수로 변환하세요.

"스왑" 기능 정의

정수 i와 j를 입력으로 사용
정수를 문자열로 변환
문자열에서 i번째 문자와 j번째 문자를 바꿉니다
문자열을 다시 정수로 변환합니다.

"순열" 함수 정의

정수, l, r 및 "순열" 집합을 입력으로 사용합니다.
정수의 가능한 모든 순열을 재귀적으로 생성합니다
"순열" 세트에 저장합니다.

"palindromic_selfie" 함수 정의

정수 "num"과 "순열" 집합을 입력으로 사용합니다.
"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!)

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

结论

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

위 내용은 회문 셀카 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!