总部位于东京涩谷的 Bakuage Co., Ltd. 于2021年7月7日宣布，该公司将为揭秘未解数学难题 Collatz猜想的人才提供 1.20 亿日元（约为 108 万美元）奖金。
什么是Collatz猜想？
Collatz猜想是未解数学难题之一。Collatz猜想是指重复运用以下序列，最终会得到 1：从一个正整数开始，若是偶数则将其除以 2；若是奇数则将其乘 3 再加 1。这一猜想以 1937年提出这一想法的 Lothar Collatz名字命名。
它首先流传于美国，不久便传到欧洲，后来一位名叫角谷静夫的日本人又把它带到亚洲，因而人们就顺势把它叫作“角谷猜想”，也称为“冰雹猜想”，“3n 1猜想”等等。
这个数学猜想的通俗说法是这样的：
任意给定一自然数 N，如果它是偶数，就将它除以 2，如果它是奇数，则对它乘 3 再加 1，继续将它生成的自然数施行这种演算，经有限步骤后，最后结果必然是最小的自然数 1。对这个猜想，我们不妨挑一个数来试试：
若 N=10，则 18÷2=9，9×3 1=28，28÷2=14，14÷2=7，7×3 1=22，22÷2=11，11×3 1=34，34÷2=17，17×3 1=52，52÷2=26，26÷2=13，13×3 1=40，40÷2=20，20÷2=10，10÷2=5，5×3 1=16，16÷2=8，8÷2=4，4÷2=2，2÷2=1。
经过 20 步演算，最后变成了 1。
与角谷猜想相关的问题有哪些呢？
问题一：读入自然数 n，输出 n 最终到 1 的变化过程以及变化的步骤数。
#include<iostream>
using namespace std;
int n,step;
int main() {
cin>>n;
cout<<n;
while (n!=1) {
step ;
if (n%2==1) n=n*3 1;
else n=n/2;
cout<<"->"<<n;
}
cout<<endl<<"STEP="<<step;
return 0;
}
问题二：求解 1-100 以内的自然数中，哪个数的步骤数最大，哪个数的变化峰值最大？（如：上例中，18 的步骤数是 20，18 的变化峰值是 52）
#include<iostream>
using namespace std;
int n,fz,fzi,s,step,stepi;
int main() {
for (int i=2;i<=100;i ) {
n=i;
s=0;
while (n!=1) {
s ;
if (n%2==1) {
n=n*3 1;
if (n>fz) fz=n,fzi=i;
}
else n=n/2;
}
if (s>step) step=s,stepi=i;
}
cout<<stepi<<' '<<step<<endl<<fzi<<' '<<fz;
return 0;
}
通过运行，我们发现 97 的步骤数最大，有 118步；27 的峰值最大，达到 9232。虽然 27 是一个貌不惊人的自然数，但是如果按照上述方法进行运算，它的上浮下沉异常剧烈：首先，27 要经过 77步的变换到达顶峰值 9232，然后又经过 34 步到达谷底值 1。全部的变换过程需要 111步，其峰值 9232，是原有数字 27 的 341 倍多。
分析上面的代码，我们不难发现其中有一些计算是重复的，比如在计算 5 的步长时，要推到 16，计算 16 的步长；然后又要推到 8，计算 8 的步长；算完 5 继续算后面的数字 6 7 8 ... 时，还要再算 8 和 16 的步长......怎么解决这个重复计算的问题呢，我们可以采用（部分）记忆化搜索的方法，下面给出参考代码。
#include<iostream>
using namespace std;
int step,stepi;
int s[2000001];
int dfs(long long a) {
if (a==1) return 0; //边界
if (a<=2000000 && s[a]) return s[a]; //若a小于200万，且已搜索过，则直接返回
if (a%2) //若在数组存储范围内（小于200万），先存储再返回
if (a<=2000000) {s[a]=dfs(3*a 1) 1;return s[a];}
else return dfs(3*a 1) 1;
else
if (a<=2000000) {s[a]=dfs(a/2) 1;return s[a];}
else return dfs(a/2) 1;
}
int main() {
for (int i=1;i<=2000000;i ) dfs(i); //部分记忆化搜索
for (int i=1;i<=2000000;i ) //找出200万以内的最大步长
if (s[i]>step) step=s[i],stepi=i;
cout<<stepi<<' '<<step;
return 0;
}
利用记忆化搜索，你能求出相应的最大峰值吗，还有更好的方法吗？欢迎评论区分享你的思路。
