算法分析-貪心算法解汽車加油問題-實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上綜合性、設(shè)計(jì)性實(shí)驗(yàn)報(bào)告姓名 唐艷 學(xué)號(hào) 4專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí)2009級(jí) 班實(shí)驗(yàn)課程名稱 算法設(shè)計(jì)與分析 指導(dǎo)教師及職稱 呂蘭蘭 講師 開課學(xué)期 2011 至 2012 學(xué)年 上 學(xué)期上課時(shí)間 2011年 10 月 18 日 湖南科技學(xué)院教務(wù)處編印專心-專注-專業(yè)一、實(shí)驗(yàn)設(shè)計(jì)方案實(shí)驗(yàn)名稱：貪心算法實(shí)例編程實(shí)驗(yàn)時(shí)間：2011-11-08 小組合作： 是 否小組成員：無1、實(shí)驗(yàn)?zāi)康模?1) 理解貪心算法的概念2) 掌握貪心算法的基本要素3) 掌握設(shè)計(jì)貪心算法的一般步驟4) 針對(duì)具體問題，能應(yīng)用貪心算法設(shè)計(jì)有效算法5) 用C+實(shí)現(xiàn)算法，并且分析算法的效率2、實(shí)驗(yàn)設(shè)備

2、及材料：（注意：請(qǐng)自行填寫，按實(shí)際情況寫，各位同學(xué)的實(shí)驗(yàn)報(bào)告應(yīng)有所區(qū)別）硬件設(shè)備： PC機(jī)一臺(tái)機(jī)器配置：良好操作系統(tǒng)：windows 7開發(fā)工具：VC+6.03、實(shí)驗(yàn)內(nèi)容： 問題描述一輛汽車加滿油后可行駛n公里。旅途中有若干個(gè)加油站。設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站停靠加油，使沿途加油次數(shù)最少。并說明算法能產(chǎn)生一個(gè)最優(yōu)解。編程任務(wù)對(duì)于給定的n和k個(gè)加油站位置，編程計(jì)算最少加油次數(shù)。樣例例如，現(xiàn)在汽車加滿油之后可跑7公里，途中共有7個(gè)加油站，各個(gè)加油站之間的距離為1公里、2公里、3公里、4公里、5公里、1公里、6公里、6公里。那么，汽車可在_第三，第四，第五，第七個(gè)加油站_（哪幾個(gè)加油站）加

3、油，使沿途加油次數(shù)最少，只需加油_4_次。4、實(shí)驗(yàn)方法步驟及注意事項(xiàng)：（注意：此部分為本實(shí)驗(yàn)的關(guān)鍵部分，請(qǐng)自行填寫，不得雷同！）實(shí)驗(yàn)步驟（請(qǐng)參考教材自行總結(jié)歸納之后再認(rèn)真填寫）問題分析由于汽車是由始向終點(diǎn)方向開的,我們最大的麻煩就是不知道在哪個(gè)加油站加油可以使我們既可以到達(dá)終點(diǎn)又可以使我們加油次數(shù)最少。提出問題是解決的開始.為了著手解決遇到的困難,取得最優(yōu)方案。我們可以假設(shè)不到萬不得已我們不加油，即除非我們油箱里的油不足以開到下一個(gè)加油站，我們才加一次油。在局部找到一個(gè)最優(yōu)的解。卻每加一次油我們可以看作是一個(gè)新的起點(diǎn)，用相同的方法進(jìn)行下去。最終將各個(gè)階段的最優(yōu)解合并為原問題的解得到我們?cè)瓎栴}的

4、求解。加油站貪心算法設(shè)計(jì)（C+）：#include<stdio.h>#include"iostream.h"#include <fstream.h>int greed(int n,int k,int *a)int sum=0,count=0;ifstream fin;fin.open("D:input.txt");ofstream fout("D:output.txt");for(int i=1;i<=k+1;i+)sum+=ai;if(sum>n)count+;sum=0;i-;fout<&

5、lt;i<<","return count;int main() int n,k,i,number;int a100;ifstream fin;fin.open("D:input.txt");ofstream fout("D:output.txt"); fin>>n;fin>>k;for(i=1;i<=k+1;i+)fin>>ai;if(ai>n)printf("No Soluthion!");elsenumber=greed(n,k,a);fout<

6、;<number;解題思路（注意：以下部分僅為提示，請(qǐng)自行填寫；若表格不夠，可自行拉伸。）1) 確定求解汽車加油問題的貪心選擇策略。2) 給出使用貪心算法求解汽車加油問題的算法，用C+語言描述。要求：求解汽車加油問題時(shí)，不僅要求出所需的最小加油次數(shù)（即最優(yōu)值），而且還要求出應(yīng)在哪些加油站加油（即最優(yōu)解）。3) 證明上述算法的正確性。（可選） 需證明：汽車加油問題始終存在以貪心選擇開始的最優(yōu)解，以及汽車加油問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法正確性證明：l 貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。對(duì)于一個(gè)具體的問題，要確定它是否具有貪

