算法設計與分析實驗三

1、南華大學計算機科學與技術學院實驗報告（200200 學年度 第 學期）課程名稱算法分析與設計實驗名稱貪心法與分治法姓名劉文東學號20104030327專業(yè)計算機技術班級10級03班地點8-209教師余穎老師實驗三分治與貪心一、實驗目的與要求熟悉C/C+語言的集成開發(fā)環(huán)境；通過本實驗加深對分治法、貪心算法的理解。二、實驗內(nèi)容：掌握分治法、貪心算法的概念和基本思想，并結合具體的問題學習如何用相應策略進行求解的方法。三、實驗題1. 【循環(huán)賽日程安排問題】計算機學院準備舉辦一次男生羽毛球單打比賽，現(xiàn)在總共有16名選手報名，首輪比賽準備采取循環(huán)賽的形式進行角逐，要求必須在15天內(nèi)比完，且每個選手每天只能

2、安排一場比賽，請你幫助學生會安排首輪循環(huán)賽的比賽日程表。2. 【找零錢問題】一個小孩買了價值為33美分的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目有限的面值為25美分、10美分、5美分、及1美分的硬幣。給出一種找零錢的貪心算法。四、實驗步驟理解算法思想和問題要求；編程實現(xiàn)題目要求；上機輸入和調(diào)試自己所編的程序；驗證分析實驗結果；整理出實驗報告。五、實驗程序（1）循環(huán)賽日程安排實驗代碼#include viostream> using namespace std; int a1616; void copysc (int x1,int y1,int x2

3、,int y2,int n); void scap(int x,int y,int n); void scjs(int x,int y,int n); int main()int i,j;a00=1；初始化兩個人的賽程安排a01=2;a10=2;a11=1；scap(0,0,16);for(i=0;ivl6;i+) 輸出結果for(j=0;j<16;j+) coutvvaijvv""coutvvendl;/每 行結尾處換行return 0;void scap(int x,int y,int n)if(n=2)/如果只有兩個人直接返回結果 return; else/否則

4、二分n=n/2;scap(0,0,n);/遞歸調(diào)用自己scjs(0,n,n);/由已安排的部分算出并行的沒安排的 copysc (0,0,n,n,n);/左上部分復制到右下部分 copysc(0,n,n,0,n);右上部分復制到左下部分void copysc(int x1,int y1,int x2,int y2,int n)實現(xiàn)復制int i,j;for(i=0;i<n;i+) for(j=0;j<n;j+) ax2+iy2+j=ax1+iy1+j;void scjs (int x,int y,int/計算并行的賽事用于復制int i,j;for(i=0;i<n;i+)fo

5、r(j=0;j<n;j+) aij+n=aij+n;/ 數(shù)字規(guī)律 (2)找零錢問題實驗代碼#include<iostream>using namespace std;int main ()int a=100,b=33,c=a-b;int money4=25,10,5,1;/把可用的錢按從大到小存入數(shù)組int num4=0;用于記錄每種錢要用多少次for(int i=0;i<4;i+)numi=c/moneyi;每次去計算當前最大可用的最大的錢要用多少 c=c%moneyi;還應找的錢for(int i=0;i<4;i+)/ 輸出結果if(numi!=0)coutv

6、vmoneyivv"美分應找"vvnumivv"個"vvendl;return 0;六、實驗結果1循環(huán)賽日程安排問題實驗結果3 4 54 3 62 71 812911 121314151618 9 12 111413161511 12 9 101516131412 1191615141313 14 15 16910111214 13 16 1510912111513 141112:91016 15 14 13121110 915 16 1 23 456? 877 88 75 &3 44 31 21112?15 161314341278512111

7、0916613141516911125G7S1231413161510 91211SE872141516131411 12910?8563411615141312 1110 9765432慣按任意鍵繼續(xù)4 344 3 2 112 13 1411 14 13 16 15 27S?85610 11L10 9 122找零錢問題實驗結果七、 實驗分析分治法 就是把一個復雜的問題分成兩個或更多的相同或相似的 子問題，再把子問題分成更小的子問題，直到最后問題可以簡單的直 接求解，原問題的解即子問題的解的合并。實驗中的16名選手賽程安排，可以先二分。用scap函數(shù)進行分治，當人數(shù)比

8、較大時，n=n/2, 然后遞歸調(diào)用自己，實現(xiàn)人數(shù)減少的分治。當人數(shù)比較少時，n=2,可以直接初始化。合并子問題用到scjs函數(shù)與copysc函數(shù)，先用scjs 函數(shù)利用人數(shù)少時已經(jīng)安排的賽程計算并行的賽程for(i=0;ivn;i+)for(j=0；j<n;j+)aij+n=aij+n;即用左上部分計算出右上部分最后用copy函數(shù)把已經(jīng)安排的賽程合并到?jīng)]安排的部分copysc (0,0, n,n,n);/左上部分復制到右下部分copysc(0, n,n ,0, n);/右上部分復制到左下部分實現(xiàn)對整個賽事的安排。貪心法 在對問題求解時，總是做出當前看來最好的選擇，他所做 出的僅是某種意義上的局部最優(yōu)解。貪心法要有最優(yōu)量度標準，最優(yōu)解可以通過一系列局部最優(yōu)的選擇來達到，根據(jù)當前狀態(tài)做出在當前看來是最好的選擇，即局部最優(yōu)解，然后再去解做出這個選擇后產(chǎn)生 的相應的子問題。每做一次選擇就將所求問題簡化為一個規(guī)模更小的 子問題，最終可得到問題的一個整體最優(yōu)解。由此原理，要使找的硬 幣數(shù)目最小，就得盡量找最大的硬幣。所以把硬幣按從