#include <iostream>
using namespace std;
int fibonacci(int n, int& count) {
// 基本情況:F(0) = 0 和 F(1) = 1
if (n == 0) return 0;
if (n == 1) return 1;
// 對於n > 1,F(n) = F(n-1) + F(n-2)
// 每次遞歸調用,我們都執行一次加法運算
count += 1;
return fibonacci(n - 1, count) + fibonacci(n - 2, count);
}
int main() {
int n;
cin >> n;//輸入
int count = 0; // 加法運算的次數
int result = fibonacci(n, count);
cout << "費氏數列 " << n << " 項的值是: " << result << endl;
cout << "在計算過程中進行了" << count << "次加法運算。" << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGZpYm9uYWNjaShpbnQgbiwgaW50JiBjb3VudCkgewogICAgLy8g5Z+65pys5oOF5rOB77yaRigwKSA9IDAg5ZKMIEYoMSkgPSAxCiAgICBpZiAobiA9PSAwKSByZXR1cm4gMDsKICAgIGlmIChuID09IDEpIHJldHVybiAxOwogICAgCiAgICAvLyDlsI3mlrxuID4gMe+8jEYobikgPSBGKG4tMSkgKyBGKG4tMikKICAgIC8vIOavj+asoemBnuatuOiqv+eUqO+8jOaIkeWAkemDveWft+ihjOS4gOasoeWKoOazlemBi+eulwogICAgY291bnQgKz0gMTsKICAgIHJldHVybiBmaWJvbmFjY2kobiAtIDEsIGNvdW50KSArIGZpYm9uYWNjaShuIC0gMiwgY291bnQpOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBuOwogICAgY2luID4+IG47Ly/ovLjlhaUKICAgIGludCBjb3VudCA9IDA7IC8vIOWKoOazlemBi+eul+eahOasoeaVuAogICAgaW50IHJlc3VsdCA9IGZpYm9uYWNjaShuLCBjb3VudCk7CiAKCWNvdXQgPDwgIuiyu+awj+aVuOWIlyAiIDw8IG4gPDwgIiDpoIXnmoTlgLzmmK86ICIgPDwgcmVzdWx0IDw8IGVuZGw7CiAgICBjb3V0IDw8ICLlnKjoqIjnrpfpgY7nqIvkuK3pgLLooYzkuoYiIDw8IGNvdW50IDw8ICLmrKHliqDms5XpgYvnrpfjgIIiIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0K