母牛数量算法

dpsuffix

原帖由 loveguohuasai 于 2003-8-3 17:14 发表
若一头小母牛，从出生起第四个年头开始每年生一头母牛，按此规律，第n年有多少头母牛？

貌似就一只公牛阿。。。。那只公牛真累阿，那么多母牛。。。

dpsuffix

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main(int argc,char **argv)
   
5. {
   
6.     if(argc != 2){
   
7.         printf("usage: cmd number\n");
   
8.         return -1;
   
9.     }
   
10.     muniu(atoi(argv[1]));
    
11. }
    
12. 
    
13. int muniu(int n)
    
14. {
    
15.     int *arr = malloc(n*sizeof(int));
    
16.     if(!arr)
    
17.         exit(-1);
    
18.     int i;
    
19.     int sum = 0;
    
20.     int cans=1;
    
21.     arr[0] = 1;
    
22.     for(i=3;i<n;i++){
    
23.         if(i>3)
    
24.             cans=cans +arr[i-3];
    
25.         arr[i] = cans;
    
26.     }
    
27.     sums=cans;
    
28.     for(i=(i-3);i<n;i++){
    
29.         sum += arr[i];
    
30.     }
    
31.     printf("sum=%d\n", sum);
    
32. }
    

复制代码

[ 本帖最后由 dpsuffix 于 2008-5-30 10:59 编辑 ]

cheng_lai_shun

这不是那个著名的数列（斐波那契数列）问题

abc3w

牛 真不简单

分析
只要清楚一个循环周期内每年母牛崽与及产崽母牛数量就可以了。

用几个变量循环赋值及累加 和用递归，哪个有效率的优势?

bber01

#include "iostream.h"
#include "stdio.h"
__int64 CurrentCowNumSum = 1;
__int64 ChildCowJustBornNum = 1;
__int64 ChildCowAgeOneNum = 0;
__int64 ChildCowAgeTwoNum = 0;
__int64 ChildCowAgeThreeNum = 0;
__int64 ProgenitiveCowNum = 0;
__int64 fun(int nYear)
{
                int CurrentYear = 1;
                //一年一年又一年
               while(CurrentYear <= nYear)
                   {
                        //小牛们都会长大一岁
                        ProgenitiveCowNum += ChildCowAgeThreeNum; //三岁的小牛加入到成年牛的队伍中
                        ChildCowAgeThreeNum = ChildCowAgeTwoNum;//两岁的长大成三岁的了
                        ChildCowAgeTwoNum = ChildCowAgeOneNum;//一岁的长大成两岁的了
                        ChildCowAgeOneNum = ChildCowJustBornNum;//……
                       //成年的母牛们各生出了一岁的小牛
                        ChildCowJustBornNum = ProgenitiveCowNum;
                        CurrentCowNumSum += ChildCowJustBornNum;//它们的出生壮大了牛群
                        printf("in year %d:\n",CurrentYear);
                        printf("ChildCowJustBornNum=%I64d\n",ChildCowJustBornNum);
                        printf("ChildCowAgeOneNum=%I64d\n",ChildCowAgeOneNum);
                        printf("ChildCowAgeTwoNum=%I64d\n",ChildCowAgeTwoNum);
                        printf("ChildCowAgeThreeNum=%I64d\n",ChildCowAgeThreeNum);
                        printf("ProgenitiveCowNum=%I64d\n",ProgenitiveCowNum);  
                        printf("CurrentCowNumSum=%I64d\n\n",CurrentCowNumSum);
                        CurrentYear++;
                   }
                return CurrentCowNumSum;
}
int main()
{
        int Years;
        printf("input Year:");
        scanf("%d",&Years);
        printf("result:%I64d\n",fun(Years));
        return 0;
}

[ 本帖最后由 bber01 于 2008-5-31 23:44 编辑 ]

frog_skywalker

fibonacci 数列的logn算法都知道吧
递推公式f(n) = f(n-1) + f(n-2)
反复乘下面的矩阵
1 1
1 0

对于该题，递推公式为f(n) = f(n-1) + f(n - 3)
反复乘
1 0 1
1 0 0
0 1 0
&brvbar;f(n)    &brvbar;    &brvbar; 1 0 1 &brvbar;               &brvbar; f(3) &brvbar;
&brvbar;f(n-1) &brvbar; = &brvbar; 1 0 0 &brvbar;^n-3    * &brvbar; f(2) &brvbar;
&brvbar;f(n-2) &brvbar;    &brvbar; 0 1 0 &brvbar;               &brvbar; f(1) &brvbar;

证明过程很简单，用数学归纳法
推到过程要完备的形式比较繁琐。简单生成一个公式还是很容易的，观察下特性，写个矩阵就出来了

剩下的问题是，乘方运算如何在O(logn)时间内完成，筛选下就可以，证明过程计算法杂性书上有
还有一个就是大数问题了....


ps:其实这个数列是可以求出通项的...

[ 本帖最后由 frog_skywalker 于 2008-6-1 18:50 编辑 ]

x2

时间复杂度是O(logn)的算法google一下 sicp 1.19 就能找到了。

lxf1986

最后一年生的小牛就不算进内了？
４周年生小牛，我比较同意
牛的总数：10年－14头，30年－8657头，50年－5453761头

tigerajs

呵呵,很牛啊

x2

《计算机程序的构造和解释》的习题1.19就是要写出时间复杂度是O(lng n)的求菲波那契数的算法。