3038 3n+1问题——3127 3n+1问题 2
原题：https://codevs.cn/problem/3038/（T3038，小数据版本）
原题：https://codevs.cn/problem/3127/（T3127，大数据版本）
题目描述 Description
3n+1问题是一个简单有趣而又没有解决的数学问题。这个问题是由L. Collatz在1937年提出的。克拉兹问题（Collatz problem）也被叫做hailstone问题、3n+1问题、Hasse算法问题、Kakutani算法问题、Thwaites猜想或者Ulam问题。
问题如下：
（1）输入一个正整数n；
（2）如果n=1则结束；
（3）如果n是奇数，则n变为3n+1，否则n变为n/2；
（4）转入第（2）步。
克拉兹问题的特殊之处在于：尽管很容易将这个问题讲清楚，但直到今天仍不能保证这个问题的算法对所有可能的输入都有效——即至今没有人证明对所有的正整数该过程都终止。
输入描述 Input Description
第一行是一个整数T.表示输入数据的组数.
第二行是T个正整数n.
输出描述 Output Description
对于每个正整数n，每行输出一个数s，表示n通过多少步变换会变成1，如果n无法变成1，则输出-1.
样例输入 Sample Input
3
1 2 3
样例输出 Sample Output
0
1
7
数据范围及提示 Data Size & Hint
小数据版本：
1 <= T <= 100
1 <= n <= 10000
大数据版本：
1 <= T <= 300000
1 <= n <= 1000000000
个人解法：
其实这个题大数据版本还有升级版：
T2969，角谷猜想
原题：https://codevs.cn/problem/2969/
题解：https://liaoy148.lofter.com/post/1da8a74e_9dccfe9
好了，接下来我们来说说这一题。
对于小数据版本，我们只需模拟即可过完所有点。
代码如下：
var
n,t,i,s:longint;
procedure dfs(num,step:longint);
begin
if num=1 then
begin
s:=step;
exit;
end;
if num mod 2=0 then dfs(num div 2,step+1)
else dfs(num*3+1,step+1);
end;
begin
read(t);
for i:=1 to t do
begin
read(n);
s:=0;
dfs(n,0);
writeln(s);
end;
end.
也就是简单的模拟，不用思考的暴力。
耗时如下：
所以小数据版本就可以简单over了。
那么大数据版本呢？
既然我们看到了那么多的0，又想想我们靠的是搜索，自然可以想到一个大大的剪枝方法：记忆化。
事实也是这样，这道题可以用记忆化over（虽然动态记忆化并不快，至于静态的（打表）我就没试了）。
我们在搜索的时候，可以把一路过来的数到1的步数都用一个数组记录下来。在下一次DFS的时候，先检查是否可以调用，如果可以调用，那么就直接带着调用的步数返回就可以了。
代码如下：
var
n:int64;
t,i,k:longint;
a:array[1..4000000] of longint;//记忆化数组
function dfs(num:int64):longint;
begin
if num<=4000000 then
if a[num]<>-1 then
begin
dfs:=a[num];
exit(dfs);
end;
if num mod 2=0 then dfs:=dfs(num div 2)+1
else dfs:=dfs(num*3+1)+1;
if num<=4000000 then a[num]:=dfs;//动态记录
end;
begin
fillchar(a,sizeof(a),255);//这个操作是把数组赋值为-1，不是255。
a[1]:=0;
read(t);
for i:=1 to t do
begin
read(n);
k:=dfs(n);
writeln(k);
end;
end.
其实动态记录的耗时是很不均匀的，但也许是数据差不多，所以评测结果也相似。
耗时如下（很慢……）：
两个题放在一起来了一篇题解，如果各位master有什么看法或意见，欢迎提出。
希望与你们共同进步。