ZeroJudge E357: 遞迴函數練習

題目敘述

每筆輸入只有一個大於0的正整數N，要求輸出 F(N)。F(N) 解釋如下：

如果N = 1，則 F(N) = 1。

如果N是偶數，則 F(N) = F(N/2)。

如果N是奇數且不等於1時，F(N) = F(N+1) + F(N-1)。

範例輸入

6

範例輸出

2

解題思路

本題可以寫一個遞迴函式，終止的條件是當N = 1時就return N，然後將偶數及奇數的判斷式寫好然後cout遞迴(N)就可以了 (詳情請見範例程式碼)。

解題程式碼如下 (僅供參考)：

#include <iostream>
using namespace std;

int calc (int N)
{
    if (N == 1) return 1;
    if (N % 2 == 0) return calc(N/2);
    else return calc(N-1)+calc(N+1);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    cout << calc(N) << endl;
}