6

我解决了欧拉问题 14，但我使用的程序很慢。我看看其他人做了什么，他们都想出了优雅的解决方案。我试图理解他们的代码，但没有取得多大成功。

这是我的代码（确定 Collat​​z 链长度的函数

def collatz(n):
a=1
while n!=1:
    if n%2==0:
        n=n/2
    else:
        n=3*n+1
    a+=1
return a

然后我使用了蛮力。它很慢，我知道它很弱。有人可以告诉我为什么我的代码很弱，以及如何用简单的英语改进我的代码。请记住，我是初学者，我的编程技能是基本的。

4

2 回答 2

11

与其计算从头到尾的每条可能的链，您可以保留链开始的缓存及其结果长度。例如，对于链

13 40  20  10  5  16  8  4  2  1

你可以记住以下内容：

  1. 以 13 开头的 Collat​​z 链的长度为 10
  2. 以 40 开头的 Collat​​z 链的长度为 9
  3. 以 20 开头的 Collat​​z 链的长度为 8

... 等等。

然后，一旦我们遇到一个已经在缓存中的数字，我们就可以使用这些保存的信息来停止计算链。

执行

使用 Python 中的字典将起始数字与其链长度相关联：

chain_sizes = {}
chain_sizes[13] = 10
chain_sizes[40] = 9
chain_sizes[40]   # => 9
20 in chain_sizes # => False

现在你只需要调整你的算法来使用这个字典（用值填充它以及查找中间数字）。

顺便说一句，这可以使用递归很好地表达。这里可能出现的链大小不会溢出堆栈:)

于 2012-04-09T20:02:17.497 回答
1

简而言之，因为我的英语很糟糕;-)

Forall n >= 1, C(n) = n/2     if n even,
                      3*n + 1 if n odd

可以一次计算几个连续的迭代。

以 k0位结尾的数字的第 k 次迭代：

C^k(a*2^k) = a

1以 k位结尾的数字的第 (2k) 次迭代：

C^(2k)(a*2^k + 2^k - 1) = a*3^k + 3^k - 1 = (a + 1)*3^k - 1

参照。维基百科文章的公式（法语）；另请参阅我的网站（法语）和我的 Python 包 DSPython 中的模块tnp1。

将以下代码与 Niklas B 解释的记忆技术结合起来：

#!/usr/bin/env python
# -*- coding: latin-1 -*-
from __future__ import division  # Python 3 style in Python 2
from __future__ import print_function  # Python 3 style in Python 2


def C(n):
    """Pre: n: int >= 1
    Result: int >= 1"""
    return (n//2 if n%2 == 0
            else n*3 + 1)


def Ck(n, k):
    """Pre: n: int >= 1
         k: int >= 0
    Result: int >= 1"""
    while k > 0:
        while (n%2 == 0) and k:  # n even
            n //= 2
            k -= 1

        if (n == 1) and k:
            n = 4
            k -= 1
        else:
            nb = 0
            while (n > 1) and n%2 and (k > 1):  # n odd != 1
                n //= 2
                nb += 1
                k -= 2

            if n%2 and (k == 1):
                n = (n + 1)*(3**(nb + 1)) - 2
                k -= 1
            elif nb:
                n = (n + 1)*(3**nb) - 1

    return n


def C_length(n):
    """Pre: n: int >= 1
    Result: int >= 1"""
    l = 1

    while n > 1:
        while (n > 1) and (n%2 == 0):  # n even
            n //= 2
            l += 1

        nb = 0
        while (n > 1) and n%2:  # n odd != 1
            n //= 2
            nb += 1
            l += 2
        if nb:
            n = (n + 1)*(3**nb) - 1

    return l


if __name__ == '__main__':
    for n in range(1, 51):
        print(n, ': length =', C_length(n))
于 2012-04-14T21:21:45.950 回答