母牛数量算法

hoxide

那就更有趣了
比如每个年龄的牛按一定比例死掉，
小牛夭折，高龄产妇，
最重要的是公牛跑到哪儿去了，
母牛会自交啊？

aero

在下去就变成养牛场的模拟软件了，是不是算一个项目啊。^_^

hoxide

算阿，很有趣的。等有钱了我买个农场，就用这个。
大家努力啊

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 ;年数 or 结果
   
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

复制代码

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. }
    

复制代码

关键就在那个for循环。
就是f(n) = f(n - 1) + f(n - 3) 的实现。[/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. }
    

复制代码

同样是n级别的时间复杂度，但是空间复杂度变为1，deque的空间只有4.
不知道这个在时间上跟上一个有什么区别，不过估计也很难反映出来测试到117时就溢出了。

sylpjx

真是不知道母牛是否可以活一百岁，还有是不是真的每四年一头，不符合实际吗。

quanliking

看了大伙的高见，受益非浅，但总觉得解释的还不是很清楚，偶尔在用麻将牌摆弄了一下，有了自己的想法，忍不住要写一下。

疯狂的奶牛(母牛产仔问题)     

首先做个约定,假定母牛在每年的春季(年初)才生育，该年的其它时间不生育(吃草，做胎教 ；新出生的小宝宝，要过满 4 周岁(整 4 年)，才长大成人，从事传宗接代工作。
先来看看最初的这头母牛(鼻祖，怎么来的，无性繁殖吗？)，出生在公元 xxx 年初,为了简化统计，假定为 00 年(届),那么从 00 年初到 01 年初，刚好过了一整年，以此类推：到了 04 年初，整 4 年，此时该母牛怀胎十月，顺利产下一子(是 mm 噢)，用图表表示：

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

复制代码

星号表示每年增加(出生)牛口，总牛口为 2，有生育能力的牛口为 1 。

我们来看看第 8 年初的情况：

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

复制代码

很容易看出第 8 年出生的数目比第 7 年多 1 ，原因是 04 届已经到了生产年龄，总牛口为 7, 有生育能力者为 2(也就是说下一年至少有 2 个生产力。

继续看第 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 * * *
    

复制代码

这次大伙都能猜到为什么了，原因是除了 00 和 04 届，05 届也开始生育了，它们是以后的新生产力。

最后让我们看一副抓图，以便找出规律来：

quanliking

当到了第 19 个年头，很容易看出规律来了，请看 19 这个位置：
红线圈出来这部分是相隔 4 届，即 15 届的牛所生；圈前这部分是 15 届的前几届牛所生，数目刚好等于 18 届出生的牛口。

如果 n 表示年数，f(n) 表示该年出生的牛口：

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

复制代码

如果要计算总牛数 ( 假定牛长生不老，青春永驻 )， count 为牛总数：

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

复制代码

下面是我写的程序源码：

1. 
   
2. #include <stdio.h>;
   
3. #define YEAR 1000       // 计算到 1000 年,自行修改
   
4. 
   
5. int main( char argc, char **argv)
   
6. {
   
7.         int year;
   
8.         if ( argc == 1)
   
9.                 year = 10;      // 默认计算 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 ("年数错误，请保持在 0 ~ 1000 范围内的整数\n");
    
18.                         return 0;
    
19.                 }
    
20.         }
    
21. 
    
22.         int born [YEAR] = {0};          // 存储该年出生奶牛数目
    
23.         unsigned long count = 0;        // 到 n 年为止全部母牛总数
    
24. 
    
25.         int i;
    
26.         for ( i = 0; i <= year; i++) {  // 计算该年出生奶牛数目
    
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. 
    

复制代码

   

我这里用了数组 born [] ，用来存储每年出生的牛口，当然如果年数比较大，还应该把  int born [] 改成 long born [] 需要占用一定的内存，但不大，获得的是很快的计算速度。
用数组保存结果，能方便奶牛的主人查看每年的出生记录，以及牛的牛龄，比如规定节育年限，应该比较容易能写出来。

上面的分析，不敢保证正确，因为结果和有些人不同。

db_info

不会吧，第100年时，第1头母牛总共生了97，第2头母牛总共生了94，第3头母牛总共生了91，依此，所以100年绝对不会超过1到100的和5050=（100+1）*100/2哦，最多也只是97+94+91+...+1=(97+1)*32/2=736头，不知是否认同？