Nième numéro de palindrome parmi K chiffres en C++

Pour trouver le nième numéro de palindrome avec k chiffres, nous pouvons parcourir à partir du premier numéro de k chiffres jusqu'à ce que nous trouvions le nième numéro de palindrome. Cette méthode n'est pas efficace. Vous pouvez l'essayer vous-même.

Voyons maintenant la manière efficace de trouver le nième nombre palindrome de k chiffres.

Il y a deux moitiés dans un nombre. La première moitié est égale au renversement de la seconde moitié.

La première moitié du nième nombre à k chiffres est

Si k est un nombre impair, c'est (n-1)+10^k/2, sinon c'est (n-1)+10^{k/ 2- 1}

La seconde moitié du nième nombre à k chiffres sera l'inversion de la première moitié du nombre. Si k est un nombre impair, supprimez le dernier chiffre de la première moitié du nombre.

Algorithme

• Initialisez les nombres n et k.
• Trouvez la longueur de la première moitié du palindrome à k chiffres en utilisant la valeur de k.
• La première moitié du nombre palindrome est pow(10, longueur) + n - 1.
• Si k est un nombre impair, supprimez le dernier chiffre de la première moitié du numéro palindrome.
• Inversez la première moitié et imprimez la seconde moitié.

Implémentation

Ce qui suit est l'implémentation de l'algorithme ci-dessus en C++

#include<bits/stdc++.h>
using namespace std;
void findNthPalindrome(int n, int k) {
   int temp = (k & 1) ? (k / 2) : (k / 2 - 1);
   int palindrome = (int)pow(10, temp);
   palindrome += n - 1;
   cout << palindrome;
   if (k & 1) {
      palindrome /= 10;
   }
   while (palindrome) {
      cout << palindrome % 10;
      palindrome /= 10;
   }
      cout << endl;
}
int main(){
   int n = 7, k = 8;
   findNthPalindrome(n ,k);
   return 0;
}

Output

Si vous exécutez le code ci-dessus, vous obtiendrez les résultats suivants.

10066001

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!