时间戳

首页 > 解决方案 > 找到最大回文数的最快算法，它是具有相同位数的 2 个数字的乘积

python - 找到最大回文数的最快算法，它是具有相同位数的 2 个数字的乘积

问题描述

如何让这段代码在 30 秒内运行，以找到最大的回文数，它是 2 个具有相同位数的数字的乘积？

def palindrome(maxInt):
    pa=[]
    for x in range(maxInt,0,-1):
        for y in range(maxInt,0,-1):
            num=x*y
            if str(num) == str(num)[::-1]:
                pa.append(num)
    return max(pa)

maxInt是具有指定位数的最大数。例如，如果您想要一个是 2 个 3 位数字的倍数的回文数，您maxInt将是 999。如果您想要一个是 2 个 4 位数字的倍数的最大回文数，则为maxInt9999。等等。

如果maxInt = 9，它应该输出 9。

如果maxInt = 99，它应该输出 9009。

所以如果maxInt = 999，程序应该输出 906609。

如何让它在 30 岁以下返回maxInt=999999000099

标签： pythonpalindrome

解决方案

  1. 如果你修复它会变得更快x>=y，所以不会单独测试和99*91发现91*99
  2. 当找到回文时，内部循环可以退出（当它向下计数时，它可能找到的所有回文x肯定小于“当前”回文）
  3. 如果当前乘积小于当前最大值，内层循环也可以退出
  4. 如果x*x小于当前最大值，外循环也可以退出
def palindrome(maxInt):
    maxpal=0
    for x in range(maxInt,0,-1):
        if x*x<maxpal:                         # 4.
            break
        for y in range(x,0,-1):                # 1.
            num=x*y
            if num<maxpal:                     # 3.
                break
            if str(num) == str(num)[::-1]:
                maxpal=num
                break                          # 2.
    return maxpal

（当然3.可能在范围内，for y in range(x,maxpal//x,-1):也许）

  1. 严格来说，它应该只检查y-s 具有与 相同的位数x，这还没有解决，但是**向下舍入log10()毕竟可以做到这一点。

我当前的完整代码：

import math,time

def palindrome(maxInt):
    maxpal=0
    for x in range(maxInt,0,-1):
        if x*x<maxpal:                                                     # 4.
            break
        for y in range(x,max(maxpal//x,10**int(math.log10(x))-1),-1):      # 1. 3. 5.
            num=x*y
            if str(num) == str(num)[::-1]:
                maxpal=num
                break                                                      # 2.
    return maxpal

start=time.time()
print(palindrome(9))
print(palindrome(99))
print(palindrome(999))
print(palindrome(9999))
print(palindrome(99999))
print(palindrome(999999))
print("%d seconds" % (time.time()-start))

示例输出：

9
9009
906609
99000099
9966006699
999000000999
0.731034 seconds

推荐阅读