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

问题描述 投票:3回答:2

考虑一下

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

什么是找到第n个回文数的有效算法?

c++ algorithm palindrome
2个回答
10
投票

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

0
投票

具有偶数位数的(非零)回文从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时,对于奇数位数的情况,从q减去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^[...]相当于:if ... then n\10 else n。)

(我在指数中添加了条件n> 1,以避免在n = 0时P = 10 ^( - 1)。如果使用整数类型,则不需要这个。另外选择它放置max(..., 0)作为P中的指数,或者在开始时使用if n=1 then return(0)。还要注意在分配P后你不需要L,所以你可以对两者使用相同的变量。)

© www.soinside.com 2019 - 2024. All rights reserved.