如何让这段代码在 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。
我如何让它为
maxInt=9999
返回 99000099 30 岁以下
请您参考如下方法:
x>=y
,所以 99*91
和 91*99
不会单独测试发现x
找到的所有回文肯定小于“当前”的)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