题目描述

时间限制：1Sec ；内存限制：128MB

内容：

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。

请编程实现在第n年的时候，共有多少头母牛？

输入：

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

输出：

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

样例：

输入

1
2
3
4
2
4
5
0

输出

1
2
3
2
4
6

思路

两种方法：

  • [递归]利用D&C方法，递归函数，分而治之。
  • [迭代]理解题目内容，化繁为简。

！！注意！！结果会超过int范围，要用long int！！

递归法

分而治之，将大问题分解成小问题：

该题目中可以以每头牛为单位进行问题分解，计算一头牛的规律，之后利用递归解决所有牛。

一头牛可以分为两个阶段：

  • 非生育期（三年
  • 生育期（之后

生育期每年可以生产一头新牛，也包含这两个阶段；

假设计算时，一头牛的年龄为n年(n>3)，则前三年可以看做数量1头，之后可以看做1+x1+x2+…

（其中，x为其子代代表的数量）

即：将牛看做一条分支

牛的数量

那么：可以将这代牛的年数设为参数，建立一个函数：

1
2
3
4
5
6
7
8
long int cow(int year){
    long int num=0;		//这一牛分支的牛总数
    if(year<4)return 1;		 //如果小于四年没有生育，数量仅为他自己
    for(int i=0;i<year-3;i++){ //大于3年的每年生育新牛
        num+=cow(i+1);		 //调用自己，参数为总年数-当前年数（新牛年数
    }				//所有牛子代的数量相加
    return num+1;		//返回 其所有子代数量 + 自己
}

再综合条件得出主函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long int add(int);
int main()
{
    int year;
    long int num;
    while(~scanf("%d", &year)){		 //输入年数
        num=0;
        if(year==0){			//为0退出
            break;
        }
        for(;year>0;year--){		 //原母牛每年生育一头牛（包括前三年）
            num+=cow(year-1);		 //所以不是直接调用cow()
        }
        printf("%ld\n",num);		 //打印输出
    }
    return 0;
}

很多题目都可以用D&C方法，简单化解；

迭代法

深刻理解题目：列举出前四年的牛数：

1
1、2、3、4

到第五年时，可以生育的牛的数量为第二年的牛总数（小牛可以在第四年生育）

第五年总牛数为：上一年牛数+新生育牛数 = 第四年+第二年

第六年总牛数为：上一年牛数+新生育牛数 = 第五年+第三年

第七年总牛数为：上一年牛数+新生育牛数 = 第六年+第四年

…

…

以此类推，可以用数列求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    int year;
    long int num;
    long int all[55]={1,2,3}
    do{
        scanf("%d",&year);
        if(year==0){
            break;
        }
    	if(a<4){
        	num = all[year-1];
    	}
    	else{
        for(int i=3;i<year;i++){
        	all[i] = all[i-1] + all[i-3];
      	 }
      	 num = all[year-1];
   	}
        printf("%ld\n",num);
    }while(1);
    return 0;
}

THE END