UVa 100 3n+1 Problem

题目描述

考虑以下算法：

1. 输入nnn
2. 输出nnn
3. 如果n=1n = 1n=1，则停止
4. 如果nnn是奇数，则n←3n+1n \leftarrow 3n + 1n←3n+1
5. 否则n←n/2n \leftarrow n/2n←n/2
6. 回到第 2 步

例如，输入n=22n = 22n=22，将输出序列：
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，该算法最终都会停止在n=1n = 1n=1。虽然尚未被证明，但已对0<n<1,000,0000 < n < 1,000,0000<n<1,000,000的所有整数验证成立。

任务：输入多组整数对(i,j)(i, j)(i,j)，对每组数据，输出iii、jjj以及区间[i,j][i, j][i,j]内所有整数的最大循环节长度。

输入格式

每行两个整数iii和jjj，所有整数满足0<i,j<10,0000 < i, j < 10,0000<i,j<10,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]计算其循环节长度，并找出最大值。
直接模拟算法过程是可行的，但需要注意以下几点：

1. 计算过程中可能溢出：
   当nnn是奇数时，会执行3n+13n + 13n+1，若nnn较大，可能超过int\texttt{int}int或long\texttt{long}long的表示范围（例如n=999999n = 999999n=999999时，3n+13n+13n+1接近333百万）。因此，应使用long long\texttt{long long}long long类型来存储中间结果。

2. 区间端点顺序：
   输入中可能i>ji > ji>j，此时需交换iii和jjj，确保区间为[min⁡(i,j),max⁡(i,j)][\min(i, j), \max(i, j)][min(i,j),max(i,j)]。

3. 效率优化：
   如果对每个数都重新计算循环节长度，会重复计算很多相同的子问题。我们可以使用记忆化（缓存）技术，将已经计算过的循环节长度保存起来，下次遇到相同数时直接查表。

算法设计

• 定义一个全局数组cache\texttt{cache}cache，cache[k]\texttt{cache}[k]cache[k]表示数kkk的循环节长度（若未计算则为000）。
• 使用递归函数counter(number)\texttt{counter(number)}counter(number)计算循环节长度：
  • 若number=1\texttt{number} = 1number=1，返回111。
  • 若number\texttt{number}number是奇数，则number=3×number+1\texttt{number} = 3 \times \texttt{number} + 1number=3×number+1。
  • 若number\texttt{number}number是偶数，则number=number/2\texttt{number} = \texttt{number} / 2number=number/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 3n+1 problem （3n+1 问题）// PC/UVa IDs: 110101/100, Popularity: A, Success rate: low Level: 1// Verdict: Accepted// Submission Date: 2011-05-22// UVa Run Time: 0.032s//// 版权所有（C）2011，邱秋。metaphysis # yeah dot net。//// [问题描述]// 考虑如下的序列生成算法：从整数 n 开始，如果 n 是偶数，把它除以 2；如果 n 是奇数，把它乘 3 加// 1。用新得到的值重复上述步骤，直到 n = 1 时停止。例如，n = 22 时该算法生成的序列是：//// 22，11，34，17，52，26，13，40，20，10，5，16，8，4，2，1//// 人们猜想（没有得到证明）对于任意整数 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 位整数表示范围的整数（括号内为循环节长度）：// 159487（184） 270271（407） 318975（185） 376831（330） 419839（162）// 420351（242） 459759（214） 626331（509） 655359（292） 656415（292）// 665215（442） 687871（380） 704511（243） 704623（504） 717695（181）// 730559（380） 736447（194） 747291（248） 753663（331） 763675（318）// 780391（331） 807407（176） 822139（344） 829087（194） 833775（357）// 839679（163） 840703（243） 847871（326） 859135（313） 901119（251）// 906175（445） 917161（383） 920559（308） 937599（339） 944639（158）// 945791（238） 974079（383） 975015（321） 983039（290） 984623（290）// 997823（440）#include<iostream>usingnamespacestd;#definemin(a,b)((a)<=(b)?(a):(b))#definemax(a,b)((a)>=(b)?(a):(b))#defineMAXSIZE1000000intcache[MAXSIZE];// 计算循环节长度intcounter(longlongnumber){if(number==1)return1;// 模 2 计算可用与计算代替，除 2 计算可用右移计算代替if(number&1)number+=(number<<1)+1;elsenumber>>=1;// 若 number 在缓存范围内则根据情况取用if(number<MAXSIZE){if(!cache[number])cache[number]=counter(number);return1+cache[number];}return1+counter(number);}intmain(){intfirst,second,start,end;while(cin>>first>>second){// 得到给定范围的上下界start=min(first,second),end=max(first,second);// 查找最大步长值intresult=0,steps;for(inti=start;i<=end;i++)if((steps=counter(i))>result)result=steps;// 输出cout<<first<<" "<<second<<" "<<result<<endl;}return0;}

总结

本题是一个经典的模拟+记忆化搜索问题，关键在于：

• 使用long long\texttt{long long}long long避免溢出；
• 正确处理输入区间；
• 使用缓存提升效率。

虽然问题本身简单，但细节处理不当容易导致错误，是一个很好的编程练习题目。