algorithm - matlab中的大数回文

Question

将数字转换为字符串并反转该字符串，然后比较两个字符串是否相等。

我正在使用上述算法找出回文。

问题是，我想检测从 10^50 到 10^100 的回文数，这个函数太耗时了。

有没有更快的算法或提示来做到这一点？

Answer 1

我认为您需要对此采取更“组合”的方法。与其暴力破解所有这些数字(以当今的计算能力可能无法完成……)，不如分步考虑:

给定数字的个数，有多少可能的组合可以是回文？

好吧，首先，我们可以开始查看数字很少的数字，以了解它的工作原理:

• 对于 2 位数字，如果您选择第一个数字，则第二个数字必须相同(如果该数字是回文数字)。也就是说，在基数 10 中，您有 10 种选择(如果您将 00 算作两位数)或 9 种选择(如果您不这样做，这更有意义)。

• 对于 3 位数字，如果您选择第一个数字，则第三个数字是固定的。这给了你 9 个选择(因为我们不称 020 三位数)。中间的数字仍然是空的，所以给了你另外 10 个(因为中间的数字可以是 0)独立的选择。回文总数由 9*10 = 90 给出。

• 对于4位数字，您可以独立选择第一位和第二位，然后固定第三位和第四位。第一个必须是非零的，但之后的零是可以的。 9*10 = 90 个回文。

• 对于5位数字，您可以独立选择第一、第二和第三位，然后固定第四和第五位。第一个非零，其余完全免费:9*10^2 = 900 个回文。

我认为我们已经准备好推广这一点，是吗？

一般方法

我们在上面注意到，对于偶数位数字，您可以独立选择数字的半数，对于奇数数位，您也可以选择中间位。 第一个 数字不能为 0，但所有其他数字都可以，屈服。这意味着对于 N 位的数字，回文选择的数量是
P = 10 _* 9 ^{ceil(N/₂)-1}。请注意，要使其正常工作，^N/₂ 必须是浮点除法 - 对于 N = 7，我们需要 3.5，因此我们可以将其四舍五入为 4 并选择中间数字。

具体问题

要计算 10^50 和 10^100 之间的回文数，我们还需要利用一点信息:我们知道这些数字的位数。由于 10⁵⁰ 和 10⁵¹ 之间的所有数字都有 50 位数字(并且由于 10¹⁰⁰ 不是回文)，剩下的就很简单了。

一个给你计数的 python 片段:

import math

palindromes = 0
for n in range(50):
    palindromes = palindromes + 10**math.ceil((n+50)/2.0)*0.9

或者，使用一个做完全相同事情的单行代码:

import math
sum(.9*10**math.ceil((n+50)/2.0) for n in range(50))

因为这个循环超过 50 次迭代，而不是将近 10¹⁰⁰，所以对于任何计算机来说都没有问题。还要注意 9*10^N-1 = 0.9*10^N。