烟大 Contest1024 - 《挑战编程》第一章:入门 Problem A: The 3n + 1 problem(水题)

时间:2023-03-08 17:38:54
烟大 Contest1024 - 《挑战编程》第一章:入门   Problem A: The 3n + 1 problem(水题)

Problem A: The 3n + 1 problem

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 14  Solved: 6
[Submit][Status][Web Board]

Description

Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

Output

For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

HINT


  
  水题。计算从 i 到 j 的最大的周期数,一开始还担心数据规模太大而超时,后来看别人的AC代码发现就是道纯水题,测试数据都没有考虑极限情况,所以就安心提交上去通过了。

My code:

 #include <iostream>

 using namespace std;

 int main()
{
int f(int );
int i,j,ii,jj;
while(cin>>i>>j){
int l,max=;
if(i>j){
ii=j;jj=i;
}
else{
ii=i;jj=j;
}
for(int k=ii;k<=jj;k++){
l=f(k);
if(l>max)
max=l;
}
cout<<i<<' '<<j<<' '<<max<<endl;
}
return ;
} int f(int n)
{//计算 cycle-length ,返回 cycle-length 的值
int l=;
while(n!=){
if(n%==) //如果n是偶数
{
n/=;
}
else//n是奇数
{
n=n*+;
}
++l;
}
return l;
} /**************************************************************
Problem: 1098
User: freecode
Language: C++
Result: Accepted
Time:4 ms
Memory:1268 kb
****************************************************************/

Freecode : www.cnblogs.com/yym2013