如何优化python序列中的Collatz序列?

Question

Collatz序列规则如下:

• 如果n =奇数:n = 3n + 1
• n =偶数:n = n/2

我是一个具有python基本水平的学生，需要最小化我检查的数字数量，以找到小于100的最长序列。我需要输出序列的起始项。偶数和5的倍数都可以是答案(如果你看到的答案小于20，答案是18)，我不确定该选什么。

下面的代码可以工作，但是检查100个数字:

highest = 0
highest_num = 0


def Collatz(num, highest, highest_num):
    iterations = 0
    
    while num!=1:
        
        if num%2 == 0:
            num//=2
            
        else:
            num = 3*num + 1
        
        iterations += 1
        
    
    if iterations > highest:
        highest = iterations
        highest_num = i
        print(highest_num)
        
    return highest, highest_num
    
    
    
   
   
for i in range(1, 101, 1):
    result = Collatz(i, highest, highest_num)
    highest = result[0]
    highest_num = result[1]

p。答案是97

Answer 1

您可以将先前计算的数字的结果保存为一些字典，然后在到达其中一些数字时使用它。下面是示例代码:

cache = {}
max_iter = 0
max_iter_num = 0
def collatz(num):
    global cache
    global max_iter
    global max_iter_num
    
    iterations = 0
    n = num
    numbers = []
    while n > 1:
        numbers.append(n)
        if n%2 == 0:
            n //= 2
        
        else:
            n = 3*n + 1
            
        iterations += 1
        
        if n in cache.keys():
            iterations += cache[n]
            break
        
    for i, n in enumerate(numbers):
        cache[n] = iterations - i
    
    if iterations > max_iter:
        max_iter = iterations
        max_iter_num = num
    
for i in range(1, 101):
    collatz(i)

时间比较:

• code from question:

626 µs ± 8.08 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

我的代码:

67.2 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)