e357: 遞迴函數練習

2019-09-06

內容

定義一個函數 F(x)，

若 x = 1, 則 F(x) = 1
若 x 為偶數，則 F(x) = F(x/2)

其餘狀況，F(x) = F(x - 1) + F(x + 1)

輸入

輸入只有一行，其中包含一個正整數 x (1 <= x <= 2000000)。

6

輸出

輸出只有一行，其中包含一個正整數 F(x)。

2

解題思路

簡單的遞迴，依照題目實作即可。

完整程式碼

AC (2ms, 120KB)

#include <stdio.h>

int F(int x)
{
    if (x & 1)
        return x == 1 ? 1 : F(x - 1) + F(x + 1);
    else
        return F(x / 2);
}

int main()
{
    int n;
    scanf(" %d", &n);
    printf("%d", F(n));
    return 0;
}