题目14：找出以100万以下的数字开始的最长序列

阿bang

1. import time
   
2. 
   
3. 
   
4. start = time.time()
   
5. cntlist = []
   
6. for i in range(2, 1000000):
   
7.     numlist = [i]
   
8.     num = i
   
9.     while num != 1:
   
10.         if num % 2 == 0:
    
11.             num /= 2
    
12.         else:
    
13.             num = num * 3 + 1
    
14.         numlist.append(num)
    
15.         if num in numlist:
    
16. 
    
17.     cntlist.append(len(numlist))
    
18. print max(cntlist)
    
19. print time.time() - start

复制代码

十分初级的版本。考虑优化点有2：

1、类似素数筛选法：已经算过的数的2的n次方倍数的数，计数直接+n，结束。
2、维护一个数的序列的表，如果出现某个数在列表内，则计数直接加上列表后面的长度，结束。

阿bang

1. (837799, 524)
   
2. 2.58100008965

复制代码

优化了一下，速度提高了不少。不过最后的字典里取结果可能慢了。还有优化的空间。代码如下：

1. import time
   
2. 
   
3. 
   
4. def longestCollatz(n=1000001):
   
5.     start = time.time()
   
6.     collatzdict = {}  #维护一个统一的collatz的统计字典，初始为[2：2]
   
7.     numlist = [True] * (n - 1) #默认所有数都未被‘挖掉’, 从2 开始
   
8.     for i in range(2, n):
   
9.         count = 0
   
10.         num = i
    
11.         if numlist[i - 2] == True: #若一个数未被挖掉，计算数量
    
12.             while num != 1:
    
13.                 num = num * 3 + 1 if num % 2 else num / 2
    
14.                 count += 1
    
15.                 if num in collatzdict: #若计算到某个步骤，产生了已经出现过的数，则直接加上该数的计数，计数结束
    
16.                     count += collatzdict[num]
    
17.                     break
    
18.             collatzdict[i] = count
    
19.             numlist[i - 2] = False
    
20.             if i < n / 2:             #以i为基数，挖掉i的2的j次方倍的所有的数
    
21.                 j = 1
    
22.                 while i * pow(2, j) < n:
    
23.                     if numlist[i] == True:
    
24.                         numlist[i * pow(2, j) - 2] = False #挖掉第i个数2的j次方倍的数
    
25.                         collatzdict[i * pow(2, j)] = collatzdict[i] + j
    
26.                     j += 1
    
27.     print list(sorted(collatzdict.items(), key=lambda x:x[1], reverse=True))[0]
    
28.     print time.time() - start
    
29. 
    
30. 
    
31. if __name__ == '__main__':
    
32.     longestCollatz()

复制代码

阿bang

阿bang 发表于 2018-4-4 12:43
优化了一下，速度提高了不少。不过最后的字典里取结果可能慢了。还有优化的空间。代码如下：

1. import time
   
2. 
   
3. 
   
4. def longestCollatz(n=1000001):
   
5.     start = time.time()
   
6.     collatzdict = {}  #维护一个统一的collatz的统计字典，初始为[2：2]
   
7.     numlist = [True] * (n - 1) #默认所有数都未被‘挖掉’, 从2 开始
   
8.     maxnum = 2
   
9.     maxcnt = 2
   
10.     for i in range(2, n):
    
11.         count = 0
    
12.         num = i
    
13.         if numlist[i - 2] == True: #若一个数未被挖掉，计算数量
    
14.             while num != 1:
    
15.                 num = num * 3 + 1 if num % 2 else num / 2
    
16.                 count += 1
    
17.                 if num in collatzdict: #若计算到某个步骤，产生了已经出现过的数，则直接加上该数的计数，计数结束
    
18.                     count += collatzdict[num]
    
19.                     break
    
20.             collatzdict[i] = count
    
21.             if count > maxcnt:
    
22.                 maxcnt = count
    
23.                 maxnum = i
    
24.             numlist[i - 2] = False
    
25.             if i < n / 2:             #以i为基数，挖掉i的2的j次方倍的所有的数
    
26.                 j = 1
    
27.                 while i * pow(2, j) < n:
    
28.                     if numlist[i] == True:
    
29.                         numlist[i * pow(2, j) - 2] = False #挖掉第i个数2的j次方倍的数
    
30.                         collatzdict[i * pow(2, j)] = collatzdict[i] + j
    
31.                         if collatzdict[i * pow(2, j)] > maxcnt:
    
32.                             maxcnt = collatzdict[i * pow(2, j)]
    
33.                             maxnum = i * pow(2, j)
    
34.                     j += 1
    
35. 
    
36. 
    
37.     # print list(sorted(collatzdict.items(), key=lambda x:x[1], reverse=True))[0]
    
38.     print maxnum, maxcnt
    
39.     print time.time() - start
    
40. 
    
41. 
    
42. if __name__ == '__main__':
    
43.     longestCollatz()

复制代码

再改了一下，只需要找最大的，不需要最后排序字典的话，会快一点

1. 837799 524
   
2. 1.69199991226

复制代码