母牛數(shù)量算法

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:循環(huán)b直到n, 牛的總數(shù)就是1+2+3+4+5

loveguohuasai

原帖由 "小飛愛使申華" 發(fā)表：


可你這也是遞歸啊！只要自己調自己就算了。

   

我覺得一定是要遞歸的，不用遞歸的話我覺得很難。

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

我的非遞歸算法，不過不是能帶參數(shù)的，如果想帶參數(shù)也可以
那就要用鏈表了，但是算法是一樣的，存儲方式不同而已。

1. 
   
2. main (){
   
3.         unsigned long year[100] ;//每年出生的牛數(shù)量
   
4.         unsigned long ulResult ;
   
5.         unsigned long sum ;//每年的育齡母牛數(shù)量
   
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

還可以優(yōu)化一下

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年數(shù)值早溢出了，不相信算算60年的數(shù)量比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年有多少牛的函數(shù)。*/
   
6.         if ( n==1 ) return 1;
   
7.         return inc(n)+fun(n-1);
   
8. }
   
9. 
   
10. int inc(int n){                        /*計算第n年牛的增長率的函數(shù)*/
    
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周歲的牛的數(shù)目，下面的類似*/
   
6.         long int ii_born=0;
   
7.         long int iii_born=0;
   
8.         long int iv_born=0;
   
9.         long int can_born=0;        /*今年能生產的牛的數(shù)目*/
   
10.         long int sum=1;                /*總數(shù)*/
    
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的做法是錯誤的，牛的數(shù)目不是等差的增長的，他的增長數(shù)率越來越快，其實它的增長速率的增長率也是越來越快的，如果把這些值看成是連續(xù)的，應該是一個無限階可導的函數(shù)，并不是等差的。用筆算，把總數(shù)和增長率都列出來，算到15年左右就能看出來了。

還有“小飛愛使申華”對loveguohuasai的疑問，我覺得算是遞歸啊，一種間接遞歸，怎么不算遞歸呢？

stuff990的想法是對的，是應該分出小于4歲的牛多大的各有多少，然后計算，這也正是我的非遞歸算法的思想。但是，如果仔細分析就會發(fā)現(xiàn)，牛的總數(shù)并不是一個等差數(shù)列那樣簡單。

zlzj2010的做法里有一個致命的錯誤，并不是fun(n)=fun(n-1)+fun(n-3)，是的確，fun(n-3)的牛在n年可以生牛了，但并不是僅僅這些�？梢陨�啊，fun(n-1)里也有很大一部分�？梢栽诘趎年繼續(xù)生小牛啊，你的程序里把這一部分漏掉了。

unicorns的做法是正確的，他是以牛3周歲開始生小牛算的，但是計算100年的確有問題，正如li2002所說，因為年份大的時候每年增長的牛的數(shù)量大大超乎了想象，造成了數(shù)組的溢出，這一點把year數(shù)組打印出來就可以很容易看出來，有很多的負值。如果計算50年就不會造成溢出。我的非遞歸算法德的結果和unicorns的一樣，個人覺得這組結果就是正確的了。如下：（也包括了100年的錯誤結果，unsigned long int是系統(tǒng)給的最長的數(shù)據了，如果要計算準確的話得自己構造數(shù)據類型。麻煩了，沒做，如果遞歸的話，也應該是這個錯誤結果。雖然是錯誤的，也有一定的參考價值。）
3周歲開始生牛，50年：83316385，100年：234467045
4周歲開始生牛，50年：3951206， 100年：566194214
從兩個100年的結果也能看出來溢出的錯誤。

我的非遞歸程序的想法和stuff990的想法是類似的，我是以4周歲開始生小牛為準，用了4個變量統(tǒng)計各個時期小于4周歲（不可生育牛）的數(shù)量，來計算每年可生育牛的數(shù)量和牛的總數(shù)的。

而公式，我覺得如果以4周歲開始生小牛為準的話（3周歲開始的可以類推，程序也很好改），應該是：
f(n)=f(n-1)+inc(n);                /*去年牛的數(shù)量，和今年增長的牛的數(shù)量的和*/
inc(n)=inc(n-1)+inc(n-4);        /*去年增長的數(shù)量（生這些牛的牛今年還可以生），和新成熟的可以生牛的牛的數(shù)量（就是4年以前出生的牛）*/
我的非遞歸算法就是用這兩個公式做的，不過計算一個年份的時候要兩次陷入inc的遞歸，復雜度很高，效率很差。覺得“小飛愛使申華”的遞歸算法很好�！盎疑�軌跡”的遞歸算法也很好，我就是在這個遞歸算法的啟示下寫出的我的非遞歸算法。

還有，就是大家貼上來的程序最好能多寫點注釋，方便閱讀和理解。

最后，感謝loveguohuasai提出這么好的問題，也非常榮幸能在這里和大家這么高興的討論問題，言辭之中有得罪的地方還請見諒。

小飛愛使申華

aero老兄不錯，碼了不少字，分析得也很有理，好！
我還正愁這么一大堆code，也不知對錯，很容易誤人子弟的，現(xiàn)在好了，有人出來評判一下，再次感謝。
PS：我對loveguohuasai的疑問，其實是想說這也是一種遞歸，后來發(fā)現(xiàn)表達得有歧意，立馬在樓下又加了一句，呵呵。

loveguohuasai

原帖由 "aero" 發(fā)表：
目前有兩種理解，3周歲開始生小牛和4周歲開始生小牛，姑且都算對的話。

“小飛愛使申華”的做法是對的，很巧妙的只用了一個遞歸就完成了，他的做法是3周歲開始生小牛。

loveguohuasai的做法是錯誤的，牛的數(shù)目..........

   

我想問一下，我知道第一種我是想錯了的，第二種也錯嗎？我覺得不可能錯，其實就是一句話可以把它解釋清楚：今年的數(shù)量是去年的數(shù)量加上四年前（就是f(n-3))的數(shù)量（因為四年前的牛在今年開始生牛，知道這個算法不是很簡單嗎？就是要用到遞歸。我覺得這樣的算法絕對是最簡單的了。