每日编码问题 210 中的问题复制如下:

数学中的 Collat​​z 序列可以定义如下。以任何正整数开头:

if n is even, the next number in the sequence is n / 2
if n is odd, the next number in the sequence is 3n + 1

推测每个这样的序列最终都会达到数字 1。测试这个猜想。

奖励:什么输入 n
我的代码(注意是不完整的):
def collatz(n):
    sequenceLength = 0
    while (n>=1):
        if (n==1):
            break # solution is found
        elif (n%2==0):
            n = n/2
            sequenceLength += 1
        else:
            n = 3*n+1
            sequenceLength += 1
    return(sequenceLength)

def longest_seq(limit):
    result = []
    for i in range(1, limit+1):
        result += [collatz(i)]
    print(result)
    return max(result)

问题:
在这种情况下,我需要测试对于所有正整数我将始终达到“1”的猜想。但是,我上面的代码假设了这一点,这意味着我可能会运行一个无限循环。

测试猜想的好/优雅方法是什么?我正在考虑缓存/数组的一些内容,以查看在 while 循环开始时是否重复了“n”的值。如果是这样,则表明存在无限循环。但是,我对语法部分有点困惑,并且不清楚我目前看到的示例。我只需要一种方法即可:
-将内容添加到缓存/等效
- 检查缓存/等效项中是否存在某些内容(这可以给我一个正确的返回或一个优雅的无效响应,我可以使用它,而不会使我的程序崩溃)

非常感谢。

最佳答案

由于每次遇到特定的数字 n_i 都会执行相同的操作,因此您知道如果遇到已经看过的数字,则会无限循环。

解决此问题的一种方法是保存您的序列。然后,您可以在每个步骤中验证您尚未遇到该号码。这是它的样子:

def collatz(n):
    sequence = []
    while (n>=1):
        if n in sequence:
            break
        else:
            sequence.append(n)
            if (n==1):
                break # solution is found
            elif (n%2==0):
                n = n/2
            else:
                n = 3*n+1
    return(sequence)

注意:如果您希望代码运行更快,因为数组具有更长的查找时间(可@@ tobias_k),则可以使用集合而不是数组。但是您将丢失序列的确切顺序。

关于python - 如何在 Python 中编写缓存函数或等效函数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/56831892/

10-12 14:28
查看更多