母牛数量算法

shiyiming

是不是老师出的题目，你拿到这里来找答案了，这样可不好，自己做出来才对

ge126

个人版的母牛
PS：测试一下GCC的扩展

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

复制代码

轩辕砍刀

C/C++版的精华也有这样的东东啊
一年多前的贴子了，好大的坑啊！！！

其实是Fibonacci斐波那契数列的变形了，原始的递进间隔是3

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

现在的间隔改成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)

所以，就是设间隔为非一正整数step（step为1时，数量无限大），就是第step年起开始生BB，则迭代公式为n(i)=n(i-1)+n(i-step+1)


用C++递归实现就是(在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; //递进间隔,大于1的正整数
   
10.       unsigned int year; //要计算的年数
    
11.       long number;   //计算结果
    
12.       bool mark;  //标识step是否在合理范围内及是否成功调用Set()；
    
13.   public:
    
14.          Fibonacci(); //构造函数显示初始化
    
15.       unsigned int Get_year();
    
16.          int  Display(); //输出计算结果
    
17.       void  Set(); //输入间隔和要计算的年数
    
18.       long  Fib_num(unsigned int); //计算数列，递归用的
    
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; //标识是否成功调用Fib_num()
    
33.    mark = 0;
    
34.    cout<< " Fibonacci数列实例：假设一头母牛在出生后第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<< "假设一头母牛在出生后第"<< step<< "年开始每年生下一头小母牛，且母牛不死亡。\n"<< "则第"<< year<<"年总共有母牛" << number << "头。"<< endl;
    
46.    else
    
47.      cout<< "接口函数调用错误！请先进行数据成员设置Set()和结果计算Fib_num()步骤。"<< endl;
    
48.    return(0);
    
49. }
    
50. 
    
51. void Fibonacci :: Set()
    
52. {
    
53.    cout<< "请输入x，x为大于1的正整数："<< endl;
    
54.    do
    
55.    {
    
56.     cin >>step;
    
57.           if(step>1)  {mark=1; break;}
    
58.           else  cout<< "请输入大于1的正整数。"<< endl;
    
59.    }while(mark);
    
60.    cout << "请输入n，n为非负整数，否则将得到不正确结果："<< 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);  //计算公式就在这了
    
71.      }
    
72.    else
    
73.      cout<< "接口函数调用错误！请先进行数据成员设置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. 
    

复制代码

以上是Fibonacci的递归实现了，如果year很大的话，那效率会比较低。

如果是非递归实现，可以，定义几个记录变量，目的是记录n（i-step+1）的值就可以了。不过程序是对具体的实例的，通用性很不好的。

要实现通用程序，可以定义一个大数组作为记录（面向对象特性不好）、或用链表实现（太麻烦），或者用new动态分配堆对象变量数组（最好重载new和delete，避免产生堆碎片而导致程序出错或者效率低下）

[ 本帖最后由 轩辕砍刀 于 2006-3-16 13:34 编辑 ]

star55

用precalculate,就是把你以前计算出来的值保留在数组里面，下次用到的时候就可以直接存取，不必要做重复的递归，算100年以上的话至少可以比你用的时候少几十倍。

yutian

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

afministrator

到底哪个是对的呀，
可不可以发到我的信箱里呀，
我是个新手呀，
好多地方不明白呀。
我的信箱是      :     fywtaichen@sina.com.cn         
谁写个完整的发到我这里呀，
先谢谢了！！！！

walkfire

非递归算法，反正我算第100年时基本上没有费什么时间：
int initCowCount = 1;
int yearInterval = 100;
long cowSum = initCowCount;

long cowCount_0 = 0;        // 刚出生的牛的数量
long cowCount_1 = 0; // 一岁的牛的数量
long cowCount_2 = 0;        // 两岁的牛的数量
long cowCount_3 = 0;        // 三岁及其以上的牛的数量

int main(int argc, char* argv[])
{
        cowCount_0 = initCowCount;
        long t1 = 0;
        long t2 = 0;
        long t3 = 0;
        // 计算牛的数量
        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年后母牛的数量为%d!\n\t",yearInterval,cowSum);
        return 0;
}

轩辕砍刀

[quote]原帖由 "star55"]用precalculate,就是把你以前计算出来的值保留在数组里面，下次用到的时候就可以直接存取，不必要做重复的递归，算100年以上的话至少可以比你用的时候少几十倍。[/quote 发表：


晕4，我无语了……

麻烦先仔细看完人家的帖子再发言。

ericooler

其实简单得很，第n年的数量是上一年牛的数量加上3年前牛的数量，因为三年前的您都在这一年生小牛了，也就是：f(n)=f(n-3)+f(n-1)， 不管递推还是递归都很容易计算。

terryliu98

原帖由 "aero" 发表：
4周岁开始生小牛：10年：10，30年：6272
3周岁开始生小牛：10年：19，30年：39865
PS：看哪，这就是晚生优生的结果。

再加一条,还应该让牛也计划生育,情况就会好多了......