母牛數(shù)量算法

hoxide

那就更有趣了
比如每個(gè)年齡的牛按一定比例死掉，
小牛夭折，高齡產(chǎn)婦，
最重要的是公牛跑到哪兒去了，
母牛會(huì)自交�。�

aero

在下去就變成養(yǎng)牛場(chǎng)的模擬軟件了，是不是算一個(gè)項(xiàng)目啊。^_^

hoxide

算阿，很有趣的。等有錢(qián)了我買(mǎi)個(gè)農(nóng)場(chǎng)，就用這個(gè)。
大家努力啊

topmint

1. START
   
2.         LEA GR1,1 ;f(n-1)
   
3.         LEA GR2,1 ;f(n-2)
   
4.         LEA GR3,1 ;f(n-3)
   
5.         LEA GR4,3 ;年數(shù) or 結(jié)果
   
6.         ST GR4,Y
   
7. LOOP         LD GR4,Y
   
8.         CPA GR4,YEAR
   
9.         JPZ FINISH
   
10.         LEA GR4,1,GR4
    
11.         ST GR4,Y
    
12.         ST GR1,D
    
13.         ADD GR3,D
    
14.         ST GR3,D
    
15.         LEA GR3,0,GR2
    
16.         LEA GR2,0,GR1
    
17.         LD GR4,D
    
18.         LEA GR1,0,GR4
    
19.         JMP LOOP
    
20.                 ST GR4,NUM
    
21. FINISH        EXIT
    
22. YEAR         DC 10
    
23. Y        DS 1               
    
24. D        DS 1
    
25. NUM         DS 1       
    
26.         END

復(fù)制代碼

pupilzeng

1. 
   
2. #include <iostream>;
   
3. #include <vector>;
   
4. #include <cstdlib>;
   
5. using namespace std;
   
6. 
   
7. int
   
8. main(int argc, char** argv)
   
9. {
   
10.         if(argc != 2)
    
11.         {
    
12.                 exit(1);
    
13.         }
    
14.         int year = atoi(argv[1]);
    
15.         vector<long long>; count(year, 1);
    
16.         for ( int i = 2; i < year; i ++)
    
17.                 count[i + 1] = count[i] + count[i - 2];
    
18.         cout << "In the " << year <<"th year, there are(is) "
    
19.              << count[year - 1] << " cows\n";
    
20. }
    

復(fù)制代碼

關(guān)鍵就在那個(gè)for循環(huán)。
就是f(n) = f(n - 1) + f(n - 3) 的實(shí)現(xiàn)。[/code]

pupilzeng

1. 
   
2. #include <deque>;
   
3. #include <cstdlib>;
   
4. #include <iostream>;
   
5. using namespace std;
   
6. 
   
7. int
   
8. main(int argc, char** argv)
   
9. {
   
10.         if(argc != 2)
    
11.         {
    
12.                 cout << "just accept 1 parameter\n";
    
13.                 exit(1);
    
14.         }
    
15.         int year = atoi(argv[1]);
    
16.         deque<long long>; count(4, 1);
    
17.         count.pop_back();
    
18.         for ( int i = 2; i < year; i ++)
    
19.         {
    
20.                 count.push_back(count[0] + count[2]);
    
21.                 count.pop_front();
    
22.         }
    
23.         cout << "In the " << year <<"th year, there are(is) "
    
24.              << count[1] << " cows\n";
    
25. }
    

復(fù)制代碼

同樣是n級(jí)別的時(shí)間復(fù)雜度，但是空間復(fù)雜度變?yōu)?，deque的空間只有4.
不知道這個(gè)在時(shí)間上跟上一個(gè)有什么區(qū)別，不過(guò)估計(jì)也很難反映出來(lái)測(cè)試到117時(shí)就溢出了。

sylpjx

真是不知道母牛是否可以活一百歲，還有是不是真的每四年一頭，不符合實(shí)際嗎。

quanliking

看了大伙的高見(jiàn)，受益非淺，但總覺(jué)得解釋的還不是很清楚，偶爾在用麻將牌擺弄了一下，有了自己的想法，忍不住要寫(xiě)一下。

瘋狂的奶牛(母牛產(chǎn)仔問(wèn)題)     

