算法單源最短路徑、多級(jí)調(diào)度實(shí)驗(yàn)報(bào)告

中南大學(xué)算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告姓名：吳冰專業(yè)班級(jí)：軟件1002學(xué)號(hào)：3902100216指導(dǎo)教師：劉莉平完成日期：2011.11一實(shí)驗(yàn)名稱貪心算法實(shí)驗(yàn)二實(shí)驗(yàn)?zāi)康牧私庳澬乃惴ㄋ枷胝莆肇澬姆ǖ湫蛦栴}，如背包問題、作業(yè)調(diào)度問題等。三、實(shí)驗(yàn)內(nèi)容(1)編寫一個(gè)簡(jiǎn)單的程序，實(shí)現(xiàn)單源最短路徑問題。(2)編寫一段程序，實(shí)現(xiàn)找零。【問題描述】當(dāng)前有面值分別為2角5分，1角，5分，1分的硬幣，請(qǐng)給出找n分錢的最佳方案(要求找出的硬幣數(shù)目最少)。編寫程序?qū)崿F(xiàn)多機(jī)調(diào)度問題【問題描述】要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。四、算法思想分析貪心算法：總是做出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心法的基本思路：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。五、算法源代碼及用戶屏幕(1)編寫一個(gè)簡(jiǎn)單的程序，實(shí)現(xiàn)單源最短路徑問題。#include<iostream>#include<stdlib.h>usingnamespacestd;#defineMAX1000000 〃充?當(dāng)ij入"無T窮?大茁?"#defineLENsizeof(structV_sub_S)#defineN5#defineNULL0ints; 〃輸°?入“?的i?源應(yīng)點(diǎn)i?intD[N]; 〃記?錄?最A(yù)?短??-路戸徑？intS[N]; 〃最A(yù)?短??-距?匕離0?已。?確?[0定;§的i?頂如點(diǎn)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é)飛點(diǎn)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)點(diǎn)i?s(0至【」I?4之?間?)：";cin>>s;head=create();Dijkstra(head,s);head=create();Print(head);system("pause");return0;}(2)編寫一段程序，實(shí)現(xiàn)找零?！締栴}描述】當(dāng)前有面值分別為2角5分,1角，5分，1分的硬幣，請(qǐng)給出找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"請(qǐng)輸入付款金額(分)：";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"個(gè)"<<""vvendl;}}(3)編寫程序?qū)崿F(xiàn)多機(jī)調(diào)度問題【問題描述】要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理但未完工前不允許中斷處理。作業(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ù)小于機(jī)器數(shù){coutvv"最短時(shí)間為"vvset_workl(time,N)vvendl;}else{coutvv"最短時(shí)間為"vvset_work2(time,N)vvendl;}system("PAUSE");}voidsort(intt[],intn){for(intk=0;kvn-l;k++) //用選擇法將處理時(shí)間從大到小排序{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ù)求解處理時(shí)間總和最長(zhǎng){intmax=t[0];for(inti=1;i<num;i++){if(max<t[i])max=t[i];}returnmax;}intmin(intt[],intm){intmin=0; //min記錄目前處理作業(yè)時(shí)間和最小的機(jī)器號(hào)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);}六、實(shí)驗(yàn)過程分析對(duì)最短路徑中紅點(diǎn)集藍(lán)點(diǎn)集的