快捷導(dǎo)航

C#算法之大牛生小牛的問題高效解決方法

更新時(shí)間：2016年06月16日 09:55:38 作者：Robin

本文主要介紹兩種方法處理大牛生小牛的問題，第二種效率更高，希望能給大家一個(gè)參考。

問題：
　　一只剛出生的小牛，4年后生一只小牛，以后每年生一只?，F(xiàn)有一只剛出生的小牛，問20年后共有牛多少只？
思路：
　　這種子生孫，孫生子，子子孫孫的問題，循環(huán)里面還有循環(huán)的嵌套循環(huán)，一看就知道是第歸問題。
于是乎,第一個(gè)版本出現(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老兄累壞了，你不信輸入一個(gè)100年測試一下上面的方法，我等了半天，都沒結(jié)果，改進(jìn)一下吧，老牛（牛魔王）和小牛（紅孩兒，奶奶的串種了），具有相同的生育能力，他們的生育曲線是一樣的，所以小?？梢詮?fù)用老牛的生育經(jīng)驗(yàn)亞，這樣就解決了重復(fù)計(jì)算一只牛第n年的時(shí)候一共生多少只的問題了，當(dāng)年齡比較大的時(shí)候，明顯大大降低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í)候，第一種方法耗時(shí)短，但兩者的時(shí)間基本在一個(gè)數(shù)量級上
2）當(dāng)輸入years比較大的時(shí)候，比如40以上的，第二種算法比第一種性能比在100以上，而且輸入years越高，性能比越懸殊。

測試結(jié)果截圖：

20年