[递归]母牛的故事-题解（C语言代码）

解题思路:

根据题意和输入输出样例，可以列出如下表格：

再联想一下斐波那契数列，不难发现：f(n) = f(n-1) + f(n-3)    (n >= 3)

可以采用递归的方式解答，也可以采用迭代大方式。

(吐槽一下：题意的年初、年头属实把我搞蒙了)

注意事项：

- 数组下标从0开始

- 递归方法求解，需要记录每次计算的结果，减少重复计算

参考代码：

1.迭代代码:

#include<stdio.h>

#define N 55

int main() {
    int n, a[55] = { 0 };
    
    a[0] = 1, a[1] = 2, a[2] = 3;
    
    for(int i = 3; i < N; ++i) {
        a[i] = a[i - 1] + a[i - 3];
    }
    
    while(scanf("%d", &n) && n > 0) {
        printf("%d\n",a[n - 1]);
    }
    
    return 0;
}

2.递归代码：

#include<stdio.h>

#define N 55

int a[N] = { 0 };

int f(n) {
    if(a[n] != 0) {
        return a[n];
    }
    
    a[n] = f(n - 1) + f(n - 3);
    
    return a[n];
}

int main() {
    int n;
    
    a[0] = 1, a[1] = 2, a[2] = 3;
    
    while(scanf("%d", &n) && n > 0) {
        printf("%d\n", f(n - 1));
    }
    
    return 0;
}