算法設(shè)計(jì)與分析 實(shí)驗(yàn)4

《算法設(shè)計(jì)與分析 實(shí)驗(yàn)4》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、測(cè)試過(guò)程：（實(shí)驗(yàn)中出現(xiàn)的問(wèn)題、錯(cuò)誤、解決方法）這是第一個(gè)實(shí)驗(yàn)中由于i這個(gè)變量沒(méi)有在循環(huán)外定義導(dǎo)致的錯(cuò)誤，經(jīng)過(guò)改正后程序就能正常運(yùn)行了。改正前的程序如下：改正后的程序如下：實(shí)驗(yàn)總結(jié)：通過(guò)這個(gè)實(shí)驗(yàn)我對(duì)貪心算法有了一定的了解，但是還很是不熟悉，希望在后的學(xué)習(xí)中能更深入的學(xué)習(xí)并掌握這個(gè)非常有用且好用的算法。簽名：2012年11月21日評(píng)語(yǔ)與成績(jī)：教師簽名：年月日洛陽(yáng)師范學(xué)院信息技術(shù)學(xué)院軟件實(shí)驗(yàn)報(bào)告專(zhuān)業(yè)：__網(wǎng)絡(luò)工程_______課程：_算法設(shè)計(jì)與分析_______學(xué)號(hào)__姓名：______班級(jí)：_網(wǎng)絡(luò)工程___實(shí)驗(yàn)名稱實(shí)驗(yàn)三

2、貪心算法實(shí)例編程實(shí)驗(yàn)類(lèi)型實(shí)踐課實(shí)驗(yàn)時(shí)間2012-11-21實(shí)驗(yàn)環(huán)境計(jì)算機(jī)一臺(tái)實(shí)驗(yàn)?zāi)康呐c要求：1.掌握貪心算法的基本思想。2.能夠編寫(xiě)用貪心算法解決問(wèn)題的程序。3.能對(duì)算法的復(fù)雜度，可靠性進(jìn)行分析。實(shí)驗(yàn)內(nèi)容：1.要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。輸入：第一行：m，n，分別表示機(jī)器數(shù)和作業(yè)數(shù)；第二行：n個(gè)整數(shù)，分別表示n個(gè)作業(yè)所需的加工時(shí)間。輸出：t表示加工時(shí)間。提示：調(diào)度時(shí)

3、間由m臺(tái)機(jī)器中，加工時(shí)間最長(zhǎng)的一個(gè)決定，故貪心選擇的一個(gè)原則應(yīng)該是：盡可能均衡m臺(tái)機(jī)器的負(fù)載（參考木桶原理）。2.一輛汽車(chē)加滿油后可以行駛N千米。旅途中有若干個(gè)加油站。若要使沿途的加油次數(shù)最少，設(shè)計(jì)一個(gè)有效的算法，指出應(yīng)在那些加油站?？考佑?。并證明你的算法能產(chǎn)生一個(gè)最優(yōu)解。輸入：第一行：n，k,分別表示加滿油后可行駛公里數(shù)和加油站個(gè)數(shù)；第二行：k+1個(gè)整數(shù)，分別表示起點(diǎn)、k個(gè)加油站、終點(diǎn)之間的距離。輸出：加油次數(shù)。實(shí)驗(yàn)步驟：（算法描述、源程序、操作步驟和方法）1.要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的

4、時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。輸入：第一行：m，n，分別表示機(jī)器數(shù)和作業(yè)數(shù)；第二行：n個(gè)整數(shù)，分別表示n個(gè)作業(yè)所需的加工時(shí)間。輸出：t表示加工時(shí)間。提示：調(diào)度時(shí)間由m臺(tái)機(jī)器中，加工時(shí)間最長(zhǎng)的一個(gè)決定，故貪心選擇的一個(gè)原則應(yīng)該是：盡可能均衡m臺(tái)機(jī)器的負(fù)載（參考木桶原理）。實(shí)驗(yàn)程序如下：#include#includeusingnamespacestd;typedefstructJob/

5、/作業(yè){intID;inttime;}Job;typedefstructJobNode//作業(yè)鏈表的節(jié)點(diǎn){intID;inttime;JobNode*next;}JobNode,*pJobNode;typedefstructHeader//鏈表的表頭{ints;//處理機(jī)上的時(shí)間；JobNode*next;}Header,pHeader;intmain(){voidQuickSort(Job*job,intleft,intright);//將job時(shí)間排序voidoutSort(Job*job,intn);//輸出排

6、序voiddisplay(Header*M,intm);//輸出每個(gè)每臺(tái)機(jī)器處理的工作序號(hào)數(shù)intSelectMin(Header*M,intm);//分配作業(yè)時(shí)選取機(jī)器函數(shù)；voidsolve(Header*head,Job*job,intn,intm);//作業(yè)分配函數(shù)；intm,n;cout<<"請(qǐng)輸入機(jī)器臺(tái)數(shù)m:";cin>>m;Header*head=newHeader[m];//動(dòng)態(tài)構(gòu)建數(shù)組結(jié)構(gòu)體，用于記錄機(jī)器的作業(yè)時(shí)間；cout<<"請(qǐng)輸入作業(yè)個(gè)數(shù)n:";cin>>n;Job*job=newJob[n]

7、;//動(dòng)態(tài)構(gòu)建作業(yè)的數(shù)組結(jié)構(gòu)體；cout<<"請(qǐng)按序號(hào)輸入每個(gè)作業(yè)調(diào)度所需時(shí)間time：";for(inti=0;i>job[i].time;job[i].ID=i;}QuickSort(job,0,n-1);//作業(yè)排序outSort(job,n);//輸出排序solve(head,job,n,m);//作業(yè)分配display(head,m);//輸出分配cout<

8、{intk=0;for(inti=1;i