母牛数量算法

stuff990

不知道是不是我想的太简单了，大家看看我的（程序来不急写了）

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

loveguohuasai

原帖由 "小飞爱使申华" 发表：


可你这也是递归啊！只要自己调自己就算了。

   

我觉得一定是要递归的，不用递归的话我觉得很难。

zlzj2010

我简单写了个递归算法,不知可以么?

我是按牛第四年开始生的,即第四年应该有5头牛,改了一下,应该没什么问题了!

1.    
   
2. long fun(int n){
   
3. if (n>;3)
   
4.    return fun(n-1)+fun(n-3);
   
5. else if(n==3)
   
6.    return 1;
   
7. else if(n==2)
   
8.    return 1;
   
9. else if(n=1)
   
10.    return 1;
    
11. }
    
12. main (){
    
13. int n;
    
14. printf("input n");
    
15. scanf("%d",&n);
    
16. printf("the result:%ld",fun(n));
    
17. }
    

复制代码

zlzj2010

非递归算法:

1. 
   
2. long fun(int n){
   
3. long a1=1;
   
4. long a2=1;
   
5. long a3=1;
   
6. long a4=1;
   
7. int i=0;
   
8. long sum=0;
   
9. for (i=4;i<n+1;i++){
   
10.    a4=a1+a3;
    
11.    a1=a2;a2=a3;a3=a4;
    
12. }
    
13. sum=a4;
    
14.    return sum;
    
15. }
    
16. main (){
    
17. int n;
    
18. printf("input n");
    
19. scanf("%d",&n);
    
20. printf("the result:%ld",fun(n));
    
21. }
    

复制代码

unicorns

我的非递归算法，不过不是能带参数的，如果想带参数也可以
那就要用链表了，但是算法是一样的，存储方式不同而已。

1. 
   
2. main (){
   
3.         unsigned long year[100] ;//每年出生的牛数量
   
4.         unsigned long ulResult ;
   
5.         unsigned long sum ;//每年的育龄母牛数量
   
6.         int i,j ;
   
7.        
   
8.         sum = 0 ;
   
9.         for (i = 0; i < 100; i ++){
   
10.                 if (i == 0){
    
11.                         year[i] = 1 ;
    
12.                         continue ;
    
13.                 }
    
14.                 if (i - 3 < 0){
    
15.                         year[i] = 0 ;
    
16.                 }else{
    
17.                         for (j = 0; j <= i -3; j ++)
    
18.                                 sum += year[j] ;
    
19.                         year[i] = sum;
    
20.                         sum = 0 ;
    
21.                 }
    
22.         }
    
23.        
    
24.         for (i = 0; i < 100; i ++)
    
25.                 ulResult += year[i] ;
    
26.        
    
27.         printf ("ulResult = [%lu]", ulResult) ;
    
28. }
    

复制代码

最后结果是234467045
是100年的，用了不到1秒时间，呵呵

unicorns

还可以优化一下

1. 
   
2. main (){
   
3.         unsigned long year[100] ;
   
4.         unsigned long ulResult ;
   
5.         unsigned long sum ;
   
6.         int i,j ;
   
7.        
   
8.         sum = 0 ;
   
9.                 year[0] = 1 ;
   
10.                 year[1] = 0 ;
    
11.                 year[2] = 0 ;  
    
12.         for (i = 3; i < 100; i ++){
    
13.                 sum += year[i - 3] ;
    
14.                 year[i] = sum ;
    
15.         }
    
16.        
    
17.         for (i = 0; i < 100; i ++)
    
18.                 ulResult += year[i] ;
    
19.        
    
20.         printf ("ulResult = [%lu]", ulResult) ;
    
21. }
    

复制代码

   

复杂度只有2n

li2002

好像结果有问题吧，不到100年数值早溢出了，不相信算算60年的数量比100年的多：3，808，901，426 >;234，467，045

aero

我的递归算法：

1. #include <stdio.h>;
   
2. 
   
3. int inc(int);
   
4. 
   
5. int fun(int n){                        /*计算第n年有多少牛的函数。*/
   
6.         if ( n==1 ) return 1;
   
7.         return inc(n)+fun(n-1);
   
8. }
   
9. 
   
10. int inc(int n){                        /*计算第n年牛的增长率的函数*/
    
11.         if ( n<5 )                return 0;
    
12.         else if ( n==5 )        return 1; /*满4周岁的时候开始生小牛，即第5年的增长率为1。*/
    
13.         else                         return inc(n-1)+inc(n-4);
    
14. }
    
15. 
    
16. int main(){
    
17.         int n;
    
18.         printf("\ninput n:");
    
19.         scanf("%d",&n);
    
20.         printf("result:%d\n",fun(n));
    
21. }
    
22. 
    

复制代码

我的非递归算法：

1. #include <stdio.h>;
   
2. 
   
3. 
   
4. long int fun(int n){
   
5.         long int i_born=0;        /*满1周岁的牛的数目，下面的类似*/
   
6.         long int ii_born=0;
   
7.         long int iii_born=0;
   
8.         long int iv_born=0;
   
9.         long int can_born=0;        /*今年能生产的牛的数目*/
   
10.         long int sum=1;                /*总数*/
    
11.         int i;
    
12.         for (i=0;i<n;i++) {
    
13.                 can_born+=iv_born;
    
14.                 sum+=can_born;
    
15.                 iv_born=iii_born;
    
16.                 iii_born=ii_born;
    
17.                 ii_born=i_born;
    
18.                 i_born=can_born;
    
19.                 if (!i) i_born=1;/*第一年的时候有1头牛满一岁*/
    
20.         }
    
21.         return sum;
    
22. }
    
23. 
    
24. int main(){
    
25.         int n;
    
26.         printf("\ninput n:");
    
27.         scanf("%d",&n);
    
28.         printf("result:%ld\n",fun(n));
    
29. }
    
30. 
    

复制代码

目前有两种理解，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的疑问，其实是想说这也是一种递归，后来发现表达得有歧意，立马在楼下又加了一句，呵呵。

loveguohuasai

原帖由 "aero" 发表：
目前有两种理解，3周岁开始生小牛和4周岁开始生小牛，姑且都算对的话。

“小飞爱使申华”的做法是对的，很巧妙的只用了一个递归就完成了，他的做法是3周岁开始生小牛。

loveguohuasai的做法是错误的，牛的数目..........

   

我想问一下，我知道第一种我是想错了的，第二种也错吗？我觉得不可能错，其实就是一句话可以把它解释清楚：今年的数量是去年的数量加上四年前（就是f(n-3))的数量（因为四年前的牛在今年开始生牛，知道这个算法不是很简单吗？就是要用到递归。我觉得这样的算法绝对是最简单的了。