母牛数量算法

selfrun

mathe在csdn给过一个求Fibonacci数列第n项复杂度为O(logN)的算法，并给出了数学归纳法的推导过程，
貌似这个也可以用类似方法推导，只是俺数学很不好，高手们来看看啊！！

ArchieYao

原帖由 db_info 于 2003-8-21 12:04 发表
不会吧，第100年时，第1头母牛总共生了97，第2头母牛总共生了94，第3头母牛总共生了91，依此，所以100年绝对不会超过1到100的和5050=（100+1）*100/2哦，最多也只是97+94+91+...+1=(97+1)*32/2=736头，不知是否 ...

同感：）
这才是算法

ArchieYao

原帖由 海滨 于 2003-8-8 05:18 发表
有这等事
很严重呀，要是改成“美女”真不知道会是什么样的呢~！

这世间就不会再有光棍了

runforu

long result[100] = {1,1,1};
int f()
{
    for(int i= 3; i<100;i++)
        result = result[i-1]+result[i-2];
    return result[99];
}

yb1682003

int t(int year){
                if(year<1)
                        return 0;
                else{
                        return year+t(year-4);
                }
        }

一百年的话:1200

poor-man

int col(int year)
{
        int i,tmp;
        uint32_t base = 1;    // 进入生育期的牛数量
        uint32_t notg0 = 0;   // 刚出生的牛数量
        uint32_t notg1 = 0;   // 1岁牛数量
        uint32_t notg2 = 0;   // 2岁牛数量
        uint32_t notg3 = 0;   // 3岁牛数量

        if(year < 4)
               return 1;

        for(i=4;i<year; i++ ) // 历史的进程开始了，时间，跑吧！
        {
                tmp = notg0;  // 将上年出生的牛保存到tmp
                notg0 = base; // 母牛生孩子了
                base += notg3; // 3岁的母牛也会生孩子了
                notg3 = notg2; // 2岁的孩子也应该长大一岁
                notg2 = notg1; // 1岁的小朋友应该会跑了
                notg1 = tmp;   // 去年刚出生的小孩子应该一岁了
        }
        return  notg3 + notg2 +notg1 +notg0 + base; // n多年后，所有的大人小孩都来集合（如果还没老死的话）
}

[ 本帖最后由 poor-man 于 2008-4-1 12:56 编辑 ]

lacalling

#include<iostream>
using namespace std;
#define N 50
int main()
{
        int born=1;
        int beg_born[N];
        unsigned int have[N];
        int i,j;
        for(j=0;j<N;++j)
        {
                beg_born[j]=have[j]=0;
        }
        have[3]=1;
        for(i=4;i<N;++i)
        {
                have=born+have[i-1];       
                if(i+4<N)beg_born[i+4]=born;
                born+=beg_born;
        }
        cout<<have[N-1];
}

100年用int都溢出了。。。
递推俄～～
多多指教

HJLin

我的玛雅，这么简单的题目居然会引无数英雄尽折腰了，那么多的解答基本上都存在很打的逻辑漏洞
先不谈什么规律了，那个不需要逻辑
两个方案
1. 循环普通解法
思路：new 一个牛圈，里面每个元素代表一头牛，元素值代表岁数。一年一年的循环计算，每个cow岁数都加一，如果岁数足够大到生孩子的年龄就生一个
int cows(int year) {
        int sum = 1;
        const int N = 100;
        int* cows = new int[N];
        cows[0] = 1;  //first cow is one year old
        for(int i=0; i<year; i++) {
//如果cows容量越界，重新非配空间
                int temp = sum;
                for(int j=0; j<temp; j++) {
                        if(cows[j] >= 4)cows[sum++] = 2;
                        cows[j]++;
                }
        }
        return sum;
}

int main() {
        printf("%d\n", cows(10));
        getchar();
        return 0;
}
2. 动态规划算法
思路：n年的牛的总头数  =  第1年出生的牛的头数+第2年出生的牛的头数+第3年出生的牛的头数+。。。
而且 第n年出生的牛的头数 = 第1年出生的牛的头数+第2年出生的牛的头数+第3年出生的牛的头数+。。。第n-3年出生的牛的头数(凡是这些年出生的牛都可以生小牛了)

int cows(int year) {
        int* cows = new int[year];
        memset(cows, 0, year*4);
        cows[0] = 1;
        if(year <= 3)return 1;
        for(int i=3; i<year; i++) {
                for(int j=0; j<=i-3; j++)cows += cows[j];
        }
        int sum = 0;
        for(int i=0; i<year; i++) {
                sum += cows;
        }
        return sum;
}

int main() {
        printf("%d\n", cows(10));
        getchar();
        return 0;
}
看不懂的话就没办法了- -!

tyz

看看吧

tyz

原帖由 HJLin 于 2008-4-3 14:45 发表
我的玛雅，这么简单的题目居然会引无数英雄尽折腰了，那么多的解答基本上都存在很打的逻辑漏洞
先不谈什么规律了，那个不需要逻辑
两个方案
1. 循环普通解法
思路：new 一个牛圈，里面每个元素代表一头牛， ...

NB啊