問題：
????????? 一只剛出生的小牛，4年后生一只小牛，以后每年生一只。現(xiàn)有一只剛出生的小牛，問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優(yōu)化方案
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存儲老牛的生育曲線,從而達到以后的小牛重復利用老牛的生育曲線.(直接取其生產(chǎn)數(shù)量)

3.采用數(shù)組的方式描述
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]);
????????}
特點:只采用一個循環(huán)搞定,效率極高.

3.采用優(yōu)化遞歸公式實現(xiàn)
?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);
????????}???
特點:代碼簡潔,功能簡單實現(xiàn),但使用遞歸當然會犧牲一定的效率作為代價.

前些天在網(wǎng)絡上偶然發(fā)現(xiàn)的生產(chǎn)小牛問題.于是搜集整理了一下,方便大家共同研究學習使用.
有好的算法大家共同研究^_^

轉載于:https://www.cnblogs.com/symbol441/archive/2008/02/19/1073291.html

總結

以上是生活随笔為你收集整理的小牛生产小牛的问题解决集粹的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。