母牛數(shù)量算法

shiyiming

是不是老師出的題目，你拿到這里來找答案了，這樣可不好，自己做出來才對(duì)

ge126

個(gè)人版的母牛
PS：測(cè)試一下GCC的擴(kuò)展

1. #include <stdio.h>;
   
2. int main()
   
3. {
   
4.   int n;
   
5.   int cow[15]={2,3,4,6,9,13,19,28,41,60,88,129};
   
6.   
   
7.   printf("input n years, from 1\n");
   
8.   scanf("%d", &n);
   
9.   switch(n)
   
10.         {
    
11.      case 0 ...3:
    
12.                   printf("total is %d\n",1);
    
13.          break;
    
14.          case 4 ...15:
    
15.                  printf("total is %ld\n", cow[n-4]);
    
16.          break;
    
17.          default:
    
18.                  printf("Sorry,The Cow is dead!");
    
19.     }
    
20. 
    
21.    return 0;
    
22. }  

復(fù)制代碼

軒轅砍刀

C/C++版的精華也有這樣的東東啊
一年多前的貼子了，好大的坑�。。�！

其實(shí)是Fibonacci斐波那契數(shù)列的變形了，原始的遞進(jìn)間隔是3

  1，1，2，3，5，8，13，21，34…  從第三年起，n(i)=n(i-1)+n(i-2)

現(xiàn)在的間隔改成4，就是

1，1，1，2，3，4，6，9，13…  從第四年起，n(i)=n(i-1)+n(i-3)

如果是5，就是
1，1，1，1，2，3，4，5，7，10，14…  從第五年起，n(i)=n(i-1)+n(i-4)

………………………………………………………………

回頭看間隔為2的情況，顯然從第2年起 n(i)=n(i-1)+n(i-1)

所以，就是設(shè)間隔為非一正整數(shù)step（step為1時(shí)，數(shù)量無限大），就是第step年起開始生BB，則迭代公式為n(i)=n(i-1)+n(i-step+1)


用C++遞歸實(shí)現(xiàn)就是(在Linux g++ 及Windows VC++6和BCB6下編譯通過)：

1. 
   
2. /*-----------------------Fibonacci.h----------------------------*/
   
3. 
   
4. #include <iostream.h>
   
5. 
   
6. class Fibonacci
   
7. {
   
8.   private:
   
9.       unsigned int step; //遞進(jìn)間隔,大于1的正整數(shù)
   
10.       unsigned int year; //要計(jì)算的年數(shù)
    
11.       long number;   //計(jì)算結(jié)果
    
12.       bool mark;  //標(biāo)識(shí)step是否在合理范圍內(nèi)及是否成功調(diào)用Set()；
    
13.   public:
    
14.          Fibonacci(); //構(gòu)造函數(shù)顯示初始化
    
15.       unsigned int Get_year();
    
16.          int  Display(); //輸出計(jì)算結(jié)果
    
17.       void  Set(); //輸入間隔和要計(jì)算的年數(shù)
    
18.       long  Fib_num(unsigned int); //計(jì)算數(shù)列，遞歸用的
    
19. };
    
20. 
    
21. 
    
22. 
    
23. /*-----------------------Fibonacci.cpp----------------------------*/
    
24. 
    
25. 
    
26. #include "Fibonacci.h"
    
27. 
    
28. Fibonacci :: Fibonacci()
    
29. {
    
30.    step = 0;
    
31.    year = 0;
    
32.    number = -1; //標(biāo)識(shí)是否成功調(diào)用Fib_num()
    
33.    mark = 0;
    
34.    cout<< " Fibonacci數(shù)列實(shí)例：假設(shè)一頭母牛在出生后第x年開始每年生下一頭小母牛，且母牛不死亡。則第n年總共有母牛多少頭？"<< endl;
    
35. }
    
36. 
    
37. unsigned int Fibonacci :: Get_year()
    
38. {
    
39.     return(year);
    
40. }
    
41. 
    
42. int Fibonacci :: Display()
    
43. {
    
44.    if(mark&&number != -1)
    
45.      cout<< "假設(shè)一頭母牛在出生后第"<< step<< "年開始每年生下一頭小母牛，且母牛不死亡。\n"<< "則第"<< year<<"年總共有母牛" << number << "頭。"<< endl;
    
46.    else
    
47.      cout<< "接口函數(shù)調(diào)用錯(cuò)誤！請(qǐng)先進(jìn)行數(shù)據(jù)成員設(shè)置Set()和結(jié)果計(jì)算Fib_num()步驟。"<< endl;
    
48.    return(0);
    
49. }
    
50. 
    
51. void Fibonacci :: Set()
    
52. {
    
53.    cout<< "請(qǐng)輸入x，x為大于1的正整數(shù)："<< endl;
    
54.    do
    
55.    {
    
56.     cin >>step;
    
57.           if(step>1)  {mark=1; break;}
    
58.           else  cout<< "請(qǐng)輸入大于1的正整數(shù)。"<< endl;
    
59.    }while(mark);
    
60.    cout << "請(qǐng)輸入n，n為非負(fù)整數(shù)，否則將得到不正確結(jié)果："<< endl;
    
61.    cin >>year;
    
62. }
    
