欧拉计划：两个三位数的最大回文积

Question

我得到580085，为什么不对？还有另一种检查数字是否为回文的方法吗？

def reverse(str, aux=''):
    count = len(str)
    while count > 0:
        aux += str[count-1]
        count -= 1
    return aux

def palindrome(num):
    j = str(num)
    if j == reverse(j):
        return 1
    else:
        return 0

i = 999
found = 0
while i > 99 and not found:
    j = 999
    while j > 99 and not found:
        if palindrome(i * j):
            found = 1
            print(i * j)
        else:
            j -= 1
    if not found:
        i -= 1

我的 post 主要是代码，但我没有其他要说的。

Answer 1

新代码：

def reverse(str, aux=''):
    count = len(str)
    while count > 0:
        aux += str[count-1]
        count -= 1
    return aux

def palindrome(num):
    j = str(num)
    if j == reverse(j):
        return 1
    else:
        return 0

i = 999
max = 0
while i > 99:
    j = 999
    while j > 99:
        num = i * j
        if palindrome(num):
            if num > max:
                max = num
                print(max)
        j -= 1
    i -= 1

Answer 2

花了一些时间研究了这个问题。我尝试采用相反的方法（从回文数字开始，找到它们的分隔符（如果有的话））。在 Win10.

上使用 Py354

code.py:

import time
from math import sqrt


def reverse(str, aux=''):
    count = len(str)
    while count > 0:
        aux += str[count-1]
        count -= 1
    return aux


def palindrome(num):
    j = str(num)
    if j == reverse(j):
        return 1
    else:
        return 0


def question_makhfi_0():
    ret = 0
    i = 999
    found = 0
    while i > 99 and not found:
        j = 999
        while j > 99 and not found:
            if palindrome(i * j):
                found = 1
                ret = i * j
            else:
                j -= 1
        if not found:
            i -= 1
    return ret, i, j


def answer_makhfi_0():
    i = 999
    _max = 0
    while i > 99:
        j = 999
        while j > 99:
            num = i * j
            if palindrome(num):
                if num > _max:
                    _max = num
                    factor0, factor1 = i, j
            j -= 1
        i -= 1
    return _max, factor0, factor1


"""
def answer_makhfi__0_improved_0():
    i = j = 999
    prod = i * j
    step = 0
    while prod > 100000:
        if step % 2:
            i -= 1
        else:
            j -= 1
        prod = i * j
        prod_str = str(prod)
        if prod_str == prod_str[::-1]:
            return prod
        step += 1
"""


def answer_cfati_0():
    pal = 999999
    while pal >= 900009:
        if pal % 10 == 9:
            pal_str = str(pal)
            if pal_str == pal_str[::-1]:
                pal_sqrt = sqrt(pal)
                for factor0 in range(101, int(pal_sqrt) + 1):
                    if pal % factor0 == 0:
                        factor1 = int(pal / factor0)
                        if 100 <= factor1 <= 999:
                            return pal, factor0, factor1
        pal -= 10
    #return pal


def time_func(f, *args):
    t0 = time.time()
    res = f(*args)
    t1 = time.time()
    return t1 - t0, res


if __name__ == "__main__":
    for func in [question_makhfi_0, answer_makhfi_0, answer_cfati_0]:
        print("\nStarting: {}".format(func.__name__))
        #print(func.__name__)
        res = time_func(func)
        print("  Time: {:.6f}\n  Result: {}".format(*res))

备注:

将您的代码转换为函数（进行所有必要的调整，并省略涉及性能的所有内容）
添加了一个额外的函数来测量执行时间
answer_makhfi_0:
- 将 max 替换为 _max 以避免隐藏内置名称
- 在末尾添加了一个 return 语句（无论如何，效率非常低）
answer_cfati_0:
- 代码假定在 [900009, 999999] 范围内有一个回文数，可以表示为 2（3 位）数字乘积。可以公平地假设（测试支持这一点）。但是如果针对防弹代码，这种形式不行，我将不得不稍微调整一下（这将是性能方面的损失）
- 它使用各种mathematical/logical "shortcuts"来避免无用的计算（我认为代码也可以在那个方向上改进）。

输出:

"e\Work\Dev\Whosebug\q47999634>"e:\Work\Dev\VEnvs\py35x64_test\Scripts\python.exe" code.py

Starting: question_makhfi_0
  Time: 0.008551
  Result: (580085, 995, 583)

Starting: answer_makhfi_0
  Time: 1.457818
  Result: (906609, 993, 913)

Starting: answer_cfati_0
  Time: 0.012599
  Result: (906609, 913, 993)

根据输出，原始和新代码之间的差异（对于one运行，随时间变化）：

最大回文数：906609 - 906609
计算时间：1.457818 - 0.012599

@EDIT0:

感谢您的评论，我在我的代码中发现了一个（严重的）逻辑错误（和一些小错误）：它是 returning 998899 (781 * 1279)。修复后，性能下降了一个数量级，但还是很快
修改函数以 return 因素（用于检查）

欧拉计划：两个三位数的最大回文积

Project Euler: Largest palindrome product of two 3-digit number

python

eulers-number