N-te Palindromzahl unter K Ziffern in C++

Um die n-te Palindromzahl mit k Ziffern zu finden, können wir von der ersten k Ziffernzahl iterieren, bis wir die n-te Palindromzahl finden. Diese Methode ist nicht effizient. Sie können es selbst versuchen.

Lassen Sie uns nun den effizienten Weg sehen, die n-te Anzahl von k Ziffern des Palindroms zu ermitteln.

Eine Zahl besteht aus zwei Hälften. Die erste Hälfte entspricht der Umkehrung der zweiten Hälfte.

Die erste Hälfte der n-ten k-stelligen Zahl ist

Wenn k eine ungerade Zahl ist, ist sie (n-1)+10^k/2, andernfalls ist sie (n-1)+10^{k/ 2- 1}

Die zweite Hälfte der n-ten k-stelligen Zahl ist die Umkehrung der ersten Hälfte der Zahl. Wenn k eine ungerade Zahl ist, entfernen Sie die letzte Ziffer aus der ersten Hälfte der Zahl.

Algorithmus

• Initialisieren Sie die Zahlen n und k.
• Ermitteln Sie die Länge der ersten Hälfte des k-stelligen Palindroms mithilfe des Werts von k.
• Die erste Hälfte der Palindromzahl ist pow(10, Länge) + n - 1.
• Wenn k eine ungerade Zahl ist, entferne die letzte Ziffer aus der ersten Hälfte des Palindroms.
• Die erste Hälfte umdrehen und die zweite Hälfte ausdrucken.

Implementierung

Das Folgende ist die Implementierung des obigen Algorithmus in 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;
}

Ausgabe

Wenn Sie den obigen Code ausführen, erhalten Sie die folgenden Ergebnisse.

10066001

Das obige ist der detaillierte Inhalt vonN-te Palindromzahl unter K Ziffern in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!