母牛数量算法

flw

呵呵。我的答案不一定是效率最高的，但是理解起来绝对是最简单的，而且结果也绝对是正确的。凡是和我的结果不同的，当然就是错的。

quanliking

[quote]原帖由 "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头，不知是否认同

quanliking

[quote]原帖由 "flw"]呵呵。我的答案不一定是效率最高的，但是理解起来绝对是最简单的，而且结果也绝对是正确的。凡是和我的结果不同的，当然就是错的。[/quote 发表：
     
刚才编译了一下老大用 c++ 链表写的,里面有一处小问题，我用的是 g++ ，改正过来了，同时改动了一下 main () 好让它接受参数，不要介意，以下是改好的代码：

1. 
   
2. // 修改自 cow_flw.cpp
   
3. # include <stdio.h>;
   
4. # include <iostream>;
   
5. # define YEAR 100
   
6. 
   
7. class cow
   
8. {
   
9. public:
   
10.    static cow *head;
    
11.    static cow *tail;
    
12.    static unsigned long cowCount;
    
13. 
    
14.    int age;
    
15.    cow *next;
    
16. 
    
17.    cow()
    
18.    {
    
19.       age = 0;
    
20.       next = ( cow * ) NULL;
    
21.    }
    
22. 
    
23.    void grow(void)
    
24.    {
    
25.       age++;
    
26.       if ( age >;= 4 )
    
27.       {
    
28.          cow *child = new cow;
    
29.          tail->;next = child;
    
30.          tail = child;
    
31.          cowCount++;
    
32.       }
    
33.    }
    
34. };
    
35. 
    
36. unsigned long cow::cowCount = 0;
    
37. cow *cow::head = NULL;
    
38. cow *cow::tail = NULL;
    
39. 
    
40. 
    
41. int main( char argc, char **argv)
    
42. {
    
43.         int years;
    
44.         if ( argc == 1)
    
45.                 years = 10;      // 默认计算 10 年
    
46.         else {
    
47.                 if ( argc >;= 2 && atoi(argv [1]) >;= 0 && atoi(argv [1]) <= YEAR)
    
48.                 {
    
49.                 years = atoi(argv [1]);
    
50.                 printf ("year: %d\n", years);
    
51.                 }
    
52. 
    
53.                 else {
    
54.                         printf ("年数错误，请保持在 0 ~ 100 范围内的整数\n");
    
55.                         return 0;
    
56.                 }
    
57.         }
    
58. 
    
59. 
    
60.    cow *cows = new cow;
    
61.    cow::head = cows;
    
62.    cow::tail = cows;
    
63.    cow::cowCount = 1;
    
64. 
    
65. 
    
66.    cow *ptr = cow::head;  // 指针 ptr 在此处定义
    
67.    for( int i=0; i<years; i++ )
    
68.       for( ptr = cow::head; ptr != NULL; ptr = ptr->;next )  // 这里改动了一下，指针定义我拿到了嵌套外部
    
69.          ptr->;grow();
    
70. 
    
71.    printf( "result: [%ld]\n", cow::cowCount );
    
72. 
    
73.    ptr = cow::head;
    
74.    while( ptr != NULL )
    
75.    {
    
76.       cow *temp = ptr;
    
77.       ptr = ptr->;next;
    
78.       delete temp;
    
79.    }
    
80. 
    
81.    return 1;
    
82. }
    

复制代码

flw 兄的约定是整整 3 周岁，就是 365 * 3 天，而我的是 4 周岁，这样的话，我的代码调整如下(修改两个数字)：

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 <= 2 )  // 这里由 3 改成 2
    
28.                         born [i] = (i == 0) ? 1 : 0;
    
29.                 else
    
30.                         born [i] = born [i - 1] + born [ i -3 ];  // 这里由 4 改成 3
    
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. }      
    

复制代码

计算结果和 flw 的结果刚好相差一年，也就是说：
我的 10 年是 28 头；
flw 11 刚好 28 头；
以此类推，除此之外完全一样。
我思考了一下，主要是对第一年的理解可能有所不同，我是算每年的年初产牛，具体谁对谁错，还没细想。

