题目描述阿克曼函数的一个特性是函数生成的数列长度无法直接从输入值计算得出。一种特定的整数阿克曼函数定义如下f(n){n/2if n is even3n1if n is odd f(n) \begin{cases} n/2 \text{if } n \text{ is even} \\ 3n 1 \text{if } n \text{ is odd} \end{cases}f(n){n/23n1​ifnis evenifnis odd​该阿克曼函数的特性是它最终收敛到111。示例起始值在方括号中后跟生成的数列数列长度在大括号中[10] 5 16 8 4 2 1 {6}[10]\ 5\ 16\ 8\ 4\ 2\ 1\ \{6\}[10]5168421{6}[13] 40 20 10 5 16 8 4 2 1 {9}[13]\ 40\ 20\ 10\ 5\ 16\ 8\ 4\ 2\ 1\ \{9\}[13]4020105168421{9}[14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}[14]\ 7\ 22\ 11\ 34\ 17\ 52\ 26\ 13\ 40\ 20\ 10\ 5\ 16\ 8\ 4\ 2\ 1\ \{17\}[14]7221134175226134020105168421{17}[19] 58 29 88 44 22 … 2 1 {20}[19]\ 58\ 29\ 88\ 44\ 22\ \dots\ 2\ 1\ \{20\}[19]5829884422…21{20}[32] 16 8 4 2 1 {5}[32]\ 16\ 8\ 4\ 2\ 1\ \{5\}[32]168421{5}[1] 4 2 1 {3}[1]\ 4\ 2\ 1\ \{3\}[1]421{3}输入格式输入包含多行每行两个整数表示区间的起始和结束值。最后一行以0 0结束。输出格式对于每个区间输出Between L and H, V generates the longest sequence of S values.其中LLL和HHH是区间的边界小的在前VVV是生成最长序列的第一个值如有并列取较小的SSS是序列长度。样例输入1 20 35 55 0 0样例输出Between 1 and 20, 18 generates the longest sequence of 20 values. Between 35 and 55, 54 generates the longest sequence of 112 values.题目分析问题的本质这是经典的3n13n13n1问题也称考拉兹猜想、冰雹猜想。需要计算区间内每个数生成到111的序列长度并找出最长者。序列长度定义从起始数开始按规则生成直到到达111为止。注意起始数本身也算一个值。例如[10]→5→16→8→4→2→1[10] \to 5 \to 16 \to 8 \to 4 \to 2 \to 1[10]→5→16→8→4→2→1长度为666101010到111共666个数。数据范围输入值在323232位整数范围内但中间值可能超过323232位需要使用long long。优化策略使用记忆化搜索memoization\texttt{memoization}memoization缓存已计算的值。由于区间最大可能很大如1∼1061 \sim 10^61∼106直接计算每个数会重复大量计算。参考代码// Ackermann Functions// UVa ID: 371// Verdict: Accepted// Submission Date: 2016-06-25// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intcache[500010]{0};// 缓存序列长度// 递归计算从 number 到 1 的序列长度intcounter(longlongintnumber){// 奇数3n1偶数n/2if(number1)number(number1)1;elsenumber1;if(number1)return1;// 如果在缓存范围内且未计算过递归计算if(number500000){if(!cache[number])cache[number]counter(number);return1cache[number];}// 超出缓存范围继续递归return1counter(number);}intmain(){ios::sync_with_stdio(false);// 预处理所有 1..500000 的序列长度for(inti1;i500000;i)cache[i]counter(i);intfirst,second,start,end;while(cinfirstsecond,firstsecond){startmin(first,second);endmax(first,second);intresult0,maxistart;for(intistart;iend;i){longlongtempi;intsteps0;// 处理大于缓存范围的值直到进入缓存范围while(temp500000){if(temp1)temp(temp1)1;// 3*temp1elsetemp1;// temp/2steps;}// 加上缓存中的长度stepscache[temp];// 更新最大值if(stepsresult){resultsteps;maxii;}}coutBetween start and end;cout, maxi generates the longest sequence of result values.endl;}return0;}