нужен алгоритм для поиска n-го палиндромного числа
считают, что
0 -- is the first
1 -- is the second
2 -- is the third
.....
9 -- is the 10th
11 -- is the 11th
Каков эффективный алгоритм для поиска n-го палиндромного числа?
Решение
Я предполагаю, что 0110 — это не палиндром, а 110.
Я мог бы потратить много слов на описание, но этой таблицы должно быть достаточно:
#Digits #Pal. Notes
0 1 "0" only
1 9 x with x = 1..9
2 9 xx with x = 1..9
3 90 xyx with xy = 10..99 (in other words: x = 1..9, y = 0..9)
4 90 xyyx with xy = 10..99
5 900 xyzyx with xyz = 100..999
6 900 and so on...
Другие решения
(Ненулевые) палиндромы с четным числом цифр начинаются с p(11) = 11, p(110) = 1001, p(1100) = 100'001,..., Они построены путем взятия индекса n - 10^L, где L=floor(log10(n))и добавьте обращение этого числа: p(1101) = 101|101, p(1102) = 102|201, ..., p(1999) = 999|999, etc, Этот случай должен быть рассмотрен для индексов n >= 1.1*10^L but n < 2*10^L,
когда n >= 2*10^Lмы получаем палиндромы с нечетным числом цифр, которые начинаются с p(2) = 1, p(20) = 101, p(200) = 10001 etc., и может быть построен таким же образом, используя снова n - 10^L with L=floor(log10(n))и добавив обращение этого числа, теперь без последней цифры: p(21) = 11|1, p(22) = 12|1, ..., p(99) = 89|8, ...,
когда n < 1.1*10^L, вычтите 1 из L, чтобы быть в правильной настройке с n >= 2*10^L для случая нечетного числа цифр.
Это дает простой алгоритм:
p(n) = { L = logint(n,10);
P = 10^(L - [1 < n < 1.1*10^L]); /* avoid exponent -1 for n=1 */
n -= P;
RETURN( n * 10^L + reverse( n \ 10^[n >= P] ))
}
где […] равно 1, если … истинно, 0 иначе, и \ является целочисленным делением.
(Выражение n \ 10^[...] эквивалентно: if ... then n\10 else n.)
(Я добавил условие n> 1 в показателе степени, чтобы избежать P = 10 ^ (- 1) для n = 0. Если вы используете целочисленные типы, вам это не нужно. Другой вариант — поставить max (…, 0) как показатель степени в P, или использовать if n=1 then return(0) в самом начале. Также обратите внимание, что вам не нужен L после назначения P, так что вы можете использовать одну и ту же переменную для обоих.)