寻找由相同位数的两个数字相乘得到的最大回文数的最快算法

Question

如何使这段代码在30秒内运行，以查找由两个具有相同位数的数字相乘得到的最大回文数？

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是指定位数的最大数字。例如，如果您想要一个由两个三位数相乘得到的回文数字，maxInt将为999。如果您想要这样一个回文数字，它是两个四位数的倍数，并且最大，maxInt将为9999。等等。

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

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

因此，如果maxInt=999，程序应输出906609。

如何使它在30秒内返回maxInt=9999的99000099？

- YEp d

---

可能是在Python中找到两个三位数乘积的最大回文数的重复问题。 - Georgy

嘿。https://www.geeksforgeeks.org/largest-palindrome-product-two-n-digit-numbers/ - AKX

Answer 1

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): 或许会出现这种情况。

5. 严格来说，它应该只检查与x相同位数的y，但这一点尚未得到解决，不过**和向下取整后的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

- tevemadar

---

@YEpd 我认为现在更好了。 - tevemadar

@AKX，那是作弊 :-) - tevemadar

保持滚动最大值，如果 num < rollingMax，则可以跳过其余的 y 并继续下一个 x。编辑：当我输入时，您已经进行了此修复，该死！ - Turksarama

@tevemadar 我称之为SO格式的怪癖 ;) 另一个选项是使用围栏代码块。 - AKX

@MushifAliNawaz，是的，我记得。偶数位回文数是11的倍数。加上解释，你就会得到我的点赞。 - tevemadar

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))

1. 由于乘法是可交换的，我们不需要同时考虑 21*34 和 34*21。因此，内部循环可以在 x 处停止，而不必一直到 0。这将减少执行时间一半。

2. 字符串操作非常耗费资源。如果计算出来的积并没有大于目前为止最大的回文数，那么甚至没有必要检查它是否是回文数。

- NPE

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版本的基准测试结果进行检查。（我稍后会添加算法说明。）

- Mushif Ali Nawaz