记忆化:就是将中间的运算结果保存起来,避免多次计算
#include<bits/stdc++.h>
using namespace std;
const int32_t MAX_N = 1e6;
const int32_t KEEP_N = 5*1e7;
int32_t keep[KEEP_N + 5];
int32_t GetChainLength(int64_t x)
{
int32_t ans = 0;
if (x == 1) return 1;
if (x <= KEEP_N && keep[x] != 0) return keep[x];
if (x%1 == 1)
{
ans = GetChainLength(3 * x + 1) + 1;
}
else
{
ans = GetChainLength(x >> 1) + 1;
}
if (x <= KEEP_N) keep[x] = ans;
return ans;
}
int main()
{
int32_t num = 1;
for (int32_t i=2; i <= MAX_N; i++)
{
if (GetChainLength(i) > GetChainLength(num)) num = i;
}
printf("%d 的长度为 %d
",num,GetChainLength(num));
return 0;
}