题目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

复制代码

najin

1. The answer is 837799
   
2. Its length is 525
   
3. Time is 136 ms

复制代码

jerry-R

0.80s在此哦~~~~
#include <iostream>
using namespace std;

int main()
{
        int longest = 0;
        int terms = 0;
        int i;
        unsigned long j;

        for (i = 1; i <= 1000000; i++)
        {
                j = i;
                int this_terms = 1;

                while (j != 1)
                {
                        this_terms++;

                        if (this_terms > terms)
                        {
                                terms = this_terms;
                                longest = i;
                        }

                        if (j % 2 == 0)
                        {
                                j = j / 2;
                        }
                        else
                        {
                                j = 3 * j + 1;
                        }
                }
        }

        cout << longest << endl << terms << endl;
        system("pause");
        return 0;
}

zzzgod

1. #include <iostream>
   
2. #include <cstring>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.         bool dest[1000001];
   
9.         long long maxtime=0,maxnum=0,time,num;
   
10.         memset(dest,0,1000001);
    
11.         dest[1]=1;
    
12.         for(int i=1;i<=1000000;++i)
    
13.         {
    
14.                 if(dest[i]==1)
    
15.                         continue;
    
16.                 num=i;
    
17.                 time=1;
    
18.                 while(num!=1)
    
19.                 {
    
20.                         ++time;
    
21.                         if(num<=1000000)
    
22.                                 dest[num]=1;
    
23.                         if(num%2==0)
    
24.                         {
    
25.                                 num/=2;
    
26.                         }
    
27.                         else
    
28.                         {
    
29.                                 num=num*3+1;
    
30.                         }
    
31.                 }
    
32.                 if(time>maxtime)
    
33.                 {
    
34.                         maxtime=time;
    
35.                         maxnum=i;
    
36.                 }
    
37.         }
    
38.         cout<<"最长的序列数是："<<maxnum<<' '<<"总共有："<<maxtime<<"个元素";
    
39. }

复制代码

不到1秒

山有扶苏啊

1. def Collatz(n):
   
2.     t = 0
   
3.     while n != 1:
   
4.         if n%2 == 0:
   
5.             n = n/2
   
6.             t += 1
   
7.         else:
   
8.             n = 3*n + 1
   
9.             t += 1
   
10.     return t
    
11. 
    
12. result = {}
    
13. for i in range(1, 1000000):
    
14.     result[i] = Collatz(i)
    
15. 
    
16. max(result, key = result.get)
    

复制代码

837799

k往事如烟k

1. count1 = 1
   
2. num1 = 1
   
3. for n in range(1, 1000001):
   
4.     count = 1
   
5.     num = n
   
6.     while 1:
   
7.         if num % 2 == 0:
   
8.             num //= 2
   
9.             count += 1
   
10.         else:
    
11.             num = num * 3 + 1
    
12.             count += 1
    
13.         if num == 1:
    
14.             break
    
15.     if count >= count1:
    
16.         count1 = count
    
17.         num1 = n
    
18. print(num1)

复制代码

837799

王小召

最大值：525
对应数值：837799
总用时：25.376614736835744

1. import time
   
2. 
   
3. 
   
4. def get_longer(num):
   
5.     if num <= 1000000:
   
6.         counter = 1
   
7.         while num != 1:
   
8.             if num % 2:
   
9.                 num = num*3 + 1
   
10.             else:
    
11.                 num = num/2
    
12.             counter += 1
    
13.         return counter
    
14.     else:
    
15.         raise ValueError
    
16. 
    
17. t1 = time.clock()
    
18. num_list = [get_longer(i) for i in range(2, 1000000)]
    
19. print("最大值：{} \n对应数值：{} \n总用时：{}".format(max(num_list), num_list.index(max(num_list))+2, time.clock() - t1))

复制代码

cwhsmile

1. import time
   
2. import math
   
3. import functools
   
4. 
   
5. def test1():
   
6.     max_len = 0
   
7.     i = 1000001
   
8.    
   
9.     while i > 1:
   
10.         num = i
    
11.         count = 1
    
12.         while num != 1:
    
13.             if num%2 == 0:
    
14.                 num = num//2
    
15.             else:
    
16.                 num = 3*num + 1
    
17.             count += 1
    
18.         if max_len < count:
    
19.             max_len = count
    
20.             max_num = i
    
21.         i -= 2
    
22.     return max_len,max_num
    
23. 
    
24. start = time.perf_counter()
    
25. 
    
26. print(test1())
    
27. end = time.perf_counter()
    
28. print(end-start)
    

复制代码

永恒的蓝色梦想

C++ 12ms

1. #include<iostream>
   
2. 
   
