回到 CPE 必考一顆星 49 題選集

UVa 100 - The 3n+1 problem

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

  • 題目給定一個演算法，當 n 為 1 則結束，如果 n 是奇數則 n = 3*n+1，否則n = n/2。每一次遞迴都會打印一次 n。
  • 給一個輸入 n ,透過以上的演算法我們可以得到一個數列（1作為結尾）。此數列的長度稱為 n 的 cycle-length。
    • 例如輸入 n 為 22, 得到的數列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 ，則 22 的 cycle length 為 16。
  • 輸入包含多列測資，每列有一對整數 i,j (0< i,j <1000000)。

Step 2. 解題思路

  • 依照題目的說明製作遞迴式。

Step 3. 範例輸入與輸出 - Sample Input and Output

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

Extra Sample Input
Extra Sample Output

uDebug 快速連結
Diffnow (線上比對程式)
C++ Online Compiler
Python Online Compiler

Step 4. 參考程式碼 - Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int main() {
    int i,j;
    while(cin>>i>>j) {
        int m=i, n=j;
        if(i>j) 
            swap(i,j);
        int k=i;
        int max=0;
        
        while(k<=j) {
            int n=k;
            int temp=1;
            while(n!=1) {
                if(n%2==1) {  //n is odd
                    n=3*n+1;
                    n/=2;
                    temp+=2;
                }
                if(n%2==0) {  //n is even
                    n/=2;
                    temp++;
                }
            }
            if(max<temp) 
                max=temp;
            k++;
        }
        cout<<m<<" "<<n<<" "<<max<<endl;
    }
    return 0;
}
回到 CPE 必考一顆星 49 題選集