Project Euler:Problem 14

By | 2013/10/14

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n  n/2 (n is even)
n  3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

 

问题很简单,就是得到1000000里面链最长的那个数。根据题意,我写出了第一版代码:

 

maxcount = 0
maxi = 0

for i in range(1, 1000001):
	endnum = i
	count = 1
	print endnum, " : ",

	while endnum != 1:
		count += 1
		if endnum % 2 == 0:
			endnum /= 2
		else:
			endnum = endnum*3 + 1 

		#print endnum," -> ",
	print ""
	if maxcount < count :
		maxcount = count 
		maxi = i
		print "Maxcount: %d  Number: %d"%(maxcount, maxi)

print maxcount," - ",maxi

 

在运行的时候,编译器总是运行到一半就死掉了……  后来分析了下问题,发现可以将链里的数都放到一个list中,在之后的计算中如果再次遇到这个数则可以直接跳过,这样可以减少很多的重复操作,我在第一版的基础上简单的修改了下:

 

maxcount = 0
maxi = 0
templist = []

for i in range(1, 1000001):
	if i in templist:
		continue

	endnum = i
	count = 1
	print endnum, " : ",

	while endnum != 1:
		templist.append(endnum)
		count += 1

		if endnum % 2 == 0:
			endnum /= 2
		else:
			endnum = endnum*3 + 1 

		print endnum," -> ",
	print ""
	if maxcount < count :
		maxcount = count 
		maxi = i
		print "Maxcount: %d  Number: %d"%(maxcount, maxi)

print maxcount," - ",maxi
print len(templist)

 

 

 
这次运行的时候,编译器不会死了,但是运行的速度竟然比第一版的还慢…… 网上找了一下也没找到比较快的代码,待我日后再慢慢研究吧……
 

 

One thought on “Project Euler:Problem 14

Leave a Reply

Your email address will not be published. Required fields are marked *