พาลินโดรมลำดับที่ n ของ k หลักใน C++

โจทย์

เพื่อหาพาลินโดรมลำดับที่ n ของ k หลัก เราสามารถวนลูปจากตัวเลข k หลักแรกจนกว่าจะเจอพาลินโดรมลำดับที่ n วิธีนี้ไม่มีประสิทธิภาพ คุณสามารถลองทำเองได้

ตอนนี้มาดูวิธีที่มีประสิทธิภาพในการหาพาลินโดรมลำดับที่ n ของ k หลัก

มีสองครึ่งในตัวเลข ครึ่งแรกเท่ากับการกลับของครึ่งหลัง

ครึ่งแรกของตัวเลขลำดับที่ n ที่มี k หลักคือ

ถ้า k เป็นคี่ แล้ว (n - 1) + 10^k/2 มิฉะนั้น (n-1)+10^k/2-1

ครึ่งหลังของตัวเลขลำดับที่ n ที่มี 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