欧拉计划14之记忆化搜索

题目描述

为正整数集合定义了以下迭代序列：

n → n /2 ( n是偶数)
n → 3 n + 1 ( n是奇数)

使用上面的规则并从 13 开始，我们生成以下序列：

13→40→20→10→5→16→8→4→2→1

可以看出，这个序列（从13开始到1结束）包含10项。虽然还没有被证明（Collatz 问题），但认为所有的起始数字都以 1 结束。

100 万以下的哪个起始数字产生最长的链？

注意：一旦链开始，条款就可以超过一百万。

代码演示

#include <iostream>

using namespace std;

int num[10000005];

int func(long long n) { //记忆化搜索 
    if (n == 1) return 1; //边界 
    if (n < 10000000 && num[n]) return num[n]; //判断是否计算过 
    int t;
    if (n & 1) t = func(3 * n + 1) + 1;
    else t = func(n >> 1) + 1;
    if (n < 10000000) num[n] = t; //没有越界，记忆化 
    return t;
}

int func1(long long n, int len) {
    if (n == 1) return len;
    if (n & 1) n = n * 3 + 1;
    else n >>= 1;
    return func1(n, len + 1);
}

int main() {
    int ans = -1, cnt;
    for (long long i = 1; i <= 1000000; i++) {
        //int len = func(i);
        int len = func1(i, 1);
        //cout << len << endl;
        if (len > ans) ans = len, cnt = i;
    }
    cout << cnt << '\n' << ans << endl; //837799 525
    return 0;
}