d486 - Fibonacci 's computation process
題目描述
題目要求模擬費氏數列的計算過程，並按照指定的格式輸出。輸入一個數字 n，輸出計算 f(n) 的過程，直到分解到只剩下 f(0) 或 f(1) 為止。最後輸出 f(n) 的值。
解題思路
程式使用佇列 (queue) 來模擬費氏數列的遞迴計算過程。首先，將輸入的 n 放入佇列。然後，不斷從佇列中取出一個數 k，輸出 "f(k)"。如果 k 大於 1，則將 k-1 和 k-2 放入佇列。如果 k 等於 1，則將 k 放入佇列。每次輸出一定數量的 f(k) 後，計算總和，並在最後輸出 f(n) 的值。使用 swap 函數來清空佇列，以便處理下一組輸入。
複雜度分析
- 時間複雜度: O(2^n) (因為模擬了遞迴的過程，最壞情況下需要計算所有可能的遞迴呼叫)
- 空間複雜度: O(2^n) (佇列中可能存儲大量的元素，取決於 n 的值)
程式碼
#include <iostream>
#include <queue>
using namespace std;
int n;
queue <int> q;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)break;
queue <int> empty;
swap(empty,q);
q.push(n);
int s=1,i=0,t=0,ans=0;
while(i<n){
int k=q.front();
cout << "f(" << k << ") ";
--s;
if(k>1){
q.push(k-1);
q.push(k-2);
t+=2;
}
else{
q.push(k);
++t;
}
if(s==0){
cout << "\n";
if(i==n-1)ans=t;
s=t;
t=0;
++i;
}
q.pop();
}
cout << "f(" << n << ") = " << ans << "\n";
}
}