母牛數量算法

loveguohuasai

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

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

loveguohuasai的做法是錯誤的，牛的數目..........

   

我沒有發覺你也提到那條公式，f(n)=f(n-1)+f(n-3)(或者n-4)，這樣本來就是遞歸了，不用遞歸簡直是犯賤啊 。一個遞歸，都不用幾句就搞定了。

ehewang

#include<stdio.h>;
void main()
{
        long int f[100];
        int i;
        f[0]=1;f[1]=1;f[2]=1;
        for(i=3;i<100;i++)
                f=f[i-1]+f[i-3];
        printf("%ld",f[99]);
}

zlzj2010

[quote]原帖由 "aero"]zlzj2010的做法里有一個致命的錯誤，并不是fun(n)=fun(n-1)+fun(n-3)，是的確，fun(n-3)的牛在n年可以生牛了，但并不是僅僅這些�？梢陨�啊，fun(n-1)里也有很大一部分�？梢栽诘趎年繼續生小牛啊，你的程序里把這一部分漏掉了[/quote 發表：
     

我覺得地fun(n)年能生小牛的牛的不正是fun(n-3)么？fun(n-1)里是有�？梢陨�小牛，但它在第n年能生的剛好是fun(n-3)呀，

不只我這思路是否正確？

unicorns

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

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

loveguohuasai的做法是錯誤的，牛的數目..........

   

PFPF,沒想到100就能溢出啊
這些牛真的太牛了。

aero也比較牛。呵呵

loveguohuasai

原帖由 "zlzj2010" 發表：
   

我覺得地fun(n)年能生小牛的牛的不正是fun(n-3)么？fun(n-1)里是有�？梢陨�小牛，但它在第n年能生的剛好是fun(n-3)呀，

不只我這思路是否正確？

   


你不明白嗎？這就是一個總局的想法，拋開其他的只在一個四年內考慮。
“今年的數量等于去年加上四年前的數量“，絕對是這樣，否則要遞歸做什么？
像你說的，（n-1)年也有生牛，但不是在n年啊，在n+2年才生的，意思你也說明白了，在今年（第n年）可以生牛的牛數就是n-3年的數（f(n-3))，不就是f(n)=f(n-1)+f(n-3).絕對沒有錯

小飛愛使申華

對，如果是f(n)=f(n-1)+f(n-3).，那程序更簡單了（main函數不變）：

1. 
   
2. long num_cow(int n){
   
3.    return (n < 4) ? 1 : num_cow(n-1) + num_cow(n-3);
   
4. }
   

復制代碼

chdonald

呵呵，分析得太好了，我當時的做法，沒放上來，不過也是同樣的問題：遞歸效率低，而且數據溢出，不知道我的結果對不對：30年 39865頭
PS：牛不會活100歲的：）

1. #include <stdio.h>;
   
2. 
   
3. int cow(int n)
   
4. {
   
5.   unsigned long sum = 1, i;
   
6. 
   
7.   if (n <= 3) sum += 0;
   
8.   else {
   
9.         for (i = 4; i <= n; i++)
   
10.                 sum += cow(i-3);
    
11.   }
    
12.   return(sum);
    
13. }
    
14. 
    
15. main()
    
16. {
    
17.   int n;
    
18. 
    
19.   printf("input n years, from 1\n");
    
20.   scanf("%d", &n);
    
21.   printf("total is %ld\n", cow(n));
    
22. }  

復制代碼

wangz

原帖由 "chdonald" 發表：
呵呵，分析得太好了，我當時的做法，沒放上來，不過也是同樣的問題：遞歸效率低，而且數據溢出，不知道我的結果對不對：30年 39865頭
PS：牛不會活100歲的：）
#include <stdio.h>;

int cow(int n)
{
  ..........

  
30年我只算出328頭，怎么差這么多？？
大家算個小一點的，比如10年，看看結果怎樣，10年可以手工算出來： 18頭。
大家看看自己的算法對不對！

zlzj2010

原帖由 "wangz" 發表：
  
30年我只算出328頭，怎么差這么多？？
大家算個小一點的，比如10年，看看結果怎樣，10年可以手工算出來： 18頭。
大家看看自己的算法對不對！

   

不對把,10年應該是19頭,

30年是39865

loveguohuasai

[quote]原帖由 "chdonald"][/quote 發表：
     

n=30,得到39865，對