算法設(shè)計(jì)與分析課程設(shè)計(jì)--用貪心算法解決汽車加油次數(shù)最少問題-預(yù)覽頁
【正文】 加油 站間的距離相等，即ａ [i]=a[j]=L=N，則加油次數(shù)最少 k=n； B： 加油站間的距離相等，即ａ [i]=a[j]=LN，則不可能到達(dá)終點(diǎn)； C： 加油站間的距離相等， 即ａ [i]=a[j]=LN，則加油次數(shù)k=n/N(n%N==0)或 k=[n/N]+1(n%N！ =0)； D： 加油站間的距離不相等，即ａ [i]！ =a[j]，則加油次數(shù) k通過以下算法求解。 不斷地 將問題實(shí)例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個全局得最優(yōu)解。 （２）解決：對于每一個階段求局部的最優(yōu)解。在局部找到一個最優(yōu)的解。 for(int i=m。 } int Tanxin(int a[n], int N) //a[n]表示加油站的個數(shù)， N為加滿油能行駛的最遠(yuǎn)距離 { int b[n]。 return add(b[i],0,n)。 return add(b[i],0,n)。amp。 } if(a[i]!=a[j]) { //如果每相鄰的兩個加油站間的距 離不相等且都小于 N if( add(a[i],m,k) N amp。 return add(b[i],0,n)。 scanf(/d,amp。對于一個具體的問題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的一個整體最優(yōu)解。 四、 貪心算法時間復(fù)雜度分析 由于若想知道該在哪個加油站加油就必須遍歷所有的加油站，且不需要重復(fù)遍歷，所以時間復(fù)雜度為 O(n)。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1