3. constexpr unsigned int MAX = 1000000;
   
4. unsigned short cache[MAX] = { 0, 1 };
   
5. 
   
6. 
   
7. 
   
8. unsigned short Collatz(unsigned int num)noexcept {
   
9.     if (num < MAX) {
   
10.         if (cache[num]) {
    
11.             return cache[num];
    
12.         }
    
13. 
    
14.         if (num & 1) {
    
15.             return cache[num] = Collatz((num >> 1) + num + 1) + 2;
    
16.         }
    
17. 
    
18.         return cache[num] = Collatz(num >> 1) + 1;
    
19.     }
    
20. 
    
21.     if (num & 1) {
    
22.         return Collatz((num >> 1) + num + 1) + 2;
    
23.     }
    
24. 
    
25.     return Collatz(num >> 1) + 1;
    
26. }
    
27. 
    
28. 
    
29. 
    
30. int main() {
    
31.     using namespace std;
    
32.     ios::sync_with_stdio(false);
    
33. 
    
34.     unsigned int num, max_num = 0;
    
35.     unsigned short len, max_len = 0;
    
36. 
    
37. 
    
38.     for (num = 1; num < MAX; num++) {
    
39.         if (!cache[num]) {
    
40.             if (num & 1) {
    
41.                 len = Collatz((num >> 1) + num + 1) + 2;
    
42.             }
    
43.             else {
    
44.                 len = Collatz(num >> 1) + 1;
    
45.             }
    
46. 
    
47.             if (len > max_len) {
    
48.                 max_len = len;
    
49.                 max_num = num;
    
50.             }
    
51.         }
    
52.     }
    
53. 
    
54. 
    
55.     cout << max_num << endl;
    
56.     return 0;
    
57. }

复制代码

leon0149

525 837799
0.788s

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX 1000
   
5. #define NUM 1000000
   
6. 
   
7. long long odd(long long);
   
8. long long even(long long);
   
9. void init(long long *);
   
10. void Insert(long long *, long long);
    
11. 
    
12. void init(long long* array){
    
13.     array[0] = 0;
    
14. }
    
15. 
    
16. void Insert(long long* array, long long e){
    
17.     if (array[0] == MAX)
    
18.         exit(EXIT_FAILURE);
    
19.     array[++array[0]] = e;
    
20. }
    
21. 
    
22. void execute(long long *array, long long e){
    
23.     long long temp = e;
    
24.     Insert(array, temp);
    
25.     while (temp != 1) {
    
26.         if (temp % 2 != 0) {
    
27.             temp = odd(temp);
    
28.             Insert(array, temp);
    
29.         }
    
30.         if (temp % 2 == 0) {
    
31.             temp = even(temp);
    
32.             Insert(array, temp);
    
33.         }
    
34.     }
    
35. }
    
36. 
    
37. long long odd(long long num){
    
38.     return 3 * num + 1;
    
39. }
    
40. 
    
41. long long even(long long num){
    
42.     return num / 2;
    
43. }
    
44. 
    
45. int main(void)
    
46. {
    
47.     int max = 0;
    
48.     int maxNum = 0;
    
49.     int temp;
    
50.     long long array[MAX] = {0};
    
51.     for (int i = NUM - 1; i > 1; i-=2) {
    
52.         init(array);
    
53.         execute(array, i);
    
54.         temp = (int)array[0];
    
55.         if (max < temp){
    
56.             maxNum = i;
    
57.             max = temp;
    
58.         }
    
59.     }
    
60. 
    
61.     printf("最大链长: %d, 数字: %d\n", max, maxNum);
    
62.    
    
63.     return 0;
    
64. }

复制代码

数据小随从

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. 
   
5. void main()
   
6. {
   
7.         int i, k;//定义一个整数变量，从1遍历到一百万
   
8.         int t;
   
9.         int n = 1;
   
10.         int max = 1;
    
11.         for (i = 2; i <= 5; i++)
    
12.         {
    
13.                 t = i;
    
14.                 n = 1;
    
15.                 while (t != 1)
    
16.                 {
    
17.                         if (t % 2 == 0)
    
18.                         {
    
19.                                 t = t / 2;
    
20.                                 n++;
    
21.                         }
    
22.                         else
    
23.                         {
    
24.                                 t = (t * 3) + 1;
    
25.                                 n++;
    
26.                         }
    
27.                         if (t == 1)
    
28.                                 if (n > max)
    
29.                                 {
    
30.                                         max = n;
    
31.                                         k = i;
    
32.                                 }
    
33.                 }
    
34.         }
    
35.         printf("%d,%d\n", max, k);
    
36. 
    
37. 
    
38. 
    
39.         system("pause");
    
40. }

