貪心的孩子的故事五篇范文-在線瀏覽
2024-11-04 12:39本頁面
【正文】 已酒足飯飽，這時(shí)已經(jīng)是下午兩點(diǎn)鐘了。小故事有大智慧：這個(gè)故事告訴我們：魚和熊掌不可兼得，貪心只會讓你會失去的更多。二、實(shí)驗(yàn)內(nèi)容題目見P143:416,、實(shí)驗(yàn)要求（1）用分治法求解最少加油次數(shù)和最少硬幣個(gè)數(shù)問題；（2）再選擇自己熟悉的其它方法求解本問題；（3）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的所有算法；四、實(shí)驗(yàn)過程設(shè)計(jì)（算法設(shè)計(jì)過程）（1）最少加油次數(shù) 實(shí)驗(yàn)題目一輛汽車加滿油以后可以行使n公里，旅途中有若干個(gè)加油站，設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使沿路加油次數(shù)最少。過程設(shè)計(jì)貪心算法總是作出在當(dāng)前看來最好的選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。比如說最少加油次數(shù)的問題。首先人機(jī)互動(dòng)的設(shè)定加滿油以后最長能夠行使的距離，然后輸入了各個(gè)站點(diǎn)之間的距離，在程序的設(shè)計(jì)中，首先檢查了程序的可行性。這個(gè)在實(shí)際情況中也是很容易理解的。采用s這個(gè)來保存現(xiàn)在車?yán)锩媪粝碌挠?，?dāng)此時(shí)留下的有能夠行駛完這一站點(diǎn)到下一站點(diǎn)之間的距離是，在這一站點(diǎn)的時(shí)候就不加油。核心算法如下：for(i=0,s=0。if(sn){sum++。}}（2）最少硬幣個(gè)數(shù)問題 實(shí)驗(yàn)題目考慮下面的用最少硬幣個(gè)數(shù)找出n分錢的問題：當(dāng)使用2角5分，1角，5分和1分四種硬幣面值時(shí)，設(shè)計(jì)一個(gè)找n分錢的貪心算法，并證明算法能產(chǎn)生最優(yōu)解。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。在算法的實(shí)現(xiàn)過程中，當(dāng)剩余的錢數(shù)大于2角5分時(shí)，我們在記錄找2角5分硬幣的個(gè)數(shù)的變量里面加一，同時(shí)把剩余所找的錢的總數(shù)目也減2角5分。5分和1分的硬幣實(shí)現(xiàn)過程同上述過程一樣，一直執(zhí)行到所剩的錢的數(shù)目為0，此時(shí)停止計(jì)算，得到最優(yōu)解。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。這樣和采用動(dòng)態(tài)規(guī)劃的算法相比，算法
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1