Найти n-ый палиндром из k цифр

Даны два целых числа n и k. Требуется найти n-ый по лексикографическому порядку чисел палиндром из k цифр.

Например, при n = 5, k = 2 ответ будет 55 (11, 22, ..., 55), а для n = 4, k = 4 находим значение 1331 (1001, 1111, 1221, 1331)

Перебор, конечно, излишество, можно попробовать сделать формулой. Для палиндрома первая половина цифр по определению совпадает со второй, записанной в обратном порядке. Скажем, для k = 8 наименьший палиндром всегда начинается с 1 и для первых 4 цифр числа имеет вид 1-ый: 1000, 2-ой: 1001, 3-ий: 1002, ..., 100-ый: 1099.

В общем виде получаем для n-ого палиндрома формулу (n-1) + 1000. Для k-значного числа формулу можно обобщить в виде:

если k нечётное, число = (n-1) + 10k / 2
иначе число = (n-1) + 10k / 2 - 1

Вторую половину цифр можно получить выводом цифр первой половины в обратном порядке. Перед этим, если k - нечётное, мы должны отбросить последнюю цифру числа.

Программа запускалась в консоли Visual Studio 2019.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string nthPalindrome (int n, int k) {
 int temp = (k & 1) ? (k / 2) : (k / 2 - 1); //Первая половина цифр
 int palindrome = (int) pow (10, temp);
 palindrome += n - 1;
 string result = to_string(palindrome);
 if (k & 1) palindrome /= 10; // Если k нечётно, обрезать последнюю цифру
 while (palindrome) {
  result += to_string(palindrome % 10);
  palindrome /= 10;
 }
 return result + "\n";
}

int main() {
 int n = 5, k = 4;
 cout << n << "'th palindrome of " << k << " digit(s) = " << nthPalindrome(n, k);

 cin.get(); return 0;
}

05.09.2020, 23:14 [1276 просмотров]