python - 在 Python 中用蛮力求解 Euler #14

Question

我试图用python暴力破解欧拉问题14 ，但没有取得多大成功。

我使用了 itertools 模块，但它太慢了。然后我找到了解决问题的公式。

有没有办法使用蛮力解决问题？

Answer 1

您可以将中间值存储在字典中并进行一种动态编程。

numbers = {1:0}
max = -1
startMax = -1
for i in range(2, 1000 000):
    n = i
    steps = 0
    while n>=i:
        if n&2 == 0:
            n = n/2
        else:
            n = 3*n + 1
        steps = steps + 1
    # n < i, hence it must already be stored in the dictionary
    steps = steps + numbers[n]
    if steps > max:
        max = steps
        startMax = i
    numbers[i] = steps
    return startMax

另一种方法可能是存储您遇到的每个号码，并始终检查您当前所在的号码是否在地图中。但我想这可能需要更多的字典查找时间：

numbers = {1:0}
max = -1
for i in range(2, 1000 000):
    if i in numbers:
        steps = numbers[i]
    else:
        n = i
        steps = 0
        found = False

        while not found:
            if n&2 == 0:
                n = n/2
            else:
                n = 3*n + 1
            if n in numbers:
                steps = numbers[n]
                found = True
            else:
                newNumbers.append(n)
        # Store all the new numbers into the dictionary
        for num in newNumbers:
            steps = steps + 1
            numbers[num] = steps
    if steps>max:
        max = steps
        startMax = i
return startMax

您可能想进行一些测试以找出哪个更好，但我的赌注是第一个。

Answer 2

pypy是“启用了优化的 python”。

在这里获取：http: //pypy.org/download.html#default-with-a-jit-compiler

要使用它，只需写pypy在你通常写的地方python。它非常兼容。主要区别在于为 python 编写的基于 C 的扩展在 pypy 中不起作用，尽管许多人正在努力解决这个问题。

---

我觉得有必要为我的答案辩护。鉴于这个非常简单的蛮力解决方案：

"Solve Project-Eueler #14"
from collections import namedtuple
Chain = namedtuple('Chain', 'length, start')


def calculate_chain(i):
    start = i
    length = 1
    while i != 1:
        length += 1
        if i & 1: # `i` is odd
            i = 3 * i + 1
        else:
            # Divide by two, efficiently.
            i = i >> 1
    return Chain(length, start)

def find_largest_chain(maxint):
    largest_chain = Chain(0, 0)
    for i in xrange(1, maxint+1):
        chain = calculate_chain(i)
        if chain > largest_chain:
            largest_chain = chain
    return largest_chain


def commandline_interface():
    from sys import argv
    maxint = int(argv[1])
    print find_largest_chain(maxint)

if __name__ == '__main__':
    commandline_interface()

python中的运行时间是23秒：

$ /usr/bin/time python 10177836.py 999999
Chain(length=525, start=837799)
22.94user 0.04system 0:23.09elapsed 99%CPU (0avgtext+0avgdata 15648maxresident)k
0inputs+0outputs (0major+1109minor)pagefaults 0swaps

在 pypy 中是 0.93 秒：

$ /usr/bin/time ~/packages/pypy-1.8/bin/pypy 10177836.py 999999
Chain(length=525, start=837799)
0.66user 0.10system 0:00.93elapsed 81%CPU (0avgtext+0avgdata 63152maxresident)k
48inputs+0outputs (1major+4194minor)pagefaults 0swaps

简单地使用 pypy 可以提高 2373% 的速度，并使用特定的算法。我看不出为什么 OP 不会用他自己的代码看到类似的改进。