角谷猜想现状（我们对其知道多少）

角谷猜想现状（我们对其知道多少）#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

　　总部位于东京涩谷的 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; }

　　利用记忆化搜索，你能求出相应的最大峰值吗，还有更好的方法吗？欢迎评论区分享你的思路。