Найти 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 [1278 просмотров]