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

Asss-whom

use std::collections::BTreeMap;

pub fn run() -> Result<(), Box<dyn std::error::Error>> {
    let mut map = BTreeMap::new();
    for mut x in 2..1000000u32 {
        let (i, mut n) = (x, 0u32);
        while x != 1 {
            if x < i {
                n += map.get(&x).unwrap();
                break;
            } else if x % 2 == 0 {
                x /= 2;
                n += 1
            } else {
                x = (3 * x + 1) / 2;
                n += 2
            }
        }
        map.insert(i, n);
    }

    let mut max = 0u32;
    let mut num = 0u32;

    for (k, v) in map {
        if v > max {
            max = v;
            num = k;
        }
    }
    println!("num = {num}, max = {max}");
    Ok(())
}

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

TLM

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

import time
tt=time.time()
data={}
maxnum=(1,1)
data[1]=1
def getl(x):
    if x in data:
        return (data[x],x)
    if x%2==0:
        ans=getl(x//2)[0]+1
    else:
        ans=getl(3*x+1)[0]+1
    data[x]=ans
    return (ans,x)
for i in range(1,10**6+1):
    maxnum=max(maxnum,getl(i))
print(maxnum)
print(time.time()-tt)

(525, 837799)
1.4954357147216797s