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

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