Shandong University of Technology ACM answers questions about the C language pla

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

3n+1 several chain

Time Limit: 1000ms Memory limit: 65536K have questions? Click here^_^

Problem description

In computer science, there are many types of like the problem is not solved, we call it can not solve the problem. However, in many cases, we do not know what kind of problem can be solved, what kind of problems can not be solved. We have such a problem now, as follows:
(1)Enter a positive integer n,
(2)The N display,
(3)If n=1 is the end,
(4)If n is odd, n to 3*n+ 1, otherwise it becomes n/2,
(5)(2) step into a.
For example, for a positive integer input 22, should have the following sequence is displayed:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
We conjecture: for any positive integer, after the above algorithm will eventually push to 1. Although this algorithm is very simple, but we still can not determine our inference is correct. Fortunately, we have computer, we tested for positive integer less than 1000000 can satisfy the above inference.
For n a positive integer, we show the definition of a number of N chain length, for example, 22 of the chain length of 16.
Your task is to write a program, for any pair of positive integers i and j, the largest chain between I and j are long, the longest chain length is between I and j and a positive integer generated. We here I and j including I including J.

Input

Enter two integers i, J, between I and j with an empty spaced. 0 <i <= j <10000.

Output

The output data is only one line, which is the longest chain between I and j long.

Sample input

1 10

Sample output

20

#include <stdio.h>
int getLinkLen(int n)
{
if (n == 1) return 1;
return n&1 ? getLinkLen(n*3+1)+1 : getLinkLen(n/2)+1;
}
int main()
{
int x, y, i, t, max = 0;
scanf("%d %d", &x, &y);
for (i=x; i<=y; i++){
t = getLinkLen(i);
if (t > max) max = t;
}
printf("%d\n", max);
return 0;
}


Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Dominic at December 18, 2013 - 11:29 PM