a134 - 00948 - Fibonaccimal Base
題目描述
題目要求將給定的十進位數字轉換為費氏進位表示法。費氏進位是一種特殊的進位制，其位數由費氏數列決定。轉換的限制條件是不允許出現相鄰的 1。
解題思路
程式碼的核心思想是貪心演算法。從最大的費氏數開始，嘗試從輸入數字中減去它，如果可以減去，則在結果中添加一個 '1'，否則添加一個 '0'。這個過程重複進行，直到輸入數字變為 0。由於費氏數列的特性，這種貪心策略可以保證得到唯一的費氏進位表示法。程式首先預先計算出前 40 個費氏數，然後對每個輸入數字進行轉換。
複雜度分析
- 時間複雜度: O(N * log(M))，其中 N 是輸入數字的個數，M 是輸入數字的最大值。log(M) 代表計算費氏數列的數量級，以及貪心演算法的迭代次數。
- 空間複雜度: O(1)，程式只使用了固定大小的陣列來儲存費氏數列，因此空間複雜度是常數級別。
程式碼
#include <iostream>
#include <string>
using namespace std;
int a[40]={0};
int main(){
a[0]=1;
a[1]=2;
for(int i=0;i<39;i++){
if(i!=0)
a[i+1]=a[i]+a[i-1];
}
int c;
cin >> c;
while(cin >> c){
bool f=0,d=0;
cout << c << " = ";
while(c>0){
for(int i=39;i>=0;i--){
if(c>=a[i]){
c-=a[i];
cout << "1";
if(c==0){
while(i--){
cout << "0";
}
}
f=1;d=1;
i--;
}
else if(c<a[i]&&f!=0)
cout << "0";
if(f!=0&&d==1&&i>=0){
cout << "0";
d=0;
}
}
}
cout << " (fib)\n";
}
}