Để tìm palindrome thứ n gồm k chữ số, chúng ta có thể lặp lại từ số k chữ số đầu tiên cho đến khi chúng ta tìm thấy số palindrome thứ n. Cách tiếp cận này không hiệu quả. Bạn có thể tự mình thử.
Bây giờ, hãy xem phương pháp hiệu quả để tìm palindrome thứ n gồm k chữ số.
Có hai nửa trong các con số. Nửa đầu bằng phần ngược lại của nửa sau.
Nửa đầu của số thứ n có k chữ số là
Nếu k lẻ thì (n - 1) + 10 k / 2 else (n-1) +10 k / 2-1
Nửa sau của số thứ n có k chữ số sẽ là đảo ngược của nửa số đầu tiên. Cắt bớt chữ số cuối cùng của nửa số đầu tiên, nếu k là số lẻ.
Thuật toán
- Khởi tạo các số n và k.
- Tìm độ dài của nửa đầu tiên của chữ số k-chữ số palindrome bằng cách sử dụng giá trị của k.
- Nửa đầu của palindrome là pow (10, chiều dài) + n - 1.
- Nếu k là số lẻ, thì hãy xóa chữ số cuối cùng khỏi nửa đầu của palindrome.
- Đảo ngược nửa đầu và in nửa sau.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
10066001