0

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

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

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

任何更快的算法或提示来做到这一点？

4

3 回答 3

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 / 2 )-1。请注意，为此，N / 2必须是浮点除法 - 对于 N = 7，我们需要 3.5，因此我们可以将其四舍五入到 4 并选择中间数字。

具体问题

要计算 10^50 和 10^100 之间的回文数，我们还需要利用一点信息：我们对这些数字的位数的了解。由于 10 50和 10 51之间的所有数字都有 50 位数字（并且由于 10 100不是回文），其余部分非常简单。

一个给你计数的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 100 次，因此对于任何计算机来说都没有问题。还要注意 9*10 N-1 = 0.9*10 N。

于 2013-04-13T14:01:56.647 回答
1

有多少个 k 位回文数？好的，现在，有多少个 k+2 位回文数？看到我们可以为回文数写一个递归。

将 P(n) 定义为 n 位回文数。任意假设只有一个 0 位回文，所以 P(0) = 1。

同样，说有 9 个一位回文串似乎是合乎逻辑的，因此 P(1) = 9。并且 P(2) 也是 9，因为两位数回文串很容易构建和计数。

我们可以生成 3 位回文数吗？我们将通过向所有 1 位回文串附加/前置任何非零数字来做到这一点。这错过了 x0x 形式的回文，所以我们也将它们添加进去。

P(3) = P(1)*9 + 1*9 = (P(1) + 1)*9

5位回文呢？再次，将任何非零数字附加并添加到较小的回文序列中。但是我们需要担心回文中需要零的情况。所以 x0p0x 和 x000x 都是回文。

P(5) = P(3)*9 + P(1)*9 + 1*9 = (P(3) + P(1) + 1)*9

（我们可以更进一步，将 P(5) 写成 P(1)。）

所以我们有 P(5) = 900。一个好主意是总是验证这样的简单声明。这让我们更有信心，我们没有错过任何东西。我会在 MATLAB 中做到这一点。

n = 10000:99999;
D = dec2base(n,10);
isp = sum(all(D == fliplr(D),2))

isp =
   900

我们可以外推上述逻辑来计算 7 位回文数，得到公式：

P(7) = P(5)*9 + P(3)*9 + P(1)*9 + 1*9 = (P(5) + P(3) + P(1) + 1)*9

这表明 P(7) = 9000。同样，我们可以使用蛮力测试该声明。

n = 1000000:9999999;
D = dec2base(n,10);
isp = sum(all(D == fliplr(D),2))
isp =

        9000

因此，当 n 为奇数时，计算 n 位回文似乎很容易。计算偶数 n 的 n 位回文数同样容易。我会让你推导出这些关系。

于 2013-04-13T14:55:50.470 回答
0

因为数字的回文属性基本上取决于您要表示数字的基数，所以您必须将其转换为字符串，在您选择的基数中。特定的基地可能有特定的技巧，但在一般情况下，我猜最快的方法是：

% Suppose your number is stored as string in str
strcmp(str, str(end:-1:1))

稍后编辑：现在我看到您要寻找的不是“回文”测试，而是计算两个给定数字之间的回文。同样，这取决于基数，但是您始终可以通过计算基数 B 中具有 n 位数字的有效数字来计算基数 B 中具有 2n 或 2n+1 位数字的回文数。但这与 Matlab 无关，我猜它与数学有关。

甚至稍后编辑：也许这会有所帮助（这不是最佳的，但我希望清楚且有帮助）：

%COUNT_PALINDROMES returns the number of palindrome
% numbers with nd digits in base b

function np = count_palindromes(b, nd)

        % For the sake of brevity the function assumes
        % that b has natural values greater than 1, and
        % nd has appropriate values also.

        if nd == 1
                % Single digit "palindromes"
                np = b;

        elseif mod(nd,2) == 1
                % 2n+1 digit palindromes
                %    abcd...uvXvu...cba
                n  = fix(nd/2);
                np = (b-1)*b^n;

        else
                % 2n digit palindromes
                %    abcd...uvvu...cba
                n = fix(nd/2);
                np = (b-1)*b^(n-1);
        end;
end

使用其值时请注意浮点精度。我不确定您是否能够准确地将回文数保持在双精度 - 这是 Matlab 中的默认类型。根据需要更改为其他（集成）类型。

于 2013-04-13T13:15:35.810 回答