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"; } }
|