63. 
    
64. long Fibonacci :: Fib_num(unsigned int i)
    
65. {
    
66.    if(mark)
    
67.      {
    
68.        if(i==0) number = 0;
    
69.        else if(i<step) number = 1;
    
70.        else  number = Fib_num(i-1)+Fib_num(i-step+1);  //計(jì)算公式就在這了
    
71.      }
    
72.    else
    
73.      cout<< "接口函數(shù)調(diào)用錯(cuò)誤！請(qǐng)先進(jìn)行數(shù)據(jù)成員設(shè)置Set()步驟。"<< endl;
    
74.    return(number);
    
75. }
    
76. 
    
77. int main()
    
78. {
    
79.     Fibonacci cow;
    
80.     cow.Set();
    
81.     cow.Fib_num(cow.Get_year());
    
82.     cow.Display();
    
83.     return 0;
    
84. }
    
85. 
    

復(fù)制代碼

以上是Fibonacci的遞歸實(shí)現(xiàn)了，如果year很大的話，那效率會(huì)比較低。

如果是非遞歸實(shí)現(xiàn)，可以，定義幾個(gè)記錄變量，目的是記錄n（i-step+1）的值就可以了。不過程序是對(duì)具體的實(shí)例的，通用性很不好的。

要實(shí)現(xiàn)通用程序，可以定義一個(gè)大數(shù)組作為記錄（面向?qū)ο筇匦圆缓茫�、或用鏈表�?shí)現(xiàn)（太麻煩），或者用new動(dòng)態(tài)分配堆對(duì)象變量數(shù)組（最好重載new和delete，避免產(chǎn)生堆碎片而導(dǎo)致程序出錯(cuò)或者效率低下）

[ 本帖最后由 軒轅砍刀 于 2006-3-16 13:34 編輯 ]

star55

用precalculate,就是把你以前計(jì)算出來的值保留在數(shù)組里面，下次用到的時(shí)候就可以直接存取，不必要做重復(fù)的遞歸，算100年以上的話至少可以比你用的時(shí)候少幾十倍。

yutian

F（n）>;=2^(n/2)

afministrator

到底哪個(gè)是對(duì)的呀，
可不可以發(fā)到我的信箱里呀，
我是個(gè)新手呀，
好多地方不明白呀。
我的信箱是      :     fywtaichen@sina.com.cn         
誰寫個(gè)完整的發(fā)到我這里呀，
先謝謝了�。。�！

walkfire

非遞歸算法，反正我算第100年時(shí)基本上沒有費(fèi)什么時(shí)間：
int initCowCount = 1;
int yearInterval = 100;
long cowSum = initCowCount;

long cowCount_0 = 0;        // 剛出生的牛的數(shù)量
long cowCount_1 = 0; // 一歲的牛的數(shù)量
long cowCount_2 = 0;        // 兩歲的牛的數(shù)量
long cowCount_3 = 0;        // 三歲及其以上的牛的數(shù)量

int main(int argc, char* argv[])
{
        cowCount_0 = initCowCount;
        long t1 = 0;
        long t2 = 0;
        long t3 = 0;
        // 計(jì)算牛的數(shù)量
        for(int i=0; i<yearInterval; i++){
                // 如果有剛出生的牛
                if(cowCount_0>;0){
                        t1 = cowCount_0;
                        cowCount_0 = 0;
                }
                // 如果有一歲的牛
                if(cowCount_1>;0){
                        t2 = cowCount_1;
                        cowCount_1=0;
                }
                // 如果有兩歲的牛
                if(cowCount_2>;0){
                        t3=cowCount_2;
                        cowCount_2=0;
                }
                // 如果有三歲及其以上的牛
                if(cowCount_3>;0){
                        cowCount_0=cowCount_3;
                }
                cowCount_1 = t1;
                cowCount_2 = t2;
                cowCount_3 += t3;
               
                cowSum = cowCount_0+cowCount_1+cowCount_2+cowCount_3;
        }//end for

        printf("第%d年后母牛的數(shù)量為%d!\n\t",yearInterval,cowSum);
        return 0;
}

軒轅砍刀

[quote]原帖由 "star55"]用precalculate,就是把你以前計(jì)算出來的值保留在數(shù)組里面，下次用到的時(shí)候就可以直接存取，不必要做重復(fù)的遞歸，算100年以上的話至少可以比你用的時(shí)候少幾十倍。[/quote 發(fā)表：


暈4，我無語(yǔ)了……

麻煩先仔細(xì)看完人家的帖子再發(fā)言。

ericooler

其實(shí)簡(jiǎn)單得很，第n年的數(shù)量是上一年牛的數(shù)量加上3年前牛的數(shù)量，因?yàn)槿�年前的您都在這一年生小牛了，也就是：f(n)=f(n-3)+f(n-1)， 不管遞推還是遞歸都很容易計(jì)算。

terryliu98

原帖由 "aero" 發(fā)表：
4周歲開始生小牛：10年：10，30年：6272
3周歲開始生小牛：10年：19，30年：39865
PS：看哪，這就是晚生優(yōu)生的結(jié)果。

再加一條,還應(yīng)該讓牛也計(jì)劃生育,情況就會(huì)好多了......