(这是 Project Euler Problem 14)
我正在尝试通过使用 Itertools 来丰富我的 Python 技能。
我想从 Python 的 itertools 中的生成器中获取设定迭代次数 (1,000,000) 中的最大返回值的索引。
该函数有效,但我无法弄清楚如何有效地获得最大值而不将其存储在一个巨大的一百万长列表中,我认为这对此几乎没有效率。有没有一种聪明的方法呢? (编辑:也许这是最简单的方法?)
当前的代码是当链达到 100 时停止,这是错误的。
#Project Euler Problem 14
#Which starting number, under one million, produces the longest chain?
import itertools
def length():
x=1
while True:
l=0
c=x #Create the running integer.
while c>1:
if c%2==0:
#Number is even, divide it by two.
c=c/2
l+=1
else:
#Number is odd, multiply by three and add one.
c=3*c+1
l+=1
yield l+1 #Add the final one as well and show the chain length.
x+=1 #Increment
print list(itertools.takewhile(lambda x:x<100,length()))
最佳答案
我按如下方式解决了这个问题:
import functools
def euler_014(max_=1000000):
longest = max_len = None
for n in range(1, max_):
length = len_collatz(n)
if max_len is None or length > max_len:
max_len, longest = length, n
return longest
def memoize(f):
cache = {}
@functools.wraps(f)
def func(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return func
@memoize
def len_collatz(n):
if n == 1:
return 1
if n % 2:
n = (n * 3) + 1
else:
n //= 2
return 1 + len_collatz(n)
这里 memoize
通过存储 len_collatz
的先前结果使事情变得更加高效,len_collatz
告诉您来自 n 的序列的长度
到 1
(没有实际生成整个序列的列表),而 euler_014
只需跟踪最长长度和相关的 值n
。请注意,它不会保留所有结果 - 只保留迄今为止最长序列的长度以及生成该序列的 n
值。
关于python - 在Python Itertools中获取一组迭代次数中最大值的索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23619512/