d704 - Fibonacci 進制轉換

🔗 前往 ZeroJudge 原題

題目描述

題目要求將一個十進位正整數轉換為阿樺自創的斐波那契進制。斐波那契進制的每一位使用不同的進位制，分別為 2, 3, 5, 8, 13, 21, 34, 55 等斐波那契數列的後續項。輸出時，各個位數之間用逗號分隔。

解題思路

解題的核心思想是貪心演算法。從最低位的斐波那契數開始，依次嘗試用當前斐波那契數來表示剩餘的數值。如果可以，則將該位數的值設為 n % fib[i]，並將 n 除以 fib[i]。重複此過程，直到 n 變為 0。由於斐波那契數列的特性（每個數都大於等於其前兩個數的和），這個過程可以保證找到唯一的斐波那契進制表示。

程式碼首先預先計算出前 20 個斐波那契數，儲存在 fib 陣列中。然後，對於每個輸入的十進位數 n，使用迴圈迭代地計算斐波那契進制表示的每一位，並將結果儲存在 ans 陣列中。最後，按照從高位到低位的順序輸出 ans 陣列中的值，並用逗號分隔。

複雜度分析

• 時間複雜度: O(log(n))。因為斐波那契數列增長迅速，迴圈的迭代次數與輸入數 n 的對數成正比。
• 空間複雜度: O(1)。程式碼使用的額外空間是固定的，與輸入數 n 的大小無關。fib 和 ans 陣列的大小都是固定的。

程式碼

#include <iostream>
using namespace std;
int fib[20]={2,3},n,it,ans[20];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=2;i<20;++i){
		fib[i]+=fib[i-1]+fib[i-2];
	}
	while(cin >> n){
		it=0;
		while(n){
			ans[it]=n%fib[it];
			n/=fib[it];
			++it;
		}
		for(int i=it-1;i>=0;--i){
			cout << ans[i];
			if(i)cout << ','; 
		}
		cout << "\n";
	}
}