The 3n + 1 problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18197 Accepted Submission(s): 6721
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n <- 3n + 1
5. else n <- n / 2
6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that
0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no opperation overflows a 32-bit integer.
for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).
1 10 100 200 201 210 900 1000
1 10 20 100 200 125 201 210 89 900 1000 174
代码如下:
#include <iostream> using namespace std ; inline bool isOdd(int n) { if ( n & 0x01) return true ; return false ; } int cycleLen(int n) { int ret = 0 ; while (1) { ret ++ ; if (n == 1) break ; if (isOdd(n)) n = ( n << 1 ) + n + 1 ; else n >>= 1 ; } return ret ; } int cycleLen(int m, int n) { int i = m; int j = n; if ( m > n) { i = n; j = m ; } int ret = 0 ; for (int p = i; p <= j; ++ p) { int tmp = cycleLen(p) ; if (ret < tmp) ret = tmp ; } return ret ; } int main(int argc, char ** argv) { int test1, test2 ; while(cin >> test1 >> test2) cout <<test1 << " " << test2 << " "<< cycleLen(test1, test2) << endl; return 0 ; }