复制代码

有马_冬巳

1. '''以下迭代序列定义在整数集合上：
   
2. n → n/2 (当 n 是偶数时)
   
3. n → 3n + 1 (当 n 是奇数时)
   
4. 应用以上规则，并且以数字 13 开始，我们得到以下序列：
   
5. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
   
6. 可以看出这个以 13 开始以 1 结束的序列包含 10 个项。虽然还没有被证明（Collatz 问题），但是人们认为在这个规则下，以任何数字开始都会以 1 结束。
   
7. 以哪个不超过 100 万的数字开始，能给得到最长的序列？
   
8. 注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。'''
   
9. 
   
10. def longestsequence(num_of_sequence):
    
11.     number = 1
    
12.     longest = 1
    
13.     memory = {}
    
14.     while number <= num_of_sequence:
    
15.         #print("这是%d的序列:" %number)
    
16.         temp = 1
    
17.         lonumber = number
    
18.         while True:
    
19.             if lonumber == 1:
    
20.                 #print(lonumber)
    
21.                 break
    
22.             elif lonumber % 2 == 0:
    
23.                 #print(lonumber)
    
24.                 lonumber = int(lonumber / 2)
    
25.                 temp += 1
    
26.                 if memory.__contains__(lonumber):
    
27.                     temp += memory[lonumber] - 1
    
28.                     break
    
29.             elif lonumber % 2 == 1:
    
30.                 #print(lonumber)
    
31.                 lonumber = 3*lonumber + 1
    
32.                 temp += 1
    
33.                 if memory.__contains__(lonumber):
    
34.                     temp += memory[lonumber] - 1
    
35.                     break
    
36.         if temp > longest:
    
37.             longest = temp
    
38.             longestnumber = number
    
39.         memory[number] = temp
    
40.         number += 1
    
41.         #print("--------")
    
42. 
    
43.     print("在不超过%d的数字中，能得到最长序列的数字是%d" %(num_of_sequence,longestnumber))
    
44.     print("该数字序列量为： %d" %longest)
    
45.     #print(memory)
    
46. 
    
47. start_longestsequence = time.time()
    
48. longestsequence(1000000)
    
49. time_longestsequence = time.time() - start_longestsequence
    
50. print("%f秒" %time_longestsequence)
    

复制代码

在不超过1000000的数字中，能得到最长序列的数字是837799
该数字序列量为： 525
2.077740秒

做一个字典去存储已经计算过的序列，之后再遇到那一段同样的序列就可以直接加上已储存的值，这个方法把整个程序从33秒提升到2秒

gonorth

def f():
    record = []
    for n in range(13,14):
        count = 1
        while  1 :
            if n % 2 == 0:
                n = n // 2

                count += 1
            if n % 2 != 0 and n > 1:
                n = 3 * n + 1
                count += 1
            if n == 1:
                count
                #print (count)
                break
        record.append(count)
        count = 1
    return max(record)




print (f())

卢本伟牛逼

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. static int flag;//计数器
   
5. 
   
6. int Collatz2(long long int value){//2、非递归
   
7.         int count = 0;
   
8.         while(value > 1){
   
9.                 flag++;
   
10.                 value = (value%2)?value * 3 + 1: value / 2;
    
11.                 count += 1;
    
12.         }
    
13.         return count + 1;
    
14. }
    
15. 
    
16. int main(void)
    
17. {
    
18.         int i;
    
19.         int max_Collatz_num;
    
20.         int max;
    
21.         int temp;
    
22. 
    
23.         for(i=1;i<1000000;i++){
    
24.                 temp = Collatz2(i);
    
25.                 if (temp > max){
    
26.                         max = temp;
    
27.                         max_Collatz_num = i;
    
28.                 }
    
29.         }
    
30. 
    
31.         printf("max_Collatz_num = %d, count = %d\n", max_Collatz_num, Collatz2(max_Collatz_num));
    
32.         printf("flag = %d\n", flag);
    
33. 
    
34.         return 0;
    
35. }
    
36. //max_Collatz_num = 837799, count = 525
    
37. //flag = 131434796
    

复制代码

ft215378

FlySelf 发表于 2017-2-7 11:24
执行结果：
[837799, 525]
程序执行了3.018928s。

棒

番杰

1. #include<stdio.h>
   
2. 
   
3. #define MAX  1000000
   
4. 
   
5. typedef unsigned int   UINT;
   
6. int len = 0;
   
7. 
   
8. int Odd_or_Even(UINT);
   
9. 
   
10. int main(void)
    
