ในการหา palindrome ที่ n ของ k หลัก เราสามารถวนซ้ำจากตัวเลข k หลักแรกจนพบ palindrome number ที่ n วิธีนี้ไม่ได้ผล คุณสามารถลองด้วยตัวคุณเอง
ทีนี้ มาดูวิธีที่มีประสิทธิภาพในการหาพาลินโดรมที่ n ของหลัก k กัน
มีสองส่วนในตัวเลข ครึ่งแรกเท่ากับครึ่งหลังของครึ่งหลัง
เลขครึ่งแรกของตัวที่ n มีหลัก k คือ
ถ้า k เป็นเลขคี่ ดังนั้น (n - 1) + 10 k/2 อื่น(n-1)+10 k/2-1
เลขครึ่งหลังของเลข n-th ที่มี k หลักจะกลับด้านของเลขครึ่งแรก ตัดหลักสุดท้ายจากครึ่งแรกของตัวเลข ถ้า k เป็นเลขคี่
อัลกอริทึม
- เริ่มต้นตัวเลข n และ k
- หาความยาวของครึ่งแรกของพาลินโดรม k หลักโดยใช้ค่าของ k
- ครึ่งแรกของพาลินโดรมคือ pow(10, length) + n - 1.
- หาก k เป็นเลขคี่ ให้ลบหลักสุดท้ายออกจากครึ่งแรกของพาลินโดรม
- ย้อนกลับครึ่งแรกและพิมพ์ครึ่งหลัง
การนำไปใช้
ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน 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;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
10066001
