奶牛4年生1只牛犊,以后每年生1只,计算20年后奶牛数量

回复
头像
paktc
出类拔萃
出类拔萃
帖子: 65
注册时间: 2016年07月21日 20:34
联系:

奶牛4年生1只牛犊,以后每年生1只,计算20年后奶牛数量

帖子 paktc »

一只刚出生的奶牛,4年生1只奶牛,以后每一年生1只。
现有一只刚出生的奶牛,请求出20年后有多少奶牛。
https://www.zhihu.com/question/492927525
头像
paktc
出类拔萃
出类拔萃
帖子: 65
注册时间: 2016年07月21日 20:34
联系:

Re: 奶牛4年生1只牛犊,以后每年生1只,计算20年后奶牛数量

帖子 paktc »

动态规划方案:
https://www.zhihu.com/question/492927525/answer/2175252368

代码: 全选

#include <iostream>
using namespace std;

int main () 
{
     int n[21] = {1,1,1,1};
     for (int i = 4; i <= 20; i++)
          n[i]=n[i-1]+n[i-4];

     cout << n[20];
     return 0;
}

头像
523066680
Administrator
Administrator
帖子: 516
注册时间: 2016年07月19日 12:14
联系:

Re: 奶牛4年生1只牛犊,以后每年生1只,计算20年后奶牛数量

帖子 523066680 »

在4年以后,每年的牛奶数量是4年前的数量+上一年的数量
这个是一开始没想到的。
思维退化严重~

不过话说回来,这些牛犊四年后都会产牛吗,没有公的吗 :coverface1
雌雄同体 :speechless3
头像
523066680
Administrator
Administrator
帖子: 516
注册时间: 2016年07月19日 12:14
联系:

Re: 奶牛4年生1只牛犊,以后每年生1只,计算20年后奶牛数量

帖子 523066680 »

比较粗劣的算法,用空间增长模拟牛的增加

代码: 全选

my $cows = [  {'year'=>0} ];

for my $y ( 1..20 )
{
    for my $id ( 0 .. $#$cows )
    {
        $cows->[$id]{year}++;
        if ( $cows->[$id]{year} >= 4 ) {
            push @$cows, { 'year' => 0 };
        }
    }
}

printf "%d\n", scalar(@$cows);
C++版

代码: 全选

#include <iostream>
#include <vector>

using namespace std;
class Cow {
private:
    int year;

public:
    Cow(void) { year = 0; }
    void plus (void) { year++; }
    int age (void) { return year; }
};

int main(int argc, char *argv[] ) 
{
    vector<Cow> cows(1); // 第一头牛

    for (int y = 1; y <= 20; y++)
    {
        int last = cows.size() - 1 ;
        for ( int id = 0; id <= last; id++  ) 
        {
            cows[id].plus();
            if ( cows[id].age() >= 4 )
            {
                cows.push_back(Cow());
            }
        }
    }

    cout << cows.size();
    return 0;
}

C++版最开始是用

代码: 全选

for ( int id = 0; id < cows.size(); id++  ) 
,结果不对,原因在于 cows.size() 是持续更新的,于是改为

代码: 全选

        int last = cows.size() - 1 ;
        for ( int id = 0; id <= last; id++  ) 
把牛群也对象化(在错误的方案上越走越远?)

代码: 全选

#include <iostream>
#include <vector>

using namespace std;
class Cow {
private:
    int year;

public:
    Cow(void) { year = 0; }
    void grow (void) { year++; }
    int age (void) { return year; }
};

class CowsHerd {
private: 
    int count = 0;
    vector<Cow> cows;

public: 
    CowsHerd(void) {  }
    void add_cow(void) 
    {
        cows.push_back(Cow());
        count++;
    }
    
    void pass_one_year(void)
    {
        int last = cows.size() - 1;
        for ( int id = 0; id <= last; id++ )
        {
            cows[id].grow();
            cout << cows[id].age() << endl;
            if ( cows[id].age() >= 4 )
                add_cow();
        }
    }

    int num_of_cows (void) { return count; }
};

int main(int argc, char *argv[] ) 
{
    CowsHerd cows;
    cows.add_cow();

    for (int y = 1; y <= 20; y++)
        cows.pass_one_year();

    cout << cows.num_of_cows();
    return 0;
}

回复

在线用户

正浏览此版面之用户: 没有注册用户 和 0 访客