3

我想计算大区间数据中有多少回文数说10^15

我的简单代码（python）片段是：

def count_palindromes(start, end):
    count = 0
    for i in range(start, end + 1):
        if str(i) == str(i)[::-1]:
            count += 1

    return count

start = 1000 #some initial number
end = 10000000000000 #some other large number

if __name__ == "__main__":
    print count_palindromes(start, end)

它是一个简单的程序，一个一个地检查每个数字。它耗时且占用大量计算机资源。

有没有其他方法/技术可以用来计算回文数？任何用于此的算法？

我想尽量减少生成输出所花费的时间。

4

3 回答 3

11

当您想计算在两个限制之间具有某些给定属性的数字时，解决稍微简单的问题通常很有用

0和之间有多少具有给定属性的数字n？

固定一个限制可以使问题更容易解决。当较简单的问题解决后，您可以通过简单的减法得到原始问题的解决方案：

countBetween(a,b) = countTo(b) - countTo(a)

或者countTo(b ± 1) - countTo(a ± 1)，取决于是否包含限制countTo以及应包含哪些限制countBetween。

如果可能出现负极限（我认为不是回文），countTo(n)则应该是<= 0负极限n（可以将函数视为相对于计数度量的积分）。

所以让我们确定

palindromes_below(n) = #{ k : 0 <= k < n, k is a palindrome }

如果我们假设 0 不是回文，我们会在第一部分得到更统一的公式，所以对于第一部分，我们这样做。

第 1 部分：有多少个给定位数d的回文？

第一个数字不能是0，否则它是不受限制的，因此有 9 种可能的选择（b-1对于任意基数的回文b）。

最后一个数字与第一个数字相同，因为它应该是回文。

第二个数字 - if d >= 3- 可以独立于第一个数字任意选择。这也决定了倒数第二个数字。

如果d >= 5，也可以自由选择第三位，以此类推。

片刻的思考表明，对于d = 2*k + 1or d = 2*k + 2，有一些k数字可以不受限制地选择，而一个数字（第一个）受到限制，即它是非零的。所以有

9 * 10**k

d-digit 回文然后（(b-1) * b**k对于 base b）。

这是一个很好且简单的公式。由此，使用几何和的公式，我们可以很容易地获得小于 10 n的回文数（即最多n位数）：

  • 如果n是偶数，则数为

       n/2-1                n/2-1
