算法分析實驗報告--貪心算法.doc

《算法分析實驗報告--貪心算法.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

1、《算法設計與分析》實驗報告貪心算法姓名：XXX專業(yè)班級：XXX學號：3XXX指導教師：XXX完成日期：XXX一、試驗名稱：貪心算法（1）寫出源程序，并編譯運行（2）詳細記錄程序調(diào)試及運行結果二、實驗目的(1)了解貪心算法思想(2)掌握貪心法典型問題，如背包問題、作業(yè)調(diào)度問題等。三、實驗內(nèi)容(1)編寫一個簡單的程序，實現(xiàn)單源最短路徑問題。(2)編寫一段程序，實現(xiàn)找零。(3)編寫程序實現(xiàn)多機調(diào)度問題四、算法思想分析(1)編寫一個簡單的程序，實現(xiàn)單源最短路徑問題。用P，T分別表示某個點的P標號、T標號，si

2、表示第i步時，具P標號點的集合。為了在求出從vs到各點的距離的同時，也求出從Vs到各點的最短路，給每個點v以一個λ值，算法終止時λ(v)=m，表示在Vs到v的最短路上，v的前一個點是Vm；如果λ(v)=∞，表示圖G中不含從Vs到v的路；λ(Vs)=0。(2)編寫一段程序，實現(xiàn)找零。先舉個例子，假如老板要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數(shù)，為了找給我最少的硬幣數(shù)，那么他是不是該這樣找呢，先看看該找多少個25分的，99／25＝3，好像是3個，要是4個的話，我們還得再給老板一個1

3、分的，我不干，那么老板只能給我3個25分的拉，由于還少給我24，所以還得給我2個10分的和4個1分。(3)編寫程序實現(xiàn)多機調(diào)度問題1、把作業(yè)按加工所用的時間從大到小排序2、如果作業(yè)數(shù)目比機器的數(shù)目少或相等，則直接把作業(yè)分配下去3、如果作業(yè)數(shù)目比機器的數(shù)目多，則每臺機器上先分配一個作業(yè)，如下的作業(yè)分配時，是選那個表頭上s最小的鏈表加入新作業(yè)。五、算法源代碼及用戶屏幕(1)編寫一個簡單的程序，實現(xiàn)單源最短路徑問題。//Dijkstra算法#include#include

4、>usingnamespacestd;#defineVEX5//定義結點的個數(shù)#definemaxpoint100doublegraph[][maxpoint]={{0,10,-1,30,100},{-1,0,50,-1,-1},{-1,-1,0,-1,10},{-1,-1,20,0,60},{-1,-1,-1,-1,0}};//鄰接矩陣voidmain(){intR[maxpoint]={0},B[maxpoint];intD[VEX],P[VEX];//定義數(shù)組D用來存放結點特殊距離，P數(shù)組存放父

5、親結點//初始時，紅點集中僅有源結點0R[0]=1;B[0]=0;for(inti=1;i

6、

7、<"";//將具有最短特殊路長度的結點min添加到紅點集中R[min]=1;B[min]=0;//對數(shù)組D作必要的修改for(j=1;jD[min]+graph[min][j]

8、

9、D[j]==-1){D[j]=D[min]+graph[min][j];//每次迭代求最小值，最后一次即為到源點的最短路徑P[j]=min;}//輸出最短路徑for(i=0;i

10、i]<<"";cout<<"";for(i=0;i#defineMax25#defineMid10#defineNext5#defineMin1usingnamespacestd;inti=0;intj=0;intk=0;ints=0;inta,b,c;voidchangeMoney(intm){if(m>=Max)