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

Question

我认为这个问题很容易理解.为了更清楚,我举例说明:

在2位数的回文列表中,第7回文是77(第1是11,第2是22,依此类推).

显然存在蛮力解决方案,但效率不高.

谁能建议我一些更好的解决方案来解决问题？

Answer 1

首先,我们可以简化问题,因为我们只需要查看数字的前半部分(如果有奇数个数字则向上舍入).我将调用第一组数字有效数字和其余非有效数字.

这是因为非有效数字必须与有效数字匹配(反之).不可能有另一个回文数字具有相同的前导有效数字和不同的非有效数字.该显著数字确定整个回文数.

现在,我们只需要提出一种算法来生成第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)
• 设offset = p ^(q - 1)
• 设数 =(n - 1)+ 偏移量
• 让答案被数扩大为回文

Answer 2

前几个7位回文是:

• 1000001
• 1001001
• 1002001
• 1003001
• ...
• 1009001
• 1010101
• 1011101
• ...

我认为这是很容易从什么模式看ň ^日 米位数字回文...