题目描述考虑以下算法输入nnn输出nnn如果n1n 1n1则停止如果nnn是奇数则n←3n1n \leftarrow 3n 1n←3n1否则n←n/2n \leftarrow n/2n←n/2回到第 2 步例如输入n22n 22n22将输出序列22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 122\ 11\ 34\ 17\ 52\ 26\ 13\ 40\ 20\ 10\ 5\ 16\ 8\ 4\ 2\ 1221134175226134020105168421该序列共有161616个数因此222222的循环节长度为161616。猜想对于任意正整数nnn该算法最终都会停止在n1n 1n1。虽然尚未被证明但已对0n1,000,0000 n 1,000,0000n1,000,000的所有整数验证成立。任务输入多组整数对(i,j)(i, j)(i,j)对每组数据输出iii、jjj以及区间[i,j][i, j][i,j]内所有整数的最大循环节长度。输入格式每行两个整数iii和jjj所有整数满足0i,j10,0000 i, j 10,0000i,j10,000。输出格式对每组输入输出一行iii、jjj和最大循环节长度用空格分隔。样例输入1 10 100 200 201 210 900 1000样例输出1 10 20 100 200 125 201 210 89 900 1000 174解题思路问题分析我们需要对每个n∈[i,j]n \in [i, j]n∈[i,j]计算其循环节长度并找出最大值。直接模拟算法过程是可行的但需要注意以下几点计算过程中可能溢出当nnn是奇数时会执行3n13n 13n1若nnn较大可能超过int\texttt{int}int或long\texttt{long}long的表示范围例如n999999n 999999n999999时3n13n13n1接近333百万。因此应使用long long\texttt{long long}long long类型来存储中间结果。区间端点顺序输入中可能iji jij此时需交换iii和jjj确保区间为[min(i,j),max(i,j)][\min(i, j), \max(i, j)][min(i,j),max(i,j)]。效率优化如果对每个数都重新计算循环节长度会重复计算很多相同的子问题。我们可以使用记忆化缓存技术将已经计算过的循环节长度保存起来下次遇到相同数时直接查表。算法设计定义一个全局数组cache\texttt{cache}cachecache[k]\texttt{cache}[k]cache[k]表示数kkk的循环节长度若未计算则为000。使用递归函数counter(number)\texttt{counter(number)}counter(number)计算循环节长度若number1\texttt{number} 1number1返回111。若number\texttt{number}number是奇数则number3×number1\texttt{number} 3 \times \texttt{number} 1number3×number1。若number\texttt{number}number是偶数则numbernumber/2\texttt{number} \texttt{number} / 2numbernumber/2。如果number\texttt{number}number在缓存范围内且已计算过直接返回缓存值否则递归计算并保存。主程序读入每组i,ji, ji,j调整区间后遍历每个数调用counter\texttt{counter}counter函数更新最大循环节长度。复杂度分析时间复杂度由于记忆化避免了重复计算每个数最多被计算一次整体复杂度接近O(n)O(n)O(n)。空间复杂度使用了一个大小为10610^6106的数组为O(1)O(1)O(1)。代码实现// The 3n1 problem 3n1 问题// PC/UVa IDs: 110101/100, Popularity: A, Success rate: low Level: 1// Verdict: Accepted// Submission Date: 2011-05-22// UVa Run Time: 0.032s//// 版权所有C2011邱秋。metaphysis # yeah dot net。//// [问题描述]// 考虑如下的序列生成算法从整数 n 开始如果 n 是偶数把它除以 2如果 n 是奇数把它乘 3 加// 1。用新得到的值重复上述步骤直到 n 1 时停止。例如n 22 时该算法生成的序列是//// 221134175226134020105168421//// 人们猜想没有得到证明对于任意整数 n该算法总能终止于 n 1。这个猜想对于至少 1 000 000// 内的整数都是正确的。//// 对于给定的 n该序列的元素包括 1个数被称为 n 的循环节长度。在上述例子中22 的循环节长度// 为 16。输入两个数 i 和 j你的任务是计算 i 到 j包含 i 和 j之间的整数中循环节长度的最大// 值。//// [输入]// 输入每行包含两个整数 i 和 j。所有整数大于 0小于 1 000 000。//// [输出]// 对于每对整数 i 和 j按原来的顺序输出 i 和 j然后输出二者之间的整数中的最大循环节长度。这三// 个整数应该用单个空格隔开且在同一行输出。对于读入的每一组数据在输出中应位于单独的一行。//// [样例输入]// 1 10// 100 200// 201 210// 900 1000//// [样例输出]// 1 10 20// 100 200 125// 201 210 89// 900 1000 174//// [解题方法]// 计算每个数的循环节长度求给定区间的最大值。//// 需要注意// 1. 中间计算过程会超过 int 或 long 如果 int 或 long 型均为 4 字节存储空间 型数据所能// 表示的范围故需要选择 long long 8 字节存储空间型整数除非你使用的算法在做乘的时候不// 使用一般的乘法而是使用替代方法实现原数的三倍加一。// 2. 输入时可能较大的数在前面需要调整顺序这个是导致算法正确却 WA 的重要原因。// 3. 采用填表的方法保存既往计算结果可以显著减少计算时间。//// 从网络上看了许多别人的解题方案大多数都是忽略了第一点求循环节长度的过程中选择了 int 或// long 按 32 位 CPU 来假定4 字节存储空间类型的数据当计算 n * 3 1 时会超出 32// 位整数的表示范围而得到错误答案只不过 Programming Challenges 和 UVa 上的测试数据不是很强// 所以尽管不完善但都会获得 AC。在 1 - 999999 之间共有 41 个数在中间计算过程中会得到大于 32 位// 无符号整数表示范围的整数当测试数据包含这些数时选用 int 或 long 类型有可能会得到错误的答案。//// 在中间计算过程中会超过 32 位整数表示范围的整数括号内为循环节长度// 159487184 270271407 318975185 376831330 419839162// 420351242 459759214 626331509 655359292 656415292// 665215442 687871380 704511243 704623504 717695181// 730559380 736447194 747291248 753663331 763675318// 780391331 807407176 822139344 829087194 833775357// 839679163 840703243 847871326 859135313 901119251// 906175445 917161383 920559308 937599339 944639158// 945791238 974079383 975015321 983039290 984623290// 997823440#includeiostreamusingnamespacestd;#definemin(a,b)((a)(b)?(a):(b))#definemax(a,b)((a)(b)?(a):(b))#defineMAXSIZE1000000intcache[MAXSIZE];// 计算循环节长度intcounter(longlongnumber){if(number1)return1;// 模 2 计算可用与计算代替除 2 计算可用右移计算代替if(number1)number(number1)1;elsenumber1;// 若 number 在缓存范围内则根据情况取用if(numberMAXSIZE){if(!cache[number])cache[number]counter(number);return1cache[number];}return1counter(number);}intmain(){intfirst,second,start,end;while(cinfirstsecond){// 得到给定范围的上下界startmin(first,second),endmax(first,second);// 查找最大步长值intresult0,steps;for(intistart;iend;i)if((stepscounter(i))result)resultsteps;// 输出coutfirst second resultendl;}return0;}总结本题是一个经典的模拟记忆化搜索问题关键在于使用long long\texttt{long long}long long避免溢出正确处理输入区间使用缓存提升效率。虽然问题本身简单但细节处理不当容易导致错误是一个很好的编程练习题目。
