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

2020-01-24 01:06:09

字體：大中小

來源：轉載

供稿：網友

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

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;}

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

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;}

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

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

測試結果截圖：

20年