如何有效地计算n位回文数？

Question

我认为这个问题很简单，可以让understand.For更清晰，我举了一个例子：

在2位回文列表中，为77 (1为11，2为22，等等)。

很明显，存在一个蛮力的解决方案，但它并不有效。

有人能给我一些更好的解决办法吗？

Answer 1

首先，我们可以简化这个问题，因为我们只需要查看数字的前半部分(如果有奇数位数，则取四舍五入)。我将调用第一组数字有效数字和rest 非有效数字。

这是因为non-significant数字必须与有效数字(反向)相匹配。不可能有另一个回文数字具有相同的前导显着数字和不同的非显着数字。有效数字确定整个回文编号。

现在，我们只需要想出一个算法来生成第n个有效的有效数字。如果允许前导零，这会更容易，所以我们将提出允许前导零的算法，然后调整算法。

前几个回文(重要数字)是：

• 1: 0000
• 2: 0001
• 3: 0002
• ..。
• 100: 0099

因此，我们可以通过找到(n-1)的十进制表示来找到第n个数的有效数字。

为了在不允许前导零的情况下调整算法以工作，我们从一个作为前导数字的开头：

• 1: 1000
• 2: 1001
• 3: 1002
• ..。
• 100: 1099

这归结为找到(n-1) + 1000 = n + 999的十进制表示，并展开为一个完整的回文。

示例：查找长度为9的第113回文。

• 确定要查看的数字数:将(9/ 2) =5->只查看前5位数。
• 查找要添加的数字以去掉前导零：10^(5-1) = 10000
• 使用公式：(113-1)+ 10000 = 10112
• 扩展为回文：101121101

此外，该算法还可以推广到寻找任意一组有序符号(或字母表)的第n个回文。

广义算法

给定:找到回文数n，回文符号有m个数字，有p个符号(十进制10个符号)。

• 设Q=上限(m/ 2)
• 设偏移量=p^ (q - 1)
• 设数= (n - 1) +偏移量
• 让答案被扩展为回文

Answer 2

当数字数为偶数时，只需取第n个数字，从100.0开始，有一半多的数字，其中长度是数字数的一半。回文就是这个数字，后面跟着它的镜像。

对于奇数的数字，只需取这个数字的一半的上限，并从100.0按同样的方式计算。然后回文是这个数字，然后是它的镜像，去掉第一个数字。

第65位10位数：

65 + 9999 = 10064

1006446001

第10298 13位数字：

10298 + 999999 = 1010297

1010297920101

Answer 3

对于两个数字回文，两个连续回文之间的差额是11。