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

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
   

复制代码

Asss-whom

1. use std::collections::BTreeMap;
   
2. 
   
3. pub fn run() -> Result<(), Box<dyn std::error::Error>> {
   
4.     let mut map = BTreeMap::new();
   
5.     for mut x in 2..1000000u32 {
   
6.         let (i, mut n) = (x, 0u32);
   
7.         while x != 1 {
   
8.             if x < i {
   
9.                 n += map.get(&x).unwrap();
   
10.                 break;
    
11.             } else if x % 2 == 0 {
    
12.                 x /= 2;
    
13.                 n += 1
    
14.             } else {
    
15.                 x = (3 * x + 1) / 2;
    
16.                 n += 2
    
17.             }
    
18.         }
    
19.         map.insert(i, n);
    
20.     }
    
21. 
    
22.     let mut max = 0u32;
    
23.     let mut num = 0u32;
    
24. 
    
25.     for (k, v) in map {
    
26.         if v > max {
    
27.             max = v;
    
28.             num = k;
    
29.         }
    
30.     }
    
31.     println!("num = {num}, max = {max}");
    
32.     Ok(())
    
33. }
    

复制代码

[Project Euler 14]
num = 837799, max = 524
[Task finished in 0.1754473s]
不知道链长为啥不一样……

TLM

python版本，通过字典进行加速。注意中间值也要写入字典

1. import time
   
2. tt=time.time()
   
3. data={}
   
4. maxnum=(1,1)
   
5. data[1]=1
   
6. def getl(x):
   
7.     if x in data:
   
8.         return (data[x],x)
   
9.     if x%2==0:
   
10.         ans=getl(x//2)[0]+1
    
11.     else:
    
12.         ans=getl(3*x+1)[0]+1
    
13.     data[x]=ans
    
14.     return (ans,x)
    
15. for i in range(1,10**6+1):
    
16.     maxnum=max(maxnum,getl(i))
    
17. print(maxnum)
    
18. print(time.time()-tt)

复制代码

(525, 837799)
1.4954357147216797s