ACM题解-母牛的故事

题目

Problem Description

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

Sample Input

2
4
5
0

Sample Output

2
4
6

题目分析

类似于斐波纳契数列，可得递推函数

f(n)=n n<=4

f(n)=f(n-1) + f(n-3) n>4

可用方法

• 递推
• 递归
• 数组

代码

递推（需要理解）

#include <stdio.h>
int main()
&#123;
int n,i;
while(scanf("%d",&n)&&n)
&#123;
int num[3]=&#123;1,2,3&#125;;
for(i=1;i<n/3.0;i++)//注意浮点数3.0,并且由于在第4年成熟所以3年一循环
&#123;
num[0]+=num[2];//第4年
num[1]+=num[0];//第5年
num[2]+=num[1];//第6年
&#125;
printf("%d\n",num[(n-1)%3]);//注意是n-1

&#125;

return 0;

&#125;

---

递归(思路很清晰的一种解法)

#include <stdio.h>
 
// 递推式 f(n) = n n<=4，f(n) = f(n-1) + f(n-3) n>4
int cow(int n)
&#123;
    if(n <= 4)
        return n;
    else
        return cow(n-1) + cow(n-3);
&#125;
 
int main(void)
&#123;
    int n;
 
    while(scanf("%d", &n) != EOF) &#123;
        // 判定结束条件
        if(n == 0)
            break;
 
        // 计算并输出结果
        printf("%d\n", cow(n));
    &#125;
 
    return 0;
&#125;
--------------------- 
作者：海岛Blog 
来源：CSDN 
原文：https://blog.csdn.net/tigerisland45/article/details/51772927 
版权声明：本文为博主原创文章，转载请附上博文链接！

---

数组(运用数学思想）

当年母牛生下的小牛与几年前的母牛数（也就是当年的成熟牛）是相等的

#include<stdio.h>
int main()&#123;
    int n,count=0;
    int i;
    while(scanf("%d",&n) == 1)
    &#123;
        int a[56];
        for(i=1;i<56;i++)
        &#123;
            if(i<=4)
                a[i]=i;
            else
                a[i]=a[i-1]+a[i-3];//第一年生的小牛在第四年成熟了
        &#125;
    printf("%d\n",a[n])
    &#125;
    return 0;
&#125;

---

总结

注意找出项与项之间的关系，可在草稿纸上进行推演

---