母牛的故事 （C语言代码）

解题思路:

注意事项:

参考代码:

题目描述

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

输入

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

n=0表示输入数据的结束，不做处理。                                                          

输出

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

每个输出占一行。

样例输入

2 4 5 0

样例输出

2 4 6

解题思路1

该题规律：

第一年只有一头牛，第五年共有前三年来生的牛总数加初始牛加上第二年牛新生的一头牛

即第5年 = 1+3+1+1 = 6

根据规律

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

参考代码：

（C++版）

#include<iostream>

using namespace std;

int main()

{

   int n, i;

   int f[55] = { 0,1,2,3 };  //f[0]=0,f[1]=1,f[2]=2,f[3]=3

   for (i = 4; i < 55; i++)

       f[i] = f[i - 1] + f[i - 3];

   while (cin >> n && n != 0)  //输入 n 的值，且 n 不等于0，则进入，否则退出

   {

       cout << f[n] << endl;

   }

   return 0;

}

(C版）

#include<stdio.h>

int main(void)

{

int n,i;

int f[55] = {0,1,2,3};

for(i=4;i<55;i++)

f[i] = f[i-1]+f[i-3];

while(scanf("%d",&n)&&n!=0)

{

printf("%d\n",f[n]);

}

return 0;

}

-----------------------------------------------

解题思路2

设可以生小牛的牛为成年牛audlt，

刚出生的牛年龄为1岁

第二年2岁

依次推到成年为止

n年后所有牛总数all = 成年牛+1岁+2岁+3岁

注意每次输入n以后，各变量初始化为0，进行循环叠加运算

注意该思路运算逻辑是进行n-1次循环运算，所以当循环次数i为0时，i<n  当循环次数i设为0时，i<n-1

参考代码:

C语言版

#include<stdio.h>

int main()

{

int adult,one,two,three,all,i,n;

while(scanf("%d",n)!=EOF)

{

if(n==0)

break;

for(adult=1,one=0，two=0，three=0，i=1;i<n;i++)

{

adult+=three;

three=two;

two=one;

one=adult;

}

all=adult+three+two+one;

printf("%d\n",all);

}

return 0;

}

C++语言版本

#include<iostream>

int main(void)

{

using namespace std;

int adult,one,two,three,all,i,n;

while(cin>>n&&n)

{

for(adult=1,one=0,two=0,three=0,i=0;i<n-1;i++)

{

adult += three;

three = two;

two = one;

one = adult;

}

all = adult + three + two + one;

cout<<all<<endl;

}

return 0;

}

--------------------------------------------------------------------------

解题思路3

通过递推可得数字 1 2 3 4 6 9 13 19 28

考虑数组太浪费空间

追寻这些数字之间的规律，可发现4=1+3 ，6=2+4，9=3+6,13=4+9,19=9+13,28=9+19

可以在原有已获得数字中进行加减运算得到接下去的数字

我们给定一个含有3个空间的数组num,进行初始化1，2，3

使num[0]=num[0]+num[2];

num[1]=num[0]+num[1];

num[2]=num[1]+num[2];

如果n为2时，直接输出num[1];

如果n为3时，直接输出num[2];

如果n为4时，进行一次运算后，输出n[0];

如果n为8时，进行两次运算后，输出n[1];

由此我们可以得出结论，当n小于等于3时，无需运算

当n大于3的m倍时，需要进行m次运算

所以循环i初始化为1

控制循环条件i<3.0

当n为3的m倍，进行了m-1次运算，输出num[2];

当n大于3的m倍时，进行了m次运算，输出num[(n-1)%3]

参考代码：

C语言版

#include <stdio.h>

int main()

{

int n,i;

while(scanf("%d",&n)&&n)

{

int num[3]={1,2,3};

for(i=1;i<n/3.0;i++)

{

num[0]+=num[2];

num[1]+=num[0];

num[2]+=num[1];

}

printf("%d\n",num[(n-1)%3]);

}

return 0;

}

C++语言版

#include<iostream>

int main(void)

{

int n,i;

using namespace std;

while(cin>>n&&n)

{

int num[3]={1,2,3};

for(i=1;i<n/3.0;i++)

{

num[0]+=num[2];

num[1]+=num[0];

num[2]+=num[1];

}

cout<<num[(n-1)%3]<<endl;

}

return 0;

}

-------------------------------------------------------------------------

解题思路4

使用递归法

（不建议使用，大数需要耗费大量运算时间）

参考代码：

#include <iostream>

using namespace std;

int fun(int n);

int main(void)

{

int n;

while(cin>>n&&n!=0)

{

cout<<fun(n)<<endl;

}

return 0;

}

int fun(int n)

{

if(n<=4)

{

return n;

}

else

{

return fun(n-1)+fun(n-3);

}

}