这里提到效率问题：
用链表操作，越到下面，效率低的可怜，要是计算 100 年，怕是等不了，内存不够大，估计可能还会死机，不过这里用到 c++ 面象对象的思想还是很不错的。


算法其实很简单，就两个循环，一个计算每年出生的牛数，另外一个用来统计总的牛数。理解上，只要你照我写的耐心看一下，只会比链表来的简单。

quanliking

如果约定 3 周岁开始生育：
每年农场出生的牛数为 f(n)：

1. 
   
2.         1 , n = 0
   
3. f(n) =  0 , n = 1 || 2
   
4.         f(n - 1) + f(n - 3) n >;= 3
   

复制代码

1. 
   
2. f(0) = 1
   
3. f(1) = 0
   
4. f(2) = 0
   
5. f(3) = f(2) + f(0)
   
6. f(4) = f(3) + f(1)
   
7. f(5) = f(4) + f(2)
   
8. ......
   
9. f(n-1) = f(n-2) + f(n-4)
   
10. f(n) = f(n-1) + f(n-3)
    
11. 
    
12. 把左边一列相加得到母牛的总数目：
    
13. Sum(n) = f(0) + f(1) +...+ f(n)
    
14. 
    
15. 等号右边第一列相加,把最后一列也加起来，刚好得到以下式子：
    
16. Sum(n) = Sum(n - 1) + Sum(n - 3)
    
17. 
    
18. 加上初始条件:
    
19. Sum(0) = Sum(1) = Sum(2) = 1
    

复制代码

我想这个式子应该不陌生了,跟楼上几位朋友推出来的一样吧！
可以这样理解：
n-1 年的母牛总数到了 n 年，一头没少，全活得好好的，而且它们中处于生育年龄母牛们还生了不少小宝宝，数目刚好等于相隔三年前母牛的总数目。

aero

我晕，现在这帖子还被顶了上来，也没有什么新的算法，还是原先讨论过的算法在不停的贴代码。

小飞爱使申华

