CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=c039
內容
考慮以下的演算法:
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
此數列的長度稱為 cycle-length。上面提到的例子, 22 的 cycle length為 16.
給定兩個整數 i, j (0 < i, j < 1000000),輸出介於 i, j 之間的數所產生的數列中最大的cycle length 。
範例輸入
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
想法
輸入 22, 得到的數列: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
可以發現計算一數的 cycle-length 時可以順便得到其他數的 cycle-length
num | cycle-length |
---|---|
22 | 16 |
11 | 15 |
34 | 14 |
17 | 13 |
… | … |
2 | 2 |
1 | 1 |
從大的數開始算,並將過程中的數也記錄下來,之後遇到就不用重複算,節省時間。
程式碼
C++
1 |
|