如何让这段代码在 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*9191*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 
    


    评论关闭
    IT干货网

    微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!