#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

MTA=

10