算法設(shè)計(jì)與分析課程設(shè)計(jì)--用貪心算法解決汽車加油次數(shù)最少問題(存儲(chǔ)版)
【正文】 （ b[2],b[3],??b[n]）是從 a[2]到 a[n]這段路 程 上 加 油 次 數(shù) 最 少 且 這 段 路 程 上 的 加 油 站 個(gè) 數(shù) 為（ a[2],a[3],??a[n]）的最優(yōu)解 ,即每次汽車中剩下的油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油，每個(gè)過 程從加油開始行駛到再次加油滿足貪心且每一次加油后 ， 相當(dāng)于與起點(diǎn)具有相同的條件，每個(gè)過程都是相同且獨(dú)立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 scanf(/n)。 } return add(b[i],0,n)。a[i]==N) { //如果相鄰的兩個(gè)加油站間的距離都是 N，每個(gè)加油站 都加油 b[i]=1。 return sb。提出問題是解決的開始 ， 為了著手解決遇到的困難 ， 取得最優(yōu)方案 ， 我們可以假設(shè)不到萬不得已我們不加油，即除非我們油箱里的油不足以開到下一個(gè)加油站，我們才加一次油。推進(jìn)的每一階段 不是依據(jù)某一個(gè)固定的遞推式，而是在每一個(gè)階段都看上去是一個(gè)最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下） 。 實(shí)驗(yàn)方法 ： 貪心算法 實(shí)驗(yàn)內(nèi)容： 一 、 問題描述 一輛汽車加滿油后可以行駛 N 千米。給出 N，并以數(shù)組的形式給出加油站的個(gè)數(shù)及相鄰距離，指出若要使沿途的加油次數(shù)最少，設(shè) 計(jì)一個(gè)有效的算法，指出應(yīng)在那些加油站?？考佑?。 （２）最優(yōu)子結(jié)構(gòu)： 問題的整體最優(yōu)解
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1