时间戳

首页 > 解决方案 > 如何在 Python 中编写缓存函数或等效函数？

python - 如何在 Python 中编写缓存函数或等效函数？

问题描述

来自 Daily Coding Problem 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 <= 1000000 给出最长的序列？

我的代码（注意它不完整）：

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”的猜想。但是，我上面的代码假设了这一点，这意味着我可能会运行一个无限循环。

什么是测试猜想的好/优雅的方法？我正在考虑缓存/数组的一些内容，以查看“n”的值是否在 while 循环的开头重复。如果是这样，它表明一个无限循环。但是，我在语法部分有点卡住了，到目前为止我看到的例子还不清楚。我只需要一种方法： - 将东西添加到缓存/等效项 - 检查缓存/等效项中是否存在某些东西（这可以给我一个正确的返回或我可以使用的优雅的无效响应，而不会崩溃我的程序）

非常感谢。

标签： python

解决方案

因为每次遇到一个特定的数字 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）。但是您将丢失序列的确切顺序。

推荐阅读