The 3n + 1 problem
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.
1 10 100 200 201 210 900 1000
1 10 20 100 200 125 201 210 89 900 1000 174
/* * hdu 1032 The 3n + 1 problem * 2011/07/25 * artwalk */ #include <iostream> using namespace std; int MAX(int i, int j); int count(int k); int main(int ac, char** av) { int i, j; while ( cin >> i >> j ) { cout << i << " " << j << " "; if ( i > j ) { // 注意 i j 之间 int temp = i; i = j; j = temp; } cout << MAX(i, j) << endl; } return 0; } int MAX(int i, int j) { // i to j 中最大次数 int maxnum = 0; for ( ; i <=j; ++i ) { int k = i; int temp = 0; temp = count(k); if ( maxnum < temp) { maxnum = temp; } } return maxnum; } int count(int k) { // 单个数的次数 int num = 1; while ( k != 1 ) { if ( k % 2 != 0 ) { k = 3 * k + 1; } else { k = k >> 1; } ++num; } return num; }