企业官网建设流程全解析

题目描述

给定一个正整数AAA和限制值LLL，根据Collatz\texttt{Collatz}Collatz序列生成规则：

• 若A=1A = 1A=1，停止；
• 若AAA为偶数，则A=A/2A = A / 2A=A/2；
• 若AAA为奇数，则A=3A+1A = 3A + 1A=3A+1。

要求计算在序列中，从初始值开始，直到遇到111或下一个将要产生的值超过LLL为止，序列中包含的项数（包括初始值）。注意：如果某一步计算出的值大于LLL，则该值不应计入序列长度。

输入格式

多组测试用例，每行两个正整数AAA和LLL，A<LA < LA<L，均不超过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已经计入项数，且A<LA < LA<L。当A=1A = 1A=1时，序列停止，项数包含111。若在循环中计算出的下一个值T>LT > LT>L，则终止循环，且TTT不计入项数。

由于AAA和LLL最大为231−12^{31}-1231−1，中间值可能溢出323232位整数，因此使用646464位整数（long long）存储。

解题思路

1. 读入AAA和LLL，若均为负数则退出。
2. 初始化项数terms = 1，当前值T = A。
3. 当T>1T > 1T>1时：
   • 若TTT为偶数，T=T/2T = T / 2T=T/2；
   • 否则T=3T+1T = 3T + 1T=3T+1。
   • 若T>LT > LT>L，则终止循环。
   • 否则terms++。
4. 输出结果。

复杂度分析

• 每个用例模拟的步数通常较小（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#include<bits/stdc++.h>usingnamespacestd;intmain(intac,char*av[]){ios::sync_with_stdio(false);intcases=0;longlongA,L;while(cin>>A>>L){if(A<=0||L<=0)break;intterms=1;longlongT=A;while(T>1){if(T%2==0)T/=2;elseT=T*3+1;if(T>L)break;terms++;}cout<<"Case "<<++cases<<": A = "<<A;cout<<", limit = "<<L<<", number of terms = "<<terms<<endl;}return0;}

总结

本题模拟Collatz\texttt{Collatz}Collatz序列，关键在于正确判断何时终止（下一个值超过限制时不计入项数）以及使用646464位整数防止溢出。该解法简单直接，适合作为模拟题的练习。