算法單源最短路徑、多級調(diào)度實驗報告

中南大學算法設(shè)計與分析》實驗報告姓名：吳冰專業(yè)班級：軟件1002學號：3902100216指導(dǎo)教師：劉莉平完成日期：2011.11一實驗名稱貪心算法實驗二實驗?zāi)康牧私庳澬乃惴ㄋ枷胝莆肇澬姆ǖ湫蛦栴}，如背包問題、作業(yè)調(diào)度問題等。三、實驗內(nèi)容(1)編寫一個簡單的程序，實現(xiàn)單源最短路徑問題。(2)編寫一段程序，實現(xiàn)找零?！締栴}描述】當前有面值分別為2角5分，1角，5分，1分的硬幣，請給出找n分錢的最佳方案(要求找出的硬幣數(shù)目最少)。編寫程序?qū)崿F(xiàn)多機調(diào)度問題【問題描述】要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。四、算法思想分析貪心算法：總是做出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。五、算法源代碼及用戶屏幕(1)編寫一個簡單的程序，實現(xiàn)單源最短路徑問題。#include<iostream>#include<stdlib.h>usingnamespacestd;#defineMAX1000000 〃充?當ij入"無T窮?大茁?"#defineLENsizeof(structV_sub_S)#defineN5#defineNULL0ints; 〃輸°?入“?的i?源應(yīng)點i?intD[N]; 〃記?錄?最A(yù)?短??-路戸徑？intS[N]; 〃最A(yù)?短??-距?匕離0?已。?確?[0定;§的i?頂如點1?集[￥constintG[N][N]={{0,10,MAX,30,100},{MAX,0,50,MAX,MAX},{MAX,MAX,0,MAX,10},{MAX,MAX,20,0,60},{MAX,MAX,MAX,MAX,0}};typedefstructV_sub_S //V-S鏈旬玄表A^a{intnum;structV_sub_S*next;};structV_sub_S*create(){structV_sub_S*head,*p1,*p2;intn=0;head=NULL;p1=(V_sub_S*)malloc(LEN);p1->num=s;head=p1;for(inti=0;i<N+1;i++){if(i!=s){++n;if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(V_sub_S*)malloc(LEN);p1->num=i;p1->next=NULL;}}free(p1);returnhead;}structV_sub_S*DelMin(V_sub_S*head,inti)//刪;？除y鏈站玄表入中中D值丘為ai的i?結(jié)飛點i?{V_sub_S*p1,*p2;p1=head;while(i!=p1->num&&p1->next!=NULL){p2=p1;p1=p1->next;}p2->next=p1->next;returnhead;}voidDijkstra(V_sub_S*head,ints){structV_sub_S*p;intmin;S[0]=s;for(inti=0;i<N;i++){D[i]=G[s][i];}for(inti=1;i<N;i++){p=head->next;min=p->num;while(p->next!=NULL){if(D[p->num]>D[(p->next)->num])min=(p->next)->num;p=p->next;}S[i]=min;head=DelMin(head,min);p=head->next;while(p!=NULL){if(D[p->num]>D[min]+G[min][p->num]){D[p->num]=D[min]+G[min][p->num];}p=p->next;}}}voidPrint(structV_sub_S*head){structV_sub_S*p;p=head->next;while(p!=NULL){if(D[p->num]!=MAX){cout<<"D["<<p->num<<"]:"<<D[p->num]<<endl;p=p->next;}else{cout<<"D["<<p->num<<"]:"<<〃8T"vvendl;p=p->next;}}}intmain(){structV_sub_S*head;cout<<"輸°?入“?源應(yīng)點i?s(0至【」I?4之?間?)：";cin>>s;head=create();Dijkstra(head,s);head=create();Print(head);system("pause");return0;}(2)編寫一段程序，實現(xiàn)找零?！締栴}描述】當前有面值分別為2角5分,1角，5分，1分的硬幣，請給出找n分錢的最佳方案(要求找出的硬幣數(shù)目最少)?！ㄝ斎耄簲?shù)組m,依次存放從大到小排列的面值數(shù)，n為需要找的錢數(shù)，單位全部為分//輸出：找錢方案#include<iostream>usingnamespacestd;#defineNUM4voidmain(){intm[NUM]={25,10,5,1};intmeishu[NUM]={0,0,0,0};intn;//假設(shè)n=99coutvv"請輸入付款金額(分)：";cin>>n;coutvvnvv"分的找錢方案為："vvendl;for(inti=0;i<NUM;i++){while(n>=m[i]&&n>0)meishu[i]++;//cout<<m[i]<<""n-=m[i];}coutvvm[i]vv"分需要"vvmeishu[i]vv"個"<<""vvendl;}}(3)編寫程序?qū)崿F(xiàn)多機調(diào)度問題【問題描述】要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。約定，每個作業(yè)均可在任何一臺機器上加工處理但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。#includeviostream>usingnamespacestd;#defineN10#defineM3voidsort(intt[],intn);intset_work1(intt[],intn);intmax(intt[],intnum);intmin(intt[],intm);intset_work2(intt[],intn);staticinttime[N]={2,8,18,32,50,72,98,128,182,200},s[M]={0,0,0};voidmain(){sort(time,N);if(M>=N) //作業(yè)數(shù)小于機器數(shù){coutvv"最短時間為"vvset_workl(time,N)vvendl;}else{coutvv"最短時間為"vvset_work2(time,N)vvendl;}system("PAUSE");}voidsort(intt[],intn){for(intk=0;kvn-l;k++) //用選擇法將處理時間從大到小排序{intj=k;for(inti=k;ivn;i++){if(t[i]>t[j]){j=i;}}{inttemp=t[j];t[j]=t[k];t[k]=temp;}intmax(intt[],intnum)//max函數(shù)求解處理時間總和最長{intmax=t[0];for(inti=1;i<num;i++){if(max<t[i])max=t[i];}returnmax;}intmin(intt[],intm){intmin=0; //min記錄目前處理作業(yè)時間和最小的機器號for(inti=1;i<m;i++){if(s[min]>s[i])min=i;}returnmin;}intset_work1(intt[],intn){intm=0;for(inti=0;i<n;i++)//分派作業(yè){s[m++]+=t[i];}returnmax(s,N);intset_work2(intt[],intn){for(inti=0;i<n;i++){s[min(s,M)]+=t[i];}returnmax(s,M);}六、實驗過程分析對最短路徑中紅點集藍點集的