小牛生产小牛的问题解决集粹

问题：

          一只刚出生的小牛，4年后生一只小牛，以后每年生一只。现有一只刚出生的小牛，问N年后共有牛多少只？





1.原始笨方法

private int Comput(int years)

        {

            //初始化为1头牛

            int count = 1;

            if (years < 4)

          {

                return count;

            }

            

            while (years - 3 > 0)

            {

                count = count + Comput(years - 3);

                years--;

            }

            return count;





        }

特点:容易理解,不过效率太低.不具有实用价值.



2.采用HashTable优化方案

Hashtable table = new Hashtable();

        public long Compute(int years)

        {

            //初始化为1头牛

            long count = 1;

            if (years <= 3)

          {

                return count;

            }

            int i = 4;

            while (i <= years)

            {

                int subYears = i - 3;

                if (table.ContainsKey(subYears))

              {

                    count = (long)table[subYears];

                }

                else

              {

                    count += Compute((int)(subYears));

                }

                if (!table.ContainsKey(subYears))

              {

                    table.Add(subYears, count);

                }

                i++;

            }

            return (long)count;

        }

特点:在第一种方案的基础上性能有了大幅度的提高.采用HashTable存储老牛的生育曲线,从而达到以后的小牛重复利用老牛的生育曲线.(直接取其生产数量)



3.采用数组的方式描述

public int Compute(int years)

        {

          int[] age = new int[4] { 1, 0, 0, 0 };

            for (int i = 2; i <= years; i++)

            {

                age[3] += age[2];              age[2] = age[1]; 

                age[1] = age[0];

                age[0] = age[3];                 



            }

            return (age[0] + age[1] + age[2] + age[3]);

        }

特点:只采用一个循环搞定,效率极高.



3.采用优化递归公式实现

 f(n)   =   f(n-1)+f(n-3)  [n   >   3]   

 f(n)   =   1                   [0   <   n   <=   3]  

public int Comput(int x)

      {

            if (x < 4) return 1;

            else return Comput(x - 1) + Comput(x - 3);

        }   

特点:代码简洁,功能简单实现,但使用递归当然会牺牲一定的效率作为代价.



前些天在网络上偶然发现的生产小牛问题.于是搜集整理了一下,方便大家共同研究学习使用.

有好的算法大家共同研究^_^