母牛数量算法
不知道是不是我想的太简单了，大家看看我的（程序来不急写了）A:分为5类: 1。生的生牛 2。一年生牛 3。2年生牛，4。3年生牛 5多产的牛（一年生一头^_^）
B:每过一年 1－>;2 ,2->;3, 3->;4, 5=5+3; 1=5+3;(牛长大一岁,第5类生出小牛)
c:循环b直到n, 牛的总数就是1+2+3+4+5
母牛数量算法
原帖由 "小飞爱使申华" 发表：可你这也是递归啊！只要自己调自己就算了。
我觉得一定是要递归的，不用递归的话我觉得很难。
母牛数量算法
我简单写了个递归算法,不知可以么?我是按牛第四年开始生的,即第四年应该有5头牛,改了一下,应该没什么问题了!
long fun(int n){
if (n>;3)
return fun(n-1)+fun(n-3);
else if(n==3)
return 1;
else if(n==2)
return 1;
else if(n=1)
return 1;
}
main (){
int n;
printf("input n");
scanf("%d",&n);
printf("the result:%ld",fun(n));
}
母牛数量算法
非递归算法:long fun(int n){
long a1=1;
long a2=1;
long a3=1;
long a4=1;
int i=0;
long sum=0;
for (i=4;i<n+1;i++){
a4=a1+a3;
a1=a2;a2=a3;a3=a4;
}
sum=a4;
return sum;
}
main (){
int n;
printf("input n");
scanf("%d",&n);
printf("the result:%ld",fun(n));
}
母牛数量算法
我的非递归算法，不过不是能带参数的，如果想带参数也可以那就要用链表了，但是算法是一样的，存储方式不同而已。
main (){
unsigned long year ;//每年出生的牛数量
unsigned long ulResult ;
unsigned long sum ;//每年的育龄母牛数量
int i,j ;
sum = 0 ;
for (i = 0; i < 100; i ++){
if (i == 0){
year = 1 ;
continue ;
}
if (i - 3 < 0){
year = 0 ;
}else{
for (j = 0; j <= i -3; j ++)
sum += year ;
year = sum;
sum = 0 ;
}
}
for (i = 0; i < 100; i ++)
ulResult += year ;
printf ("ulResult = [%lu]", ulResult) ;
}
最后结果是234467045
是100年的，用了不到1秒时间，呵呵
母牛数量算法
还可以优化一下main (){
unsigned long year ;
unsigned long ulResult ;
unsigned long sum ;
int i,j ;
sum = 0 ;
year = 1 ;
year = 0 ;
year = 0 ;
for (i = 3; i < 100; i ++){
sum += year ;
year = sum ;
}
for (i = 0; i < 100; i ++)
ulResult += year ;
printf ("ulResult = [%lu]", ulResult) ;
}
复杂度只有2n
母牛数量算法
好像结果有问题吧，不到100年数值早溢出了，不相信算算60年的数量比100年的多：3，808，901，426 >;234，467，045母牛数量算法
我的递归算法：#include <stdio.h>;
int inc(int);
int fun(int n){ /*计算第n年有多少牛的函数。*/
if ( n==1 ) return 1;
return inc(n)+fun(n-1);
}
int inc(int n){ /*计算第n年牛的增长率的函数*/
if ( n<5 ) return 0;
else if ( n==5 ) return 1; /*满4周岁的时候开始生小牛，即第5年的增长率为1。*/
else return inc(n-1)+inc(n-4);
}
int main(){
int n;
printf("\ninput n:");
scanf("%d",&n);
printf("result:%d\n",fun(n));
}
我的非递归算法：
#include <stdio.h>;
long int fun(int n){
long int i_born=0; /*满1周岁的牛的数目，下面的类似*/
long int ii_born=0;
long int iii_born=0;
long int iv_born=0;
long int can_born=0; /*今年能生产的牛的数目*/
long int sum=1; /*总数*/
int i;
for (i=0;i<n;i++) {
can_born+=iv_born;
sum+=can_born;
iv_born=iii_born;
iii_born=ii_born;
ii_born=i_born;
i_born=can_born;
if (!i) i_born=1;/*第一年的时候有1头牛满一岁*/
}
return sum;
}
int main(){
int n;
printf("\ninput n:");
scanf("%d",&n);
printf("result:%ld\n",fun(n));
}
目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。
“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。
loveguohuasai的做法是错误的，牛的数目不是等差的增长的，他的增长数率越来越快，其实它的增长速率的增长率也是越来越快的，如果把这些值看成是连续的，应该是一个无限阶可导的函数，并不是等差的。用笔算，把总数和增长率都列出来，算到15年左右就能看出来了。
还有“小飞爱使申华”对loveguohuasai的疑问，我觉得算是递归啊，一种间接递归，怎么不算递归呢？
stuff990的想法是对的，是应该分出小于4岁的牛多大的各有多少，然后计算，这也正是我的非递归算法的思想。但是，如果仔细分析就会发现，牛的总数并不是一个等差数列那样简单。
zlzj2010的做法里有一个致命的错误，并不是fun(n)=fun(n-1)+fun(n-3)，是的确，fun(n-3)的牛在n年可以生牛了，但并不是仅仅这些牛可以生啊，fun(n-1)里也有很大一部分牛可以在第n年继续生小牛啊，你的程序里把这一部分漏掉了。
unicorns的做法是正确的，他是以牛3周岁开始生小牛算的，但是计算100年的确有问题，正如li2002所说，因为年份大的时候每年增长的牛的数量大大超乎了想象，造成了数组的溢出，这一点把year数组打印出来就可以很容易看出来，有很多的负值。如果计算50年就不会造成溢出。我的非递归算法德的结果和unicorns的一样，个人觉得这组结果就是正确的了。如下：（也包括了100年的错误结果，unsigned long int是系统给的最长的数据了，如果要计算准确的话得自己构造数据类型。麻烦了，没做，如果递归的话，也应该是这个错误结果。虽然是错误的，也有一定的参考价值。）
3周岁开始生牛，50年：83316385，100年：234467045
4周岁开始生牛，50年：3951206， 100年：566194214
从两个100年的结果也能看出来溢出的错误。
我的非递归程序的想法和stuff990的想法是类似的，我是以4周岁开始生小牛为准，用了4个变量统计各个时期小于4周岁（不可生育牛）的数量，来计算每年可生育牛的数量和牛的总数的。
而公式，我觉得如果以4周岁开始生小牛为准的话（3周岁开始的可以类推，程序也很好改），应该是：
f(n)=f(n-1)+inc(n); /*去年牛的数量，和今年增长的牛的数量的和*/
inc(n)=inc(n-1)+inc(n-4); /*去年增长的数量（生这些牛的牛今年还可以生），和新成熟的可以生牛的牛的数量（就是4年以前出生的牛）*/
我的非递归算法就是用这两个公式做的，不过计算一个年份的时候要两次陷入inc的递归，复杂度很高，效率很差。觉得“小飞爱使申华”的递归算法很好。“灰色轨迹”的递归算法也很好，我就是在这个递归算法的启示下写出的我的非递归算法。
还有，就是大家贴上来的程序最好能多写点注释，方便阅读和理解。
最后，感谢loveguohuasai提出这么好的问题，也非常荣幸能在这里和大家这么高兴的讨论问题，言辞之中有得罪的地方还请见谅。
母牛数量算法
aero老兄不错，码了不少字，分析得也很有理，好！我还正愁这么一大堆code，也不知对错，很容易误人子弟的，现在好了，有人出来评判一下，再次感谢。
PS：我对loveguohuasai的疑问，其实是想说这也是一种递归，后来发现表达得有歧意，立马在楼下又加了一句，呵呵。
母牛数量算法
原帖由 "aero" 发表：目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。
“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。
loveguohuasai的做法是错误的，牛的数目..........
我想问一下，我知道第一种我是想错了的，第二种也错吗？我觉得不可能错，其实就是一句话可以把它解释清楚：今年的数量是去年的数量加上四年前（就是f(n-3))的数量（因为四年前的牛在今年开始生牛，知道这个算法不是很简单吗？就是要用到递归。我觉得这样的算法绝对是最简单的了。