需要算法来寻找第n个回文数。

Question

请考虑：

    0 -- is the first
    1 -- is the second
    2 -- is the third
    .....
    9 -- is the 10th
    11 -- is the 11th

寻找第n个回文数的高效算法是什么？

- Merna

---

@SingerOfTheFall 我可以找到一个算法来找到具有k位数的第n个回文数，例如我可以找到具有8位数的第113个回文数是11122111。 - Merna

使用该算法并在数字数量上添加迭代。 - Oswald

@Oswald，同意。但是OP还应该澄清他只需要算法还是_快速的_算法。 - SingerOfTheFall

@Oswald，不好意思，你能给个例子吗？ - Merna

@SingerOfTheFall OP确实说了“高效算法”。 - Bernhard Barker

Answer 1

我假设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...

- Sjoerd

---

我猜那非常有用 :) 非常感谢。 - Merna

Answer 2

具有偶数位数的（非零）回文数从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 等等 开始，并且可以使用相同的方式构造，再次使用 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 时，将 L 减 1 可以得到正确的设置，使得对于奇数位的情况，有 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^[...]等同于：如果...则n\10 else n。）

（我在指数中添加了条件n>1，以避免n=0时P = 10^(-1)。如果您使用整数类型，则不需要此条件。另一种选择是将max(...,0)作为P的指数，或者在开始时使用if n=1 then return(0)。还要注意，在分配P后，您不需要L，因此可以对两者使用相同的变量。）

- Max