母牛数量算法

leeon868

大概12点到3点之间都在看这个帖子的代码。代码其实并不复杂，关键是前2个小时我在自己写代码验证数据的正确性，

后面花时间，一个个验证这个帖子帖子代码的数据正确性，还有算法复杂度，

呵呵，最后4点睡觉，现在8点继续上班，有些小困，现在继续上班。我才睡了4个小时，中午补觉。

有关C/C++学习，还有，有没有对这个问题深究的必要。

有个叫KingOfArk的朋友，写了个《学习C++和编程的50个观点》

在新的版本的中的，条款5. 不要放过任何一个看上去很简单的小编程问题——他们往往并不那么简单，或者可以引伸出很多知识点；

而且解释里面就提到有可能用到long long long long int，呵呵。

原帖地址：http://blog.csdn.net/kingofark/archive/2001/11/09/2010.aspx

leeon868

网上找的这个解释不错：

若一头小母牛，从出生起第四个年头开始每年生一头母牛，按此规律，第n年有多少头母牛？（假设这是永生的优良品种牛）

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)

gta

跟fibonacci数列的兔子产仔问题很相似。用生成函数求

wuyipig

/*若一头小母牛，从出生起第四个年头开始每年生一头母牛，按此规律，第n年有多少头母牛？*/
/*
        Sum(n)=Sum(n-1)+Born(n);//第n年的母牛总头数应该等于去年总头数加第n年出生的头数
        Born(n)=Sum(n-3);//由题意可知第n-3年的母牛将在第n年全部生下小母牛
        Sum(n)=Sum(n-1)+Sum(n-3);
*/
/*使用递归算法*/

#include <stdio.h>

/*注意值域，超出值域则返回错误结果；而且当n较大时(n>50),此算法非常消耗资源*/
int Sum(int n)/*母牛总数*/
{
        int sum;
        if(n<4)/*第4年生下一头母牛 ，所以前三年都只有一头母牛*/
                sum=1;
        else
                sum=Sum(n-1)+Born(n);
        return sum;
}
int Born(int n)/*新出生母牛数*/
{
        int born;
        born=Sum(n-3);
        return born;
}
int main()
{
        int n;       
        printf("请输入第n年:");
        scanf("%d",&n);
        printf("n年母牛的总数是：");
        printf("%d头\n",Sum(n));
        printf("新出生的母牛有%d头\n",Born(n));
}

希望有人可以改良一下算法，一个算法不好，似解数学多于编程

heiying610

#include <iostream.h>

int f(int N);
void main()
{

        int i,n;
        n=1;
        while(n)
        {
                cin>>n;
        i=f(n);
        cout<<i<<endl;
        }
}
int f(int N)
{
        int sum,sum1,sum2,sum3;
sum=sum1=sum2=sum3=1;
if(N<4)
{
return sum;
}
int m=(N-1)%3;
for(int i=1;i<(N+2)/3;i++)
{
sum1+=sum3;
sum2+=sum1;
sum3+=sum2;
}
switch(m)
{
case 0:sum=sum1;break;
case 1:sum=sum2 ;break;
case 2:sum=sum3;
}
return sum;
}

heiying610

原帖由 heiying610 于 2008-3-28 14:00 发表
#include

int f(int N);
void main()
{

        int i,n;
        n=1;
        while(n)
        {
                cin>>n;
        i=f(n);
        cout

调试过了 可以的 并且感觉速度还是很快的
如果要是 溢出 可以考虑 将int  换成 long int 或者更大的

selfrun

算是dp的吧，时间复杂度O(n),空间复杂度O(n)
UINT64 *g_array = 0;
UINT64 cow(int year)
{
    if ( year < 4 ) return 1;
    if ( g_array[year] == 0 ) g_array[year] = cow( year - 1 ) + cow (year - 3);
    return g_array[year];
}
int main(int argc, char* argv[])
{

    if ( argc > 1 ) {
        int len = atoi(argv[1]);
        g_array = new UINT64[len + 1];
        for ( int i = 0; i <= len; i++ ) g_array = 0;

        for ( int j = 4; j < len; j++ ) {
#ifdef LINUX
            printf("\n%d %ll",j, cow(j));
#else
            printf("\n%d %I64d",j, cow(j));
#endif
        }
        delete[] g_array;
    }
        return 0;
}

runforu

int N[100]={1,1,1};

int f(int n)
{   
    for(int i = 3; i<100; i++)
        N[ i ] = N[i-1]+ N[i-3];
    return N[99];   
}

selfrun

貌似楼上的方法可以改用循环链表，空间复杂度变成O(1), 最后这题就成了解决大数运算的问题了！ 呵呵

selfrun

struct _NODE_{
    UINT64 data;
    _NODE_ *_left;
    _NODE_ *_right;
};
UINT64 cow1(int year)
{
    if ( year < 4 ) return 1;
    _NODE_ buf[3] = {2, &buf[2], &buf[1], 1,buf, &buf[2], 1, &buf[1], buf};
    _NODE_ *_current = buf;
    for ( int i = 4; i < year; i++ ) {
        _current = _current->_right;
        _current->data += _current->_left->data;
    }
    return _current->data;
}