CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=a134
內容
給一組十進位數字，以費氏進位輸出(如下)。
17 = 1 0 0 1 0 1
13+3+1 = 13 8 5 3 2 1
輸入的第一行含有一個數字 N，代表以下有幾個數字 ( 1 ≤ N ≤ 500)。
接下來有 N 行，每行有一個小於 100 000 000 的正整數。數字不一定按順序出現。
範例輸入
10
1
2
3
4
5
6
7
8
9
10
範例輸出
1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)
想法
先建一個足夠大的陣列存費氏數列，將陣列由大跑到小，如果小於輸入值，則更新。
注意不可出現相鄰的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
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
int N, dp[41], num;
bool suc, beg;
cin >> N;
memset(dp, 0, sizeof(dp));
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < 41; ++i){
dp[i] = dp[i - 1] + dp[i - 2];
}
while(N--){
cin >> num;
suc = true;
beg = false;
cout << num << " = ";
for(int i = 40; i >= 0; --i){
if(dp[i] <= num){
beg = true;
if(suc){
num -= dp[i];
cout << 1;
suc = false;
}
else {
cout << 0;
suc = true;
}
}
else if(beg){
cout << 0;
suc = true;
}
}
cout << " (fib)\n";
}
}
|