7、心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的一個(gè)整體最優(yōu)解。根據(jù)貪心選擇，在該題中，為使加油次數(shù)最少就會(huì)選擇距離加滿油得點(diǎn)遠(yuǎn)一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。l 最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個(gè)問題大的最優(yōu)解包含著它的子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由于（b1,b2,bn）是這段路程加油次數(shù)最少的一個(gè)滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個(gè)加油站加油時(shí)，b1=1,則（b2,b3,bn）是從 a2到an這段路程上加油次數(shù)最少且這段路程上的加油站個(gè)數(shù)為（a2,a3,an）的最優(yōu)解，再者，每個(gè)過程從加油開始行駛到再次加油滿足貪心且每一次加油后相當(dāng)于與起點(diǎn)具有相同

8、的條件，每個(gè)過程都是相同且獨(dú)立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。5實(shí)驗(yàn)數(shù)據(jù)處理方法：數(shù)據(jù)輸入由文件input.txt給出輸入數(shù)據(jù)。第一行有2 個(gè)正整數(shù)n和k，表示汽車加滿油后可行駛n公里，且旅途中有k個(gè)加油站。接下來的1 行中，有k+1 個(gè)整數(shù)，表示第k個(gè)加油站與第k-1 個(gè)加油站之間的距離。第0 個(gè)加油站表示出發(fā)地，汽車已加滿油。第k+1 個(gè)加油站表示目的地。結(jié)果輸出將編程計(jì)算出的最少加油次數(shù)以及應(yīng)在哪些加油站加油輸出到文件output.txt。如果無法到達(dá)目的地，則輸出”No Solution”。6參考文獻(xiàn)：計(jì)算機(jī)算法設(shè)計(jì)與分析（第3版） 王曉東著 電子工業(yè)出版社算法設(shè)計(jì)與實(shí)驗(yàn)題解

9、王曉東著 電子工業(yè)出版社指導(dǎo)老師對(duì)實(shí)驗(yàn)設(shè)計(jì)方案的意見：指導(dǎo)老師簽名：呂蘭蘭 2011年 11 月 10 日 2、 實(shí)驗(yàn)報(bào)告1、實(shí)驗(yàn)?zāi)康?、設(shè)備與材料、實(shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)方法步驟見實(shí)驗(yàn)設(shè)計(jì)方案2、實(shí)驗(yàn)現(xiàn)象、數(shù)據(jù)及結(jié)果（請(qǐng)自行填寫真實(shí)結(jié)果）序號(hào)輸入文件(input.txt)輸出文件(output.txt)0.7 71 2 3 4 5 1 6 641.3708 633 20 83 77 26 59 6702.630 3746 43 94 77 45 98 11 60 15 42 7 69 61 54 51 65 50 16 28 60 91 17 44 54 93 52 32 54 41 80 88 54

10、 55 27 58 59 92 7333.181 4654 94 61 51 51 57 73 96 32 45 97 73 44 88 25 14 53 59 79 41 63 100 25 57 35 55 61 88 54 40 77 1 53 86 67 59 13 56 96 56 75 45 37 76 99 41 94183、對(duì)實(shí)驗(yàn)現(xiàn)象、數(shù)據(jù)及觀察結(jié)果的分析與討論：（對(duì)輸入數(shù)據(jù)和相應(yīng)輸出結(jié)果按照你所設(shè)計(jì)的算法進(jìn)行分析，舉12個(gè)例子即可。要求分析出一個(gè)輸入的最優(yōu)解。）例：輸入：7 8 1 3 5 1 5 4 1 6 7輸出：54、結(jié)論：（包括：使用的算法設(shè)計(jì)方法是否正確，是否也可以

11、用其他方法解決，算法效率如何？程序的編譯是否通過，程序的輸出結(jié)果是否正確等）該實(shí)驗(yàn)使用的算法基本正確，程序編譯通過。程序結(jié)果正確。時(shí)間復(fù)雜度為O(n)。5、實(shí)驗(yàn)總結(jié)1）、本次實(shí)驗(yàn)成敗之處及其原因分析：注：從技術(shù)角度來分析實(shí)驗(yàn)的成功或失敗，分析實(shí)驗(yàn)過程中出現(xiàn)了哪些問題，程序出現(xiàn)了什么錯(cuò)誤，出現(xiàn)錯(cuò)誤的具體原因是什么，以及是如何解決的。本次實(shí)驗(yàn)基本成功。只是最后輸出加油的次數(shù)的數(shù)據(jù)覆蓋了之前寫入output文件中的在第1次在哪個(gè)加油站加油的數(shù)據(jù)。不知道應(yīng)該在文件打開的語句中修改，使它可以在已經(jīng)存在的文件中追加數(shù)據(jù)，而不是覆蓋。2）、本實(shí)驗(yàn)的關(guān)鍵環(huán)節(jié)及改進(jìn)措施：做好本實(shí)驗(yàn)需要把握的關(guān)鍵環(huán)節(jié)： 在greed函數(shù)中，判斷sum>n后，i的次數(shù)要減1。因?yàn)樵诰嚯x大