C#算法之大牛生小牛的問題高效解決方法
問題：
一只剛出生的小牛，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年
50年
源程序以及測試程序：http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar
以上就是本文的全部內(nèi)容，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
從IE瀏覽器獲取當(dāng)前頁面內(nèi)容可能有多種方式，今天我所介紹的是其中一種方法?；驹恚寒?dāng)鼠標(biāo)點(diǎn)擊當(dāng)前IE頁面時(shí)，獲取鼠標(biāo)的坐標(biāo)位置，根據(jù)鼠標(biāo)位置獲取當(dāng)前頁面的句柄，然后根據(jù)句柄，調(diào)用win32的東西進(jìn)而獲取頁面內(nèi)容。感興趣的朋友可以參考下本文2021-06-06
WPF調(diào)用ffmpeg實(shí)現(xiàn)屏幕錄制
這篇文章主要為大家詳細(xì)介紹了WPF如何調(diào)用ffmpeg實(shí)現(xiàn)屏幕錄制，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)或工作有一定幫助，感興趣的小伙伴可以了解一下2023-05-05
這篇文章主要介紹了C#泛型和反射實(shí)例解析,對于C#初學(xué)者理解泛型和反射有很好的幫助借鑒作用,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細(xì)介紹了winform實(shí)現(xiàn)五子棋游戲，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
C#實(shí)現(xiàn)Excel導(dǎo)入sqlite的方法
這篇文章主要介紹了C#實(shí)現(xiàn)Excel導(dǎo)入sqlite的方法,是C#程序設(shè)計(jì)中非常重要的一個(gè)實(shí)用技巧,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了C#獲得文件屬性信息的實(shí)現(xiàn)方法,對于C#初學(xué)者了解與學(xué)習(xí)應(yīng)用程序設(shè)計(jì)有一定的借鑒價(jià)值,需要的朋友可以參考下2014-07-07
用c#實(shí)現(xiàn)簡易的計(jì)算器功能實(shí)例代碼
這篇文章主要介紹了c#實(shí)現(xiàn)簡易的計(jì)算器功能，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
本文主要介紹了C#中利用GDI來繪制圖形和文字的方法，并提供的簡單的示例供大家參考學(xué)習(xí)，希望能夠?qū)Υ蠹矣兴鶐椭?/div> 2016-03-03
.NET實(shí)現(xiàn)定時(shí)發(fā)送郵件代碼（兩種方式）
經(jīng)常發(fā)郵件的朋友都知道，郵箱有個(gè)特殊功能，可以設(shè)定郵件發(fā)送時(shí)間，定時(shí)發(fā)送，這個(gè)功能是怎么實(shí)現(xiàn)的呢？接下來，小編給大家分享.NET實(shí)現(xiàn)定時(shí)發(fā)送郵件的代碼，有需要的朋友可以參考下2015-08-08
本文主要介紹了C#中new的幾種用法，具有很好的參考價(jià)值，下面跟著小編一起來看下吧2017-02-02最新評論