题目描述给定一个正整数AAA和限制值LLL根据Collatz\texttt{Collatz}Collatz序列生成规则若A1A 1A1停止若AAA为偶数则AA/2A A / 2AA/2若AAA为奇数则A3A1A 3A 1A3A1。要求计算在序列中从初始值开始直到遇到111或下一个将要产生的值超过LLL为止序列中包含的项数包括初始值。注意如果某一步计算出的值大于LLL则该值不应计入序列长度。输入格式多组测试用例每行两个正整数AAA和LLLALA LAL均不超过231−12^{31}-1231−1。输入以两个负数结束。输出格式对于每组用例输出格式为Case X: A A, limit L, number of terms N其中XXX为用例编号从111开始。样例输入3 100 34 100 75 250 27 2147483647 101 304 101 303 -1 -1输出Case 1: A 3, limit 100, number of terms 8 Case 2: A 34, limit 100, number of terms 14 Case 3: A 75, limit 250, number of terms 3 Case 4: A 27, limit 2147483647, number of terms 112 Case 5: A 101, limit 304, number of terms 26 Case 6: A 101, limit 303, number of terms 1题目分析本题直接模拟Collatz\texttt{Collatz}Collatz序列并在每一步计算新值后检查是否超过限制。注意初始值AAA已经计入项数且ALA LAL。当A1A 1A1时序列停止项数包含111。若在循环中计算出的下一个值TLT LTL则终止循环且TTT不计入项数。由于AAA和LLL最大为231−12^{31}-1231−1中间值可能溢出323232位整数因此使用646464位整数long long存储。解题思路读入AAA和LLL若均为负数则退出。初始化项数terms 1当前值T A。当T1T 1T1时若TTT为偶数TT/2T T / 2TT/2否则T3T1T 3T 1T3T1。若TLT LTL则终止循环。否则terms。输出结果。复杂度分析每个用例模拟的步数通常较小Collatz\texttt{Collatz}Collatz序列长度在L≤231L \le 2^{31}L≤231时不超过几百时间复杂度O(steps)O(\text{steps})O(steps)。空间复杂度O(1)O(1)O(1)。代码实现// The Collatz Sequence// UVa ID: 694// Verdict: Accepted// Submission Date: 2016-07-14// UVa Run Time: 0.020s#includebits/stdc.husingnamespacestd;intmain(intac,char*av[]){ios::sync_with_stdio(false);intcases0;longlongA,L;while(cinAL){if(A0||L0)break;intterms1;longlongTA;while(T1){if(T%20)T/2;elseTT*31;if(TL)break;terms;}coutCase cases: A A;cout, limit L, number of terms termsendl;}return0;}总结本题模拟Collatz\texttt{Collatz}Collatz序列关键在于正确判断何时终止下一个值超过限制时不计入项数以及使用646464位整数防止溢出。该解法简单直接适合作为模拟题的练习。
