Euler第四题

寻找一个最大的为两个3位数乘积的回文。
回文就是正着念,反着念相同的数或单词,如 9009 = 91×99。
__________________________________________________________________________________________
from time import clock
start=clock()
z=999
a=[0,0,0]
flag=False
for i in range(100000):
    a[0]=int(z/100)
    a[1]=int((z-100*a[0])/10)
    a[2]=int(z-100*a[0]-10*a[1])
    palindrome=100000*a[0]+10000*a[1]+1000*a[2]+100*a[2]+10*a[1]+a[0]
    #print(palindrome)
    product=999
    for j in range(999):
        if palindrome/product<1000 and palindrome%product==0:
            print(“the answer is {0}={1}×{2}”.format(palindrome,product,int(palindrome/product)))
            flag=True
            break
        product=product-1
    z=z-1
    if flag==True or palindrome<0: break
print(“{0:5f}s”.format(clock()-start))
_________________________________________________________________________________________

这段代码执行结果大约需要0.057S。看了一下给出的答案,代码还可以优化一下。
关键在此处:
palindrome=100000*a[0]+10000*a[1]+1000*a[2]+100*a[2]+10*a[1]+a[0]
palindrome=100001*a[0]+10010*a[1]+1100*a[2]
palindrome=11(9091*a[0]+910*a[1]+100*a[2])
经过这个变化可以知道一个因数肯定是11的倍数。因此不需要在循环中一个一个试了。一个因数为11*j,并且j<91,因为当j大于等于91时,11*j>1000,不符合题目要求。

_________________________________________________________________________________________
优化代码:
    j=90
    while j>0:
        product=j*11
        if palindrome/product<1000 and palindrome%product==0:
            print(product)
            print(“the answer is {0}={1}×{2}”.format(palindrome,product,int(palindrome/product)))
            flag=True
            break
        j=j-1
_________________________________________________________________________________________
这段代码执行时间只需要0.0065s左右。

发表评论

无觅相关文章插件,快速提升流量