l = [[i, i, 1] for i in range(1,1000000)]
def collatz(li):
for el in li:
if el[1] == 1:
li.remove(el)
elif el[1] % 2 == 0:
el[1] = el[1] / 2
el[2] += 1
elif el[1] % 2 == 1:
el[1] = 3*el[1] + 1
el[2] += 1
return li
while len(collatz(l)) >= 2:
l = collatz(l)
print l
嗨，这是 Euler Problem 14 的（部分）解决方案，用 Python 编写。
最长 Collatz 序列
问题14
为正整数集合定义以下迭代序列：
n → n/2 (n is even) n → 3n + 1 (n is odd)使用上面的规则并从 13 开始，我们生成以下序列：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1可以看出，这个序列（从 13 开始，到 1 结束）包含 10 个项。尽管尚未得到证明（Collatz 问题），但人们认为所有起始数字都以 1 结束。
一百万以下的起始数字会产生最长的链？
注意： 一旦链启动，条款允许超过一百万。
我写了部分内容，因为它并没有真正输出解决方案，因为我无法真正在整个 1 - 1000000 范围内运行它。它太慢了——上次我杀死这个进程花了 20 多分钟。我刚刚开始学习 python 和一般编程（大约 2 周），我希望了解我在效率方面犯的明显错误是什么。我用谷歌搜索了一些解决方案，甚至平均的解决方案也比我的快几个数量级。那么我在这里缺少什么？有什么文献可以避免将来犯同样的错误吗？
对萨拉的回答有一点改进
import time
start = time.time()
def collatz(n):
k = n
length = 1
nList = []
nList.append(n)
while n != 1:
if n not in dic:
n = collatzRule(n)
nList.append(n)
length += 1
else:
# we dont need the values but we do need the real length for the for-loop
nList.extend([None for _ in range(dic[n] - 1)])
length = (length - 1) + dic[n]
break
for seq in nList:
if seq not in dic:
dic[seq] = len(nList) - nList.index(seq)
return length
def collatzRule(n):
if n % 2 == 0:
return n // 2
else:
return 3 * n + 1
longestLen = 0
longestNum = 0
dic = {}
for n in range(2, 1000001):
prsntLen = collatz(n)
if prsntLen > longestLen:
longestLen = prsntLen
longestNum = n
# print(f'{n}: {prsntLen}')
print(f'The starting num is: {longestNum} with the longest chain having: {longestLen} terms.')
print(f'time taken: {time.time() - start}')
Sara 的回答很好，但还可以更有效率。 如果我们从函数返回的值是
len(seq)我稍微修改了代码，性能提升显着
def collatz(x):
count = 1
temp = x
while temp > 1:
if temp % 2 == 0:
temp = int(temp/2)
if temp in has2: # calculate temp and check if in cache
count += has2[temp]
break
else:
count += 1
else:
temp = 3*temp + 1
if temp in has2:
count += has2[temp]
break
else:
count += 1
has2[x] = count
return count
837799 has 525 elements. calculation time =1.97099995613 seconds.
与原版相比
837799 has 525 elements. calculation time =11.3389999866 seconds.使用
int问题是你使用的暴力算法效率低下。这是我对欧拉项目中问题 14 的解决方案。运行需要几秒钟。关键是您应该将以前的结果保存在字典中，这样您就不必再次计算这些结果。:
#problem 14 project euler
import time
start=time.time()
has2={}
def collatz(x):
seq=[]
seq.append(x)
temp=x
while(temp>1):
if temp%2==0:
temp=int(temp/2)
if temp in has2:
seq+=has2[temp]
break
else:
seq.append(temp)
else:
temp=3*temp+1
if temp in has2:
seq+=has2[temp]
break
else:
seq.append(temp)
has2[x]=seq
return len(seq)
num=0
greatest=0
for i in range(1000000):
c=collatz(i)
if num<c:
num=c
greatest=i
print('{0} has {1} elements. calculation time ={2} seconds.'.format(greatest,num,time.time()-start))
正如@Sara所说，您可以使用字典来保存以前的结果，然后查找它们以使程序运行得更快。但我不太明白你的结果，花了20多分钟听起来你有问题。 通过使用暴力破解，我的代码运行时间约为 16 秒。
#!/bin/python3
########################
# Collatz Conjecture #
# Written by jeb 2015 #
########################
import time
current = 0
high = 0
# While number is not one, either divide it by 2
# or multiply with 3 and add one
# Returns number of iterations
def NonRecursiveCollatz(i):
counter = 1
while i != 1:
counter = counter + 1
if i%2 == 0:
i = i / 2
else:
i = 3*i + 1
return counter
time_start = time.time()
# Test all numbers between 1 and 1.000.000
# If number returned is higher than last one, store it nd remember
# what number we used as input to the function
for i in range(1,1000000):
current = NonRecursiveCollatz(i)
if current > high:
high = current
number = i
elapsed_time = time.time() - time_start
print "Highest chain"
print high
print "From number "
print number
print "Time taken "
print elapsed_time
输出：
Highest chain
525
From number
837799
Time taken
16.730340004
from numba import njit
from time import perf_counter
@njit
def getColatzLength(n: int) -> int:
c = 1
while n != 1:
if n % 2 == 0:
n = n / 2
else:
n = n * 3 + 1
c += 1
return c
@njit
def main() -> None:
maxv = 0
for i in range(1, 1_010_001):
sequence_length = getColatzLength(i)
if maxv < sequence_length:
maxv = sequence_length
print(maxv)
s = perf_counter()
main()
print(perf_counter() - s)
# problem 14 project euler
需要 4.5 秒
//Longest Colletz Sequence
public class Problem14 {
static long getLength(long numb) {
long length = 0;
for(long i=numb; i>=1;) {
length++;
if(i==1)
break;
if(i%2==0)
i = i/2;
else
i = (3*i)+1;
}
return length;
}
static void solution(long numb) {
long number = numb;
long maxLength = getLength(number);
for(long i=numb; i>=1; i--) {
if(getLength(i)>=maxLength) {
maxLength = getLength(i);
number = i;
}
}
System.out.println("`enter code here`Length of "+number+" is : "+maxLength);
}
public static void main(String args[]) {
long begin = System.currentTimeMillis();
solution(1000000);
long end = System.currentTimeMillis();
System.out.println("Time : "+(end-begin));
}
}
output :
Length of 837799 is : 525
Time : 502