[C_CH10-中] The 3n + 1 problem(C++)

[C_CH10-中] The 3n + 1 problem

成績: 0 / 倒扣: 0.8

問題描述：考慮以下的演算法：
1. 輸入 n
2. 印出 n
3. 如果 n = 1 結束
4. 如果 n 是奇數 那麼 n=3*n+1
5. 否則 n=n/2
6. GOTO 2
例如輸入 22, 得到的數列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
據推測此演算法對任何整數而言會終止 ( 當列印出 1 的時候 ) 。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的 n ( 0 < n < 1,000,000 ) 來說，以上的推測已經被驗證是正確的。
給一個輸入 n , 透過以上的演算法我們可以得到一個數列（ 1 作為結尾）。此數列的長度稱為 n 的 cycle-length 。上面提到的例子 , 22 的 cycle length 為 16 。
問題來了：對任 2 個整數 i ， j 我們想要知道介於 i ， j （包含 i ， j ）之間的數所產生的數列中最大的 cycle length 是多少。
輸入說明：輸入可能包含了好幾列測試資料，每一列有一對整數資料 i ， j 。 0< i ， j < 1,000,000
輸出說明：對每一對輸入 i , j 你應該要輸出 i, j 和介於 i, j 之間的數所產生的數列中最大的 cycle length 。範例：

Sample Input:	Sample Output:
1 10 10 1 100 200 201 210 900 1000	1 10 20 10 1 20 100 200 125 201 210 89 900 1000 174

解釋

長度count

範圍內最常長度max

帶測數字num

num是奇數: num = num*3+1

num是偶數: num = num/2

假設num的範圍是1~10

1 4 2 1

2 1 4 2 1

3 10 5 16 8 4 2 1

4 2 1

5 16 8 4 2 1

6 3 10 5 16 8 4 2 1

7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

8 4 2 1

9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

10 5 16 8 4 2 1

num    1   2   3   4   5   6   7    8   9   10

count  4   5   8   3   6   9   17   4   20  7

max = 20

輸出 x y max

1. #include <iostream>  
2. using namespace std;  
3.   
4. int main() {  
5.     // [C_CH10-中] The 3n + 1 problem  
6.     int x, y, num, count = 1,max = 0;  
7.     bool fir = true;  
8.     while(cin >> x >> y)  
9.     {  
10.         if(x > y)  
11.         {  
12.             for(int i = y;i <= x;i++)  
13.             {  
14.                 num = i;  
15.                 if(i == 1 && fir)  
16.                 {  
17.                     num = 3*num+1;  
18.                     count++;  
19.                     fir = false;  
20.                 }  
21.                 while(num != 1)  
22.                 {  
23.                     if(num % 2 != 0)  
24.                     {  
25.                         num = 3*num+1;  
26.                         count++;  
27.                     }  
28.                     else  
29.                     {  
30.                         num = num / 2;  
31.                         count++;  
32.                     }  
33.                 }  
34.                 if(max < count)  
35.                 {  
36.                     max = count;  
37.                 }  
38.                 count = 1;  
39.             }  
40.             cout << x << " " << y << " " << max << endl;  
41.             max = 0;  
42.         }  
43.         else //y > x  
44.         {  
45.             for(int i = x;i <= y;i++)  
46.             {  
47.                 num = i;  
48.                 if(i == 1 && fir)  
49.                 {  
50.                     num = 3*num+1;  
51.                     count++;  
52.                     fir = false;  
53.                 }  
54.                 while(num != 1)  
55.                 {  
56.                     if(num % 2 != 0)  
57.                     {  
58.                         num = 3*num+1;  
59.                         count++;  
60.                     }  
61.                     else  
62.                     {  
63.                         num = num / 2;  
64.                         count++;  
65.                     }  
66.                 }  
67.                 if(max < count)  
68.                 {  
69.                     max = count;  
70.                 }  
71.                 count = 1;  
72.             }  
73.             cout << x << " " << y << " " << max << endl;  
74.             max = 0;  
75.         }  
76.         fir = true;  
77.     }  
78.     return 0;  
79. }