首先做個(gè)約定,假定母牛在每年的春季(年初)才生育，該年的其它時(shí)間不生育(吃草，做胎教 ；新出生的小寶寶，要過(guò)滿 4 周歲(整 4 年)，才長(zhǎng)大成人，從事傳宗接代工作。
先來(lái)看看最初的這頭母牛(鼻祖，怎么來(lái)的，無(wú)性繁殖嗎？)，出生在公元 xxx 年初,為了簡(jiǎn)化統(tǒng)計(jì)，假定為 00 年(屆),那么從 00 年初到 01 年初，剛好過(guò)了一整年，以此類(lèi)推：到了 04 年初，整 4 年，此時(shí)該母牛懷胎十月，順利產(chǎn)下一子(是 mm 噢)，用圖表表示：

1. 
   
2. year 4
   
3. 0 *
   
4. 1
   
5. 2
   
6. 3
   
7. 4 *
   

復(fù)制代碼

星號(hào)表示每年增加(出生)�？冢�總�？跒� 2，有生育能力的�？跒� 1 。

我們來(lái)看看第 8 年初的情況：

1. 
   
2. year 8
   
3. 0 *
   
4. 1
   
5. 2
   
6. 3
   
7. 4 *
   
8. 5 *
   
9. 6 *
   
10. 7 *
    
11. 8 * *
    

復(fù)制代碼

很容易看出第 8 年出生的數(shù)目比第 7 年多 1 ，原因是 04 屆已經(jīng)到了生產(chǎn)年齡，總�？跒� 7, 有生育能力者為 2(也就是說(shuō)下一年至少有 2 個(gè)生產(chǎn)力。

繼續(xù)看第 9 年初的情況：

1. 
   
2. year 9
   
3. 0 *
   
4. 1
   
5. 2
   
6. 3
   
7. 4 *
   
8. 5 *
   
9. 6 *
   
10. 7 *
    
11. 8 * *
    
12. 9 * * *
    

復(fù)制代碼

這次大伙都能猜到為什么了，原因是除了 00 和 04 屆，05 屆也開(kāi)始生育了，它們是以后的新生產(chǎn)力。

最后讓我們看一副抓圖，以便找出規(guī)律來(lái)：

quanliking

當(dāng)?shù)搅说?19 個(gè)年頭，很容易看出規(guī)律來(lái)了，請(qǐng)看 19 這個(gè)位置：
紅線圈出來(lái)這部分是相隔 4 屆，即 15 屆的牛所生；圈前這部分是 15 屆的前幾屆牛所生，數(shù)目剛好等于 18 屆出生的�？�。

如果 n 表示年數(shù)，f(n) 表示該年出生的�？冢�

1. 
   
2.          1  ( n = 0 )
   
3. f(n) =  0  ( 0 <= n <= 3 )
   
4.          f(n-1) + f(n-4)   ( n >;= 4 )
   
5. 
   

復(fù)制代碼

如果要計(jì)算總牛數(shù) ( 假定牛長(zhǎng)生不老，青春永駐 )， count 為�？倲�(shù)：

1. 
   
2. int count = 0;
   
3. for ( i = 0; i <= n; i++)
   
4.      count += f(i)
   

復(fù)制代碼

下面是我寫(xiě)的程序源碼：

1. 
   
2. #include <stdio.h>;
   
3. #define YEAR 1000       // 計(jì)算到 1000 年,自行修改
   
4. 
   
5. int main( char argc, char **argv)
   
6. {
   
7.         int year;
   
8.         if ( argc == 1)
   
9.                 year = 10;      // 默認(rèn)計(jì)算 10 年
   
10.         else {
    
11.                 if ( argc >;= 2 && atoi(argv [1]) >;= 0 && atoi(argv [1]) <= YEAR)
    
12.                 {
    
13.                 year = atoi(argv [1]);
    
14.                 printf ("year: %d\n", year);
    
15.                 }
    
16.                 else {
    
17.                         printf ("年數(shù)錯(cuò)誤，請(qǐng)保持在 0 ~ 1000 范圍內(nèi)的整數(shù)\n");
    
18.                         return 0;
    
19.                 }
    
20.         }
    
21. 
    
22.         int born [YEAR] = {0};          // 存儲(chǔ)該年出生奶牛數(shù)目
    
23.         unsigned long count = 0;        // 到 n 年為止全部母牛總數(shù)
    
24. 
    
25.         int i;
    
26.         for ( i = 0; i <= year; i++) {  // 計(jì)算該年出生奶牛數(shù)目
    
27.                 if ( i <= 3 )
    
28.                         born [i] = (i == 0) ? 1 : 0;
    
29.                 else
    
30.                         born [i] = born [i - 1] + born [ i -4 ];
    
31.         }
    
32.         for ( i = 0; i <= year; i++) {
    
33.                 printf ("%3d ", i);
    
34.                 int j;
    
35.                 for ( j = 0; j < born[i]; j++)
    
36.                         printf ("*");
    
37.                 printf ("\n");
    
38.                 count += born [i];
    
39.         }
    
40.         printf ("total cow number after %d year: %lu\n", year, count);
    
41. 
    
42.         return 0;
    
43. }     
    
44. 
    

復(fù)制代碼

   

我這里用了數(shù)組 born [] ，用來(lái)存儲(chǔ)每年出生的�？�，當(dāng)然如果年數(shù)比較大，還應(yīng)該把  int born [] 改成 long born [] 需要占用一定的內(nèi)存，但不大，獲得的是很快的計(jì)算速度。
用數(shù)組保存結(jié)果，能方便奶牛的主人查看每年的出生記錄，以及牛的牛齡，比如規(guī)定節(jié)育年限，應(yīng)該比較容易能寫(xiě)出來(lái)。

上面的分析，不敢保證正確，因?yàn)榻Y(jié)果和有些人不同。

db_info

不會(huì)吧，第100年時(shí)，第1頭母�？偣采�了97，第2頭母牛總共生了94，第3頭母�？偣采�了91，依此，所以100年絕對(duì)不會(huì)超過(guò)1到100的和5050=（100+1）*100/2哦，最多也只是97+94+91+...+1=(97+1)*32/2=736頭，不知是否認(rèn)同？