母牛数量算法

win_hate

这么老的帖都有人顶，留个名先。


说穿了就是一个线性递归序列。

看这里：

http://www.cublog.cn/u/20/showart.php?id=80060

[ 本帖最后由 win_hate 于 2006-3-3 13:52 编辑 ]

unixyeah

版主用的是maple吧？
真是牛哄哄

ghostwolf

long niu=1
void born(int n)
{
    if(n>=4)
    {
         niu+=(n-3);
         born(n-3);
    }
}

[ 本帖最后由 ghostwolf 于 2006-3-9 08:21 编辑 ]

billzhou

#include <iostream>
using namespace std;
int main(   )
{int n;

cin>>n;
cout<<"the n is:"<<n<<endl;
        int howmany(int );
   
        cout<<"the n year there are femile  pigs:"<<howmany(n)<<endl;;
        return 0;
}
int howmany(int i  )
{
if(i<4)
  return 1;
else if(i==4)
   return 2;

else if(i==5)
return 3;
else if(i==6)
return 4;
else if(i==7)
  return 6;
else
return (howmany(i-1)+i-5);

}
不知道对不对
到100年是4563头
1  2 3 4 5 6 7 8 9    0
1  1  1 2 3 4 6 9 13 18
规律很明显啊
可以写个函数直接解出来
从第6年开始 没年都比上一年多出生1个
高中数学就可以解了
一个等加递增数列

billzhou

好象不对了 少考虑了一种情况 明天再写了

zfol_510

如果我没有理解错的话,是这样的吧
第100年为4563


#include <iostream>
#include <cstdio>
#include <cassert>
#define GROWING_STEP 4                //每头小牛需要多长时间成为母牛(可以生新的小牛)
using namespace std;

int main(int argc, char *argv[])
{
        int total;
        int step;                        //control the increment cow number
        if (argc!=2)
        {
                cout<<"wrong parameter"<<endl;
                exit(-1);
        }
        int years = atoi(argv[1]);
        assert (years > 0);

        if (years < GROWING_STEP)                //当输入年数小于4,只有一头牛,因为初始的小牛还没有成熟
        {
                total = 1;
        }
        else if(years < (GROWING_STEP*2-1))                //输入年数小于7,只有一头牛生产,此时增量固定为1.
        {
                total =1;
                step = 1;
                for (int i= GROWING_STEP; i<=years; i++)
                {
                        total += step;
                }
                       
        }
        else if(years >= (GROWING_STEP*2-1))     //从第7年开始,此时每年都会有新的小牛成为母牛.所以增量为1,2,3,4,5自然数列.
        {
                total = GROWING_STEP;
                step = 1;
                for (int i=GROWING_STEP*2-1; i<=years; i++)
                {
                        step++;
                        total+=step;
                }

        }
        else;                        //空语句,无用,仅仅为了格式
       
        cout<<"after "<<years<<" years, the number of cows are :"<<total<<endl;
        return 0;
}

marinekiller

我错了,错了,错了,错了
#include<iostream.h>
#include<conio.h>
int f(int j)
{
     return j*(j+1)/2;
}
void main()
{
     int m,n;
     cout<<"输入 n :";
     cin>>n;
     if(n<4)
        m=1;
     else
     {
        m+=n-3;
        for (int i=2;4*i-1<n;i++)
        {
           m+=f(n-4*i+1);
        }
}
     cout<<"第"<<n<<"年母牛数量："<<m;
     _getch();
}
//  第100年算出来是36370
//  第1000年算出来是41107495
//  第10000年算出来是4.16104e+10
算法原理：
         只说n>=4的情况
         第一头牛一共生了 n-3头牛，这n-3头牛被称为二代牛
             如果n>7,二代牛的第一个出生的生了n-7头牛，第二个出生的生了n-8头牛......知道有一个生了一个
             所一二代牛一共生了 1+2+......+(n-7) 头牛，这些被称为三代牛
         三代牛一共生了 1+2+......+(n-11)头牛，这些被称为四代牛
         直到有一代牛没机会长大生仔

发现自己错了啊,sigh

[ 本帖最后由 marinekiller 于 2006-3-23 14:02 编辑 ]

tanchanghe

1、所有牛在计算年限内不死

marinekiller

#include <iostream.h>
#include <conio.h>
int fib(int i)
{  if(i == 1 ||i == 2||i == 3)
      return 1;
    else if(i == 4)
      return 2;
    else if(i == 5)
      return 3;
    else
      return fib(i-1)+fib(i-4);
}
void main()
{
    int n;
    cout<<"Input n:";
    cin>>n;
    cout<<fib(n);
}
// n 为50时结果是：5453761
// n 为60时结果是：136886433
// n 为66时结果是：946583628

[ 本帖最后由 marinekiller 于 2006-3-23 16:51 编辑 ]

marinekiller

#include <iostream.h>
#include <conio.h>
int fib(int y)
{
     if(y == 1||y == 2||y ==3)
       return 1;
     if(y == 4)
       return 2;
     int m = 1,n = 1,p = 1,q = 2;
     int x=0;
     for(int i = 5;i <= y;i++)
     {
          x = m+q;
          m = n;
          n = p;
          p = q;
          q = x;
      }
      return x;
}
void main()
{
         int n;
         cout << "Input n:";
         cin >> n;
         cout << fib(n);
         _getch();
}

//n 为 50  时结果是：5453761
//n 为 100时结果是：195857222
//n 为 1000时结果是：5.06763e+139

[ 本帖最后由 marinekiller 于 2006-3-23 16:47 编辑 ]