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 |
從大的數開始算，並將過程中的數也記錄下來，之後遇到就不用重複算，節省時間。
程式碼
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
35
36
37
38
39
40
41
42
43
44
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define mxn 1000000
using namespace std;
long long int cycle_len[mxn];
bool vis[mxn];
int main(){
fastio;
stack<long long int> sta;
long long int temp, c, num;
cycle_len[1] = 1;
vis[1] = true;
for(int i = mxn - 1; i > 0; --i){
if(!vis[i]){
temp = i;
while(temp != 1){
sta.push(temp);
if(temp & 1) temp = 3 * temp + 1;
else temp >>= 1;
}
c = 2;
while(!sta.empty()){
num = sta.top();
sta.pop();
if(num < mxn){
vis[num] = true;
cycle_len[num] = c;
}
++c;
}
}
}
int s, e;
long long int mx;
while(cin >> s){
cin >> e;
mx = -50;
for(int i = min(s, e); i <= max(s, e); ++i){
mx = max(mx, cycle_len[i]);
}
cout << s << " " << e << " " << mx << "\n";
}
}
|