2 *  ∑ 9*10**k =  18 *    ∑ 10**k = 18 * (10**(n/2) - 1) / (10 - 1) = 2 * (10**(n/2) - 1)
    k=0                  k=0

  • 如果n是奇数，则数为

    2 * (10**((n-1)/2) - 1) + 9 * 10**((n-1)/2) = 11 * (10**((n-1)/2) - 2

（对于一般基数b，数字分别2 * (b**(n/2) - 1)为(b+1) * b**((n-1)/2) - 2）。

这不再那么统一了，但仍然很简单：

def palindromes_up_to_n_digits(n):
    if n < 1:
        return 0
    if n % 2 == 0:
        return 2*10**(n//2) - 2
    else:
        return 11*10**(n//2) - 2

（请记住，我们还不算 0）。

现在剩下的部分。n > 0给定k数字，回文< n要么是

  • 少于k数字的回文，有palindromes_up_to_n_digits(k-1)它们，或
  • k正好数字小于 的回文数n。

所以还是要算后者。

第2部分：

让m = (k-1)//2和

d[1] d[2] ... d[m] d[m+1] ... d[k]

的十进制表示n（整个事情对其他基础的工作原理相同，但我没有在下面明确提及），所以

    k
n = ∑ d[j]*10**(k-j)
   j=1

对于每一个1 <= c[1] < d[1]，我们可以自由选择m数字c[2], ..., c[m+1]来获得一个回文。

p = c[1] c[2] ... c[m+1] {c[m+1]} c[m] ... c[2] c[1]

（c[m+1]奇数出现一次，偶数出现k两次k）。现在，

c[1]*(10**(k-1) + 1) <= p < (c[1] + 1)*10**(k-1) <= d[1]*10**(k-1) <= n,

所以所有这些10**m回文（对于给定的选择c[1]！）都小于n.

因此存在(d[1] - 1) * 10**m k-digit 回文数，其第一个数字小于 的第一个数字n。

现在让我们考虑第一个数字小于的k-digit 回文串。d[1]n

如果k == 2，则只有一个 if d[1] < d[2]，否则没有。如果k >= 3，对于每个0 <= c[2] < d[2]，我们可以自由选择m-1数字c[3] ... c[m+1]来获得回文

p = d[1] c[2] c[3] ... c[m] c[m+1] {c[m+1]} c[m] ... c[3] c[2] d[1]

我们看到p < n：

d[1]*(10**(k-1) + 1) + c[2]*(10**(k-2) + 10)
         <= p < d[1]*(10**(k-1) + 1) + (c[2] + 1)*(10**(k-2) + 10)
         <= d[1]*(10**(k-1) + 1) + d[2]*(10**(k-2) + 10) <= n

（假设k > 3,k == 3替换10**(k-2) + 10为 10）。

所以这使得d[2]*10**(m-1) k-digit 回文第一个数字d[1]和第二个数字小于d[2]。

继续，对于1 <= r <= m，有

d[m+1]*10**(m-r)

k-digit 回文数，其第一个r数字是d[1] ... d[r]并且其r+1st数字小于d[r+1]。

总结一下，有

(d[1]-1])*10**m + d[2]*10**(m-1) + ... + d[m]*10 + d[m+1]

k- 数字回文，其前一位m+1数字小于 的对应数字，n所有前面的数字都等于 的对应数字n。显然，这些都小于n。

有一位数的k回文数p，其第一个m+1数字是d[1] .. d[m+1]，我们也必须计算它 if p < n。

所以，总结起来，现在也加入 0，我们得到

def palindromes_below(n):
    if n < 1:
        return 0
    if n < 10:
        return n   # 0, 1, ..., n-1

    # General case
    dec = str(n)
    digits = len(dec)
    count = palindromes_up_to_n_digits(digits-1) + 1   # + 1 for 0
    half_length = (digits-1) // 2
    front_part = dec[0:half_length + 1]
    count += int(front_part) - 10**half_length
    i, j = half_length, half_length+1
    if digits % 2 == 1:
        i -= 1
    while i >= 0 and dec[i] == dec[j]:
        i -= 1
        j += 1
    if i >= 0 and dec[i] < dec[j]:
        count += 1
    return count

由于限制都包含在给定问题的计数中（除非 OP 被误解），所以我们有

def count_palindromes(start, end):
    return palindromes_below(end+1) - palindromes_below(start)

快速解决方案：

>>> bench(10**100,10**101-1)
900000000000000000000000000000000000000000000000000 palindromes between
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
and
99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
in 0.000186920166016 seconds
于 2013-04-14T09:14:25.457 回答
2

实际上，这对 Google Codejam 来说是个问题（我很确定你不应该得到外界的帮助），但唉，我会投入 2 美分。

我为这个大问题想出（但未能实现）的想法是预编译（在运行时生成，而不是硬编码到源代码中）所有回文数的列表小于10^15（不是很多，大约需要 60 秒) 然后找出这些数字中有多少位于每个输入的范围之间。

编辑：这对问题不起作用10^100，就像你说的那样，这将是一个数学解决方案（虽然如果你看有一个模式，所以你只需要一个算法来生成具有该模式的所有数字）

于 2013-04-13T12:13:21.570 回答
1

我认为这适用于像 Project Euler 之类的东西......我的粗略想法是生成所有数字，直到您的限制长度的一半（例如，如果您要达到 99999，则上升到 99）。然后反转它们，将它们附加到未反转的那个，并可能在中间添加一个数字（对于奇数长度的数字）。您可能需要对重复项或奇怪的项进行一些过滤（例如，如果您在数字或 sommat 的开头有一个零），但这应该比您所做的要快得多。

于 2013-04-13T12:00:54.867 回答