母牛數(shù)量算法

selfrun

mathe在csdn給過一個求Fibonacci數(shù)列第n項復(fù)雜度為O(logN)的算法，并給出了數(shù)學(xué)歸納法的推導(dǎo)過程，
貌似這個也可以用類似方法推導(dǎo)，只是俺數(shù)學(xué)很不好，高手們來看看�。�！

ArchieYao

原帖由 db_info 于 2003-8-21 12:04 發(fā)表
不會吧，第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 發(fā)表
有這等事
很嚴(yán)重呀，要是改成“美女”真不知道會是什么樣的呢~！

這世間就不會再有光棍了

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;    // 進入生育期的牛數(shù)量
        uint32_t notg0 = 0;   // 剛出生的牛數(shù)量
        uint32_t notg1 = 0;   // 1歲牛數(shù)量
        uint32_t notg2 = 0;   // 2歲牛數(shù)量
        uint32_t notg3 = 0;   // 3歲牛數(shù)量

        if(year < 4)
               return 1;

        for(i=4;i<year; i++ ) // 歷史的進程開始了，時間，跑吧！
        {
                tmp = notg0;  // 將上年出生的牛保存到tmp
                notg0 = base; // 母牛生孩子了
                base += notg3; // 3歲的母牛也會生孩子了
                notg3 = notg2; // 2歲的孩子也應(yīng)該長大一歲
                notg2 = notg1; // 1歲的小朋友應(yīng)該會跑了
                notg1 = tmp;   // 去年剛出生的小孩子應(yīng)該一歲了
        }
        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

我的瑪雅，這么簡單的題目居然會引無數(shù)英雄盡折腰了，那么多的解答基本上都存在很打的邏輯漏洞
先不談什么規(guī)律了，那個不需要邏輯
兩個方案
1. 循環(huán)普通解法
思路：new 一個牛圈，里面每個元素代表一頭牛，元素值代表歲數(shù)。一年一年的循環(huán)計算，每個cow歲數(shù)都加一，如果歲數(shù)足夠大到生孩子的年齡就生一個
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. 動態(tài)規(guī)劃算法
思路：n年的牛的總頭數(shù)  =  第1年出生的牛的頭數(shù)+第2年出生的牛的頭數(shù)+第3年出生的牛的頭數(shù)+。。。
而且 第n年出生的牛的頭數(shù) = 第1年出生的牛的頭數(shù)+第2年出生的牛的頭數(shù)+第3年出生的牛的頭數(shù)+。。。第n-3年出生的牛的頭數(shù)(凡是這些年出生的牛都可以生小牛了)

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 發(fā)表
我的瑪雅，這么簡單的題目居然會引無數(shù)英雄盡折腰了，那么多的解答基本上都存在很打的邏輯漏洞
先不談什么規(guī)律了，那個不需要邏輯
兩個方案
1. 循環(huán)普通解法
思路：new 一個牛圈，里面每個元素代表一頭牛， ...

NB啊