python - 两个基数中的回文数，欧拉计划 #36

Question

这是我对 Project Euler problem 36 的解决方案，内容如下:

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

我的结果有点不对。谁能帮忙？

def findnum(n):
    a = 0
    for i in range(0, n + 1):
        temp = '{0:08b}'.format(i)
        if str(i) == str(i)[::-1] and str(temp) == str(temp)[::-1]:
            a += i 
    return a 

print findnum(1000000)

我得到的结果是872096，但是正确答案好像是872187。不过这两者之差，91，不是回文。我做错了什么？

Answer 1

你在问题​​描述中遗漏了一些东西:

Please note that the palindromic number, in either base, may not include leading zeros.

但您正在使用前导零:

temp = '{0:08b}'.format(i)

从格式中删除 08；这里根本不需要将其填充到宽度:

temp = '{0:b}'.format(i)

通过此更改，您将获得正确答案。

您也可以只使用 format() function相反，因为您没有将字符串放入更大的模板中。您不需要将它提供给 str()，因为 format() 已经生成了一个字符串。我会交换测试以首先测试二进制回文并避免额外的 str() 调用。 range() 调用中的 n + 1 不是必需的；问题描述要求所有 100 万以下的数字:

for i in range(n):
    temp = format(i, 'b')
    if temp == temp[::-1] and str(i) == str(i)[::-1]:
        a += i

或者您可以先测试十进制回文，然后格式:

for i in range(n):
    decimal = str(i)
    if decimal != decimal[::-1]:
        continue
    binary = format(i, 'b')
    if binary == binary[::-1]:
        a += i

这减少了整个运行时的相当多的调用，使最终版本的速度提高了一倍多:

>>> from timeit import timeit
>>> def findnum_orig(n):
...     a = 0
...     for i in range(0, n + 1):
...         temp = '{0:b}'.format(i)
...         if str(i) == str(i)[::-1] and str(temp) == str(temp)[::-1]:
...             a += i 
...     return a 
... 
>>> def findnum_optimised(n):
...     a = 0
...     for i in range(n):
...         decimal = str(i)
...         if decimal != decimal[::-1]:
...             continue
...         binary = format(i, 'b')
...         if binary == binary[::-1]:
...             a += i
...     return a
... 
>>> timeit('fn(1000000)', 'from __main__ import findnum_orig as fn', number=10)
10.886759996414185
>>> timeit('fn(1000000)', 'from __main__ import findnum_optimised as fn', number=10)
3.7782959938049316

那是因为 str() 比 format() 快很多:

>>> timeit('for i in range(1000): str(i)', number=1000)
0.17951107025146484
>>> timeit('for i in range(1000): format(i, 'b')', number=1000)
0.2837510108947754

由于100万以下只有1999个十进制数和2000个二进制回文数:

>>> sum(1 for i in range(1000000) if str(i) == str(i)[::-1])
1999
>>> sum(1 for i in range(1000000) if format(i, 'b') == format(i, 'b')[::-1])
2000

除了那些 1999 十进制回文之外，避免所有较慢的操作可以节省您很多时间。

我们可以通过切换将整数转换为二进制的方式来使其更快； bin() function也产生二进制数，尽管带有 0b 前缀。即使必须删除该前缀，使用该函数也比使用 format() 更快:

>>> timeit('for i in range(1000): format(i, "b")', number=1000)
0.46987009048461914
>>> timeit('for i in range(1000): bin(i)[2:]', number=1000)
0.24124693870544434

如果您使用的是 Python 2.x，您还应该使用 xrange() function避免创建包含 1.000.000 个整数的列表。这将最终时间安排为:

>>> def findnum_bin_xrange(n):
...     a = 0
...     for i in xrange(n):
...         decimal = str(i)
...         if decimal != decimal[::-1]:
...             continue
...         binary = bin(i)[2:]
...         if binary == binary[::-1]:
...             a += i 
...     return a 
... 
>>> findnum_bin_xrange(1000000)
872187
>>> timeit('fn(1000000)', 'from __main__ import findnum_bin_xrange as fn', number=10)
3.5071611404418945

这大约是原始代码时间的 1/3。