11. {
    
12.         unsigned int Max_len = 0,Max_num = 0;
    
13.        
    
14.         for(int i = 1;i < max;i++)
    
15.         {
    
16.                 len = 0;
    
17.                 Odd_or_Even(i);
    
18.                 if(Max_len < len )
    
19.                 {
    
20.                         Max_len = len;
    
21.                         Max_num = i;
    
22.                 }
    
23.         }
    
24.        
    
25.         printf("%d,%d",Max_len,Max_num);
    
26.        
    
27.         return 0;
    
28. }
    
29. 
    
30. int Odd_or_Even(UINT num)
    
31. {
    
32.         len ++;       
    
33.        
    
34.         if(num == 1)
    
35.                 return 1;
    
36.         else
    
37.         {
    
38.                 if(num % 2 ==0)
    
39.                         Odd_or_Even((num / 2));
    
40.                 else
    
41.                         Odd_or_Even((num * 3 + 1));
    
42.         }
    
43.        
    
44.         return 0;
    
45. }

复制代码

guosl

1. /*
   
2. 答案：837799
   
3. 耗时：0.411748秒（单核）
   
4.       0.0373096秒（八核）
   
5. */
   
6. #include <iostream>
   
7. #include <omp.h>
   
8. using namespace std;
   
9. 
   
10. const int N = 1000000;
    
11. 
    
12. int main(void)
    
13. {
    
14.   volatile int nMaxLen = 0, nVal = 0;
    
15. #pragma omp parallel for shared(nMaxLen,nVal) schedule(dynamic,16)
    
16.   for (int i = 1; i <= N; ++i)
    
17.   {
    
18.     int nStep = 1;
    
19.     long long l = i;
    
20.     while (l != 1LL)
    
21.     {
    
22.       if (l % 2LL == 0)
    
23.         l = l >> 1;
    
24.       else
    
25.         l = 3LL * l + 1LL;
    
26.       ++nStep;
    
27.     }
    
28.     if (nStep > nMaxLen)
    
29.     {
    
30. #pragma omp critical
    
31.       {
    
32.         nMaxLen = nStep;
    
33.         nVal = i;
    
34.       }
    
35.     }
    
36.   }
    
37.   cout << nVal << endl;
    
38.   return 0;
    
39. }

复制代码

jerryxjr1220

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "time"
   
6. )
   
7. 
   
8. //题目14：
   
9. //
   
10. //以下迭代序列定义在整数集合上：
    
11. //
    
12. //n → n/2 (当 n 是偶数时)
    
13. //n → 3n + 1 (当 n 是奇数时)
    
14. //
    
15. //应用以上规则，并且以数字 13 开始，我们得到以下序列：
    
16. //
    
17. //13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
    
18. //
    
19. //可以看出这个以 13 开始以 1 结束的序列包含 10 个项。虽然还没有被证明（Collatz 问题），但是人们认为在这个规则下，以任何数字开始都会以 1 结束。
    
20. //
    
21. //以哪个不超过 100 万的数字开始，能给得到最长的序列？
    
22. //
    
23. //注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。
    
24. 
    
25. var n = map[int64]int64{
    
26.         1: 1,
    
27.         2: 2,
    
28. }
    
29. 
    
30. func If(b bool, vt int64, vf int64) int64 {
    
31.         if b == true {
    
32.                 return vt
    
33.         } else {
    
34.                 return vf
    
35.         }
    
36. }
    
37. 
    
38. func loop(a int64) int64 {
    
39.         t := a
    
40.         var c int64 = 0
    
41.         for n[t] == 0 {
    
42.                 t = If(t%2 == 0, t/2, t*3+1)
    
43.                 c++
    
44.         }
    
45.         n[a] = n[t] + c
    
46.         t = If(a%2 == 0, a/2, a*3+1)
    
47.         p := a
    
48.         for n[t] == 0 {
    
49.                 n[t] = n[p] - 1
    
50.                 p = t
    
51.                 t = If(a%2 == 0, a/2, a*3+1)
    
52.         }
    
53.         return n[a]
    
54. }
    
55. 
    
56. func main() {
    
57.         t := time.Now()
    
58.         var i int64
    
59.         for i = 3; i < 1000000; i++ {
    
60.                 _ = loop(i)
    
61.         }
    
62.         var max = map[string]int64{
    
63.                 "key":   1,
    
64.                 "value": 1,
    
65.         }
    
66.         for key, value := range n {
    
67.                 if value > max["value"] {
    
68.                         max["value"] = value
    
69.                         max["key"] = key
    
70.                 }
    
71.         }
    
72.         fmt.Println(max)
    
73.         tt := time.Now()
    
74.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
75. }
    

复制代码

输出：

1. map[key:837799 value:525]
   
2. 耗时： 309 ms
   

复制代码