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

Question

如何在 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 位数字的倍数 maxInt 将是9999.等等

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

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

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

如何在 30 多岁

的时间内 maxInt=9999 达到 return 99000099

Answer 1

如果您修复 x>=y，它会变得更快，因此 99*91 和 91*99 将不会被单独测试和找到
当找到一个回文后，内循环就可以退出（因为它是向下计数的，它可能找到的所有回文对于相同的 x 肯定比 "current" 小）
如果当前乘积小于当前最大值，内循环也可以退出
如果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):也许）

严格来说，它应该只检查 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

Answer 2

您可以通过多种方式减少计算量。在我的笔记本电脑上，以下内容在 4 秒内完成：

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

print(palindrome(9999))

因为乘法是可交换的，所以我们不需要同时查看，比如 21*34 和 34*21。因此，内部循环可以在 x 处停止，而不是一直下降到 0。这将执行时间减半。
字符串操作很昂贵。如果在计算乘积后，我们发现它不大于我们目前看到的最大回文，那么检查它本身是否是回文就没有意义了。

Answer 3

这是一种快速高效的算法（基于数学计算）：

def palindrome(maxInt):
    largest_palindrome = 9
    digit_count = len(str(maxInt))
    a = maxInt
    while a >= 10**(digit_count-1):
        if a % 11 == 0:
            b = maxInt
            divided_by = 1
        else:
            b = maxInt - maxInt % 11
            divided_by = 11

        while b >= a:
            if a * b <= largest_palindrome:
                break
            prod = a * b
            str_num = str(prod)
            if str_num == str_num[::-1]:
                largest_palindrome = prod

            b = b - divided_by
        a = a - 1
    return largest_palindrome

它在几分之一秒内给出结果。您还可以使用@tevemadar 版本检查 benchmark result。 （后面会补充算法的解释）

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

Fastest algorithm to find the largest palindrome that is the product of 2 numbers with the same number of digits

python

palindrome