算法的優(yōu)化示例

算法的優(yōu)化示例學(xué)習(xí)目標(biāo)知識(shí)目標(biāo)：了解算法的優(yōu)化思想。技能目標(biāo)：能對(duì)所選用的方法進(jìn)行優(yōu)化設(shè)計(jì)。情感目標(biāo)：1.能夠多角度考慮問題。2.養(yǎng)成細(xì)致周全的思考習(xí)慣。算法優(yōu)化之事例一算法：指解決問題的步驟與方法。算法的優(yōu)化：指從多個(gè)解決問題的方法中選擇其中最簡(jiǎn)潔、最高效的方法的過程。事例一“高斯問題〞的分析與優(yōu)化算法優(yōu)化之前：計(jì)算機(jī)從1開始循環(huán)，一直累加到100，需要運(yùn)行100次。算法優(yōu)化之后：將1+2+……100的問題轉(zhuǎn)換為101×50的問題，只需要運(yùn)行一次。結(jié)論：“高斯問題〞經(jīng)過算法優(yōu)化之后，計(jì)算機(jī)運(yùn)行次數(shù)從之前的100次減少到1次，運(yùn)行效率大大提高。算法優(yōu)化之事例二welcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience“燒水泡茶〞問題的分析與優(yōu)化家里來客人時(shí)，需要燒水泡茶，其工作有如下幾項(xiàng)：燒開水〔15分鐘〕，洗茶壺〔2分鐘〕，洗茶杯〔1分鐘〕，拿茶葉〔1分鐘〕，沏茶。做完這項(xiàng)工作至少有三種方法，試分析哪一種方法可以最快地讓客人喝上茶。方法一洗茶壺，洗茶杯，拿茶葉燒水水開沏茶總計(jì)用時(shí)：20分鐘方法二燒水燒水過程中洗茶壺茶杯，拿茶葉水開沏茶總計(jì)用時(shí)：16分鐘方法三燒水水開后，洗茶壺茶杯，拿茶葉水開沏茶總計(jì)用時(shí)：20分鐘結(jié)論三種方法中，只有第二種方法很好的利用了燒水過程中的時(shí)間去完成洗茶壺、洗茶杯、拿茶葉等的工作，效率最高、用時(shí)最短，屬于最優(yōu)化的方法。算法優(yōu)化之任務(wù)一李明從早上起床到上學(xué)前這段時(shí)間為25分鐘，他要做以下幾件事：疊被〔2分鐘〕，洗臉〔3分鐘〕，刷牙〔2分鐘〕，刷鍋〔1分鐘〕，煮雞蛋〔10分鐘〕，吃早點(diǎn)〔10分鐘〕。請(qǐng)為李明設(shè)計(jì)一個(gè)最節(jié)省時(shí)間的合理方法。答案刷鍋煮雞蛋煮雞蛋過程中疊被洗臉?biāo)⒀莱栽琰c(diǎn)總計(jì)用時(shí)：21分鐘算法優(yōu)化之任務(wù)二“百錢買百雞〞問題的算法優(yōu)化優(yōu)化前：對(duì)母雞、公雞和小雞數(shù)量都從1到100取值，各層循環(huán)均需循環(huán)100次，因此總循環(huán)次數(shù)為：100×100×100=1百萬次。運(yùn)算量太大，可作如下分析來進(jìn)行算法優(yōu)化：首先，考慮到每只母雞為3元，因此，最多只能買33只母雞，故第一層循環(huán)只需要從1到33即可。其次，考慮到每只公雞為2元，因此，最多只能買50只公雞，又因?yàn)樵谏厦娴牡谝粚友h(huán)中已確定了母雞的數(shù)量，因此公雞數(shù)量最多為50減去母雞數(shù)量，即第二層循環(huán)只需要從1到“50減去母雞數(shù)量〞即可。最后，由于上面兩層已經(jīng)分別確定了母雞和公雞的數(shù)量，考慮到總共需要買100只雞，故小雞的數(shù)量只能是“100-母雞數(shù)量-公雞數(shù)量〞，即第三層的循環(huán)已沒有必要了。優(yōu)化后：總循環(huán)次數(shù)最多為：33×50×1=1650次?！鞍馘X買百雞〞代碼比照算法優(yōu)化之任務(wù)三“韓信點(diǎn)兵〞問題的算法優(yōu)化韓信每次集合部隊(duì)，都要求部下報(bào)3次數(shù)，第一次按1到3報(bào)數(shù)，第二次按1到5報(bào)數(shù)，第三次按1到7報(bào)數(shù)，每次報(bào)數(shù)后都要求最后一個(gè)人報(bào)告他報(bào)告的數(shù)是幾，這樣韓信就知道士兵總共有多少人了。

仔細(xì)閱讀課本P36頁關(guān)于“韓信點(diǎn)兵〞問題的分析，結(jié)合本節(jié)課所學(xué)的“算法優(yōu)化〞的思想，課下思考如何對(duì)“韓信點(diǎn)兵〞問題進(jìn)行算法優(yōu)化。優(yōu)化后算法的特點(diǎn)算法著眼于解決問題，不同的算法雖然都能夠最終解決問題，但是它們所消耗的時(shí)間卻不盡相同，對(duì)于計(jì)算機(jī)內(nèi)存的占用也同樣不同。總的來說，優(yōu)化