問題：
　　一只剛出生的小牛，4年后生一只小牛，以后每年生一只?，F(xiàn)有一只剛出生的小牛，問20年后共有牛多少只？
思路：
　　這種子生孫，孫生子，子子孫孫的問題，循環(huán)里面還有循環(huán)的嵌套循環(huán)，一看就知道是第歸問題。
于是乎,第一個版本出現(xiàn)：

public long Compute1(uint years)
{
  //初始化為1頭牛
  long count = 1;
  if (years <= 3)
  {
    return count;
  }
  int i = 4;
  while (i <= years)
  {
    int subYears = i - 3;
    count += Compute1((uint)(subYears));
    i++;
  }
  return (long)count;
}

　　可是這種循環(huán)在循環(huán)的做法可要把cpu老兄累壞了，你不信輸入一個100年測試一下上面的方法，我等了半天，都沒結(jié)果，改進(jìn)一下吧，老牛（牛魔王）和小牛（紅孩兒，奶奶的串種了），具有相同的生育能力，他們的生育曲線是一樣的，所以小牛可以復(fù)用老牛的生育經(jīng)驗(yàn)亞，這樣就解決了重復(fù)計算一只牛第n年的時候一共生多少只的問題了，當(dāng)年齡比較大的時候，明顯大大降低cpu的運(yùn)算次數(shù)，下面是基于這種思路的算法

Hashtable table = new Hashtable();
public long Compute(uint 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((uint)(subYears));
    }
    if (!table.ContainsKey(subYears))
    {
      table.Add(subYears, count);
    }
    i++;
  }
  return (long)count;
}

用測試程序測試一下上面的推論吧，結(jié)果如下:

1）當(dāng)輸入years比較小的時候，第一種方法耗時短，但兩者的時間基本在一個數(shù)量級上
2）當(dāng)輸入years比較大的時候，比如40以上的，第二種算法比第一種性能比在100以上，而且輸入years越高，性能比越懸殊。

測試結(jié)果截圖：

20年

50年

源程序以及測試程序：http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar

以上就是本文的全部內(nèi)容，希望能給大家一個參考，也希望大家多多支持我們。