岁堤春晓

CSDN上看到一条题目：  觉得经典 自己还没怎么研究 先给出chinese_submarine的解决方案吧

 一个农夫养了一头牛，三年后，这头牛每年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……问农夫10年后有多少头牛?n年呢？

chinese_submarine 给的解决方案

首先可以联系斐波那契数列，设f(n)为第n年的牛，则

f(n) = f(n – 1) + f(n – 2)————>表达式1-1

即第n年的牛为去年牛的个数f(n – 1)加上今年出生牛的个数,那么今年有多少头牛能生呢？（不考虑死亡的牛）则为前年牛的个数即f(n – 2)，因为前年的牛今年至少3岁，即为表达式1-1。

推广一下，将牛生育年龄设为m，那么计算的表达式就变为

f(n) = f(n – 1) + f(n – m + 1)————>表达式1-2

即n-1年牛的个数加上n-m+1年的牛生出的小牛。

那么下面讨论一个稍微复杂点的问题，如果增加一个条件，即牛会在第８年死去，那么第n年会有多少条牛呢？

为了便于推导，这里先设几个函数:

• f(n)即第n年牛的个数
• h(n)即第n年出生的牛的个数
• g(n)即第n年死亡的牛的个数

那么这里可以首先想到一个表达式:

(1)f(n) = f(n -1) + h(n) – g(n)

即第n年牛的个数为第n-1年牛的个数+第n年出生的牛的个数-第n年死亡的牛的个数

而第二个表达式即关于新增牛的个数h(n)的：

(2)h(n) = f(n – 2) – g(n – 1)

即第n年出生的牛的个数为第n-2年牛的个数减去在第n-1年死亡的牛的个数

再看第三个表达式关于第n年死亡的牛的个数的：

(3)g(n)=h(n – 7)

即第n年死亡的牛的个数为第n – 7年出生的牛的个数，这是一个对称的关系。

推导的步骤如下，将(2)代入(1)

即f(n) = f(n – 1) + f(n – 2)- g(n – 1) – g(n)—->（4）

再将(3)式代入(4)

即f(n) = f(n – 1) + f(n – 2) – h(n – – h(n – 7)—–>(5)

再将（2）式代入（5）的h(n – 7)

即f(n) = f(n – 1) + f(n – 2) – (h(n – + f(n – 9) – g(n – 8))

到了这里不难看出(h(n – + f(n – 9) – g(n – 8))即为f(n – 8)通过式(1)。

则最终的表达式为

f(n) = f(n – 1) + f(n – 2) – f(n –

即第n年牛的个数为第n-1年牛的个数+第n-2年牛的个数-第n-8年牛的个数

当牛的生育年龄用a表示，死亡年龄用b表示时，则表示为：

f(n) = f(n – 1) + f(n – a +　１) – f(n – b)

验证程序如下：

using System;
namespace TopCoder

{

    class Program

    {

        static void Main(string[] args)

        {

            FeedCow feedCow = new FeedCow();

            for (int i = 1; i < 30; ++i)

            {

                int sum = feedCow.Feed(i, 5, 7);

                Console.WriteLine(“{0}:{1}“, i, sum);

            }

        }

    }

    /// <summary>

    ///

    /// </summary>

    /// <param name=”year”>要计算的年限</param>

    /// <param name=”age”>牛的生育年龄</param>

    /// <param name=”deadAge”>牛的死亡年龄</param>

    /// <returns></returns>

    public int Feed(int year, int age, int deadAge)

    {

        int sum = 1;

        int min = deadAge < year ? deadAge : year;

        for (int i = age; i <= min; ++i)

        {

            sum += Feed(year - i + 1, age, deadAge);

        }

        return sum;

    }