[quote]原帖由 "aero"]我晕，现在这帖子还被顶了上来，也没有什么新的算法，还是原先讨论过的算法在不停的贴代码。[/quote 发表：
     

呵呵，就这帖子，比清茶斋还热闹。

great3779

这是递归调用的好题啊。
是精华！

山山水水

大家好，我是新手（C&linux）近来看此题，工作闲暇与几位同事闲聊得出一结果：16637075746565964头牛！！！有点夸张了吧？？？
对题目首先进行假设处理：每头牛寿命无限
解题思路：首先，同样受前帖子解题思想的影响考虑用递归，但发现就单纯从牛繁殖且用年份度量的话，很短时间后，牛的数目的增长已经不单单是线性指数关系了所以先否定了递归调用+牛繁殖且用年份度量的解题思路。
          其次，对核裂变公式的推敲更加认识到用线性时间变量去度量以高阶指数形式改变数量的解题思路关键在公式的形成，因为再好、再超前的硬件也经不住N（线性时间变量）的考验！！！
          所以认识到就此题所设，及我自身数学水平有限而采用以下方法与步骤：
         1、不采用线性时间变量，而采用牛的生产周期时间做变量（关键）；
         2、用电子表格，划分4个阶段（列，注：牛的生产周期）罗列100年（行），观察数据变化推出基本可行公式；
         3、用for循环实现。

附程序（草）
  

     main()
{
               double a,a1,a2,a3;/*分别为：生产牛，1年牛，2年牛，3年牛*/
                double temp,sum;
               int i;
               a=1;a1=1;a2=1;a3=1;/*第6年（共4头牛）各周期的牛*/
                for(i=7;i<=100;i++)
                {
                        a=(a+a3);
                        a1=a;
                        temp=a2;
                        a2=(a-a3);
                        a3=temp;
                 }
                   sum=a+a1+a2+a3;
                  printf("sum=%f\n",sum);
}

完

duisburg

刚刚来到这儿，就看到这么一篇帖子，受益匪浅！
以后会常来，还请各位老大关照！

blazewater

性能最好，最容易理解的解决方法上场了！！
#define AGE_1 0  //一岁的牛
#define AGE_2 1 //二岁的牛
#define AGE_3 2 //三岁的牛
#define AGE_4 3 //大于或者等于四岁的牛，可以生牛的牛；
int main(void)
{
     int cow[4]；
    int years = 0;

   //初始化，只有一头一岁的母牛；
   cow[AGE_1] = 1;
    cow[AGE_2] = 1;
    cow[AGE_3] = 1;
    cow[AGE_4] = 1;

    printf("input Years? ";
    scanf("%d", years);
    for (int i=1; i<=years; i++)
    {
     //三岁的猪都长了一岁，所以放到四岁的数组中来；
         cow[AGE_4] += cow[AGE_3];
     //2岁的猪也长了一岁，放到三岁的数组中来；
        cow[AGE_3] = cow[AGE_2];
     //1岁的猪也长了一岁，放到二岁的数组中来；
     cow[AGE_2] = cow[AGE_3];
     //1岁的猪是由今年四岁的和大于四岁的猪生的；
     cow[AGE_1] = cow[AGE_4];
    }
    printf("all cow is : %d", cow[0] + cow[1] + cow[2] + cow[3]);
}

不好意思，一直以为是猪，应该是牛，呵呵。。。


其他的几种不大让我满意的解决方法：

solution1:
#include <stdio.h>;
#include <stdlib.h>;

int total_n(int year)
{
    if (year <= 3) return 1;
    if (year == 4) return 2;
    return total_n(year-1)+total_n(year-3);
}

int main(void)
{
   printf("50 years go by, total pigs: %d\n", total_n(50));
   return 1;
}

solution2:
#include <iostream.h>;

struct pig
{
    int age;
//    int mother;
    int children;
};
int count_pigs(int year)
{
    int i, j, k, m;
    int count, count_tmp;
    pig pigs[102400000];
    //init;
    i=j=k=m=0;
    count=count_tmp=1;
    for (i=0; i<10240; i++)
    {
        pigs.age=0;
//        pigs.mother=0;
        pigs.children=0;
    }
    //years go by...;
    for(i=1; i<=year; i++)
    {
        cout << "现在是第" << i << "年:" << endl;
        for (j=0; j<count_tmp; j++)
        {
            pigs[j].age++;
//            cout << "    第" << j << "头猪的年龄是:" << pigs[j].age << endl;
//            cout << "        她共生了" << pigs[j].children << "头小猪" << endl;
            if (pigs[j].age >;= 4)
            {
                pigs[j].children++;
                pigs[count++].age=1;
//                pigs[count-1].mother=j;
                pigs[count-1].children=0;
//                cout <<"            她今年生了一头小猪" << count -1 << endl;
            }
        }
        count_tmp=count;
        cout << "\t" << "第" << i << "年猪的总数: " << count << endl;
    }
    cout << "total pigs: " << count << endl;
    return count;
}
int main(void)
{
    int years=0;
    //get year;
    cout << "input years: ";
    cin >;>; years;
    count_pigs(years);
}

solution3:
#include <stdio.h>;
#define n 70
struct year{
int yearnum;
long pignum;
};
struct year yearslot[n];
int main(){
yearslot[0].yearnum=1;
yearslot[0].pignum=1;
for(int i=1;i<n;i++)
{
long num=0;
for(int j=0;j<=i-3;j++)
{
        num+=yearslot[j].pignum;
}
printf("year %d's pig num = %ul\n",i+1,num);
yearslot.pignum=num;
yearslot.yearnum=1;

for(int j=0;j<i;j++)
yearslot[j].yearnum++;
}
long num=0;
for(int i=0;i<n;i++)
num+=yearslot.pignum;
printf("all pig is:%ul\n",num);
}