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

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

2、安排一場(chǎng)比賽，請(qǐng)你幫助學(xué)生會(huì)安排首輪循環(huán)賽的比賽日程表。2. 【找零錢問題】一個(gè)小孩買了價(jià)值為33美分的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目有限的面值為25美分、10美分、5美分、及1美分的硬幣。給出一種找零錢的貪心算法。四、實(shí)驗(yàn)步驟理解算法思想和問題要求；編程實(shí)現(xiàn)題目要求；上機(jī)輸入和調(diào)試自己所編的程序；驗(yàn)證分析實(shí)驗(yàn)結(jié)果；整理出實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)程序（1）循環(huán)賽日程安排實(shí)驗(yà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；初始化兩個(gè)人的賽程安排a01=2;a10=2;a11=1；scap(0,0,16);for(i=0;ivl6;i+) 輸出結(jié)果for(j=0;j<16;j+) coutvvaijvv""coutvvendl;/每 行結(jié)尾處換行return 0;void scap(int x,int y,int n)if(n=2)/如果只有兩個(gè)人直接返回結(jié)果 return; else/否則

4、二分n=n/2;scap(0,0,n);/遞歸調(diào)用自己scjs(0,n,n);/由已安排的部分算出并行的沒安排的 copysc (0,0,n,n,n);/左上部分復(fù)制到右下部分 copysc(0,n,n,0,n);右上部分復(fù)制到左下部分void copysc(int x1,int y1,int x2,int y2,int n)實(shí)現(xiàn)復(fù)制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/計(jì)算并行的賽事用于復(fù)制int i,j;for(i=0;i<n;i+)fo

5、r(j=0;j<n;j+) aij+n=aij+n;/ 數(shù)字規(guī)律 (2)找零錢問題實(shí)驗(yàn)代碼#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;每次去計(jì)算當(dāng)前最大可用的最大的錢要用多少 c=c%moneyi;還應(yīng)找的錢for(int i=0;i<4;i+)/ 輸出結(jié)果if(numi!=0)coutv

6、vmoneyivv"美分應(yīng)找"vvnumivv"個(gè)"vvendl;return 0;六、實(shí)驗(yàn)結(jié)果1循環(huán)賽日程安排問題實(shí)驗(yàn)結(jié)果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找零錢問題實(shí)驗(yàn)結(jié)果七、 實(shí)驗(yàn)分析分治法 就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的 子問題，再把子問題分成更小的子問題，直到最后問題可以簡單的直 接求解，原問題的解即子問題的解的合并。實(shí)驗(yàn)中的16名選手賽程安排，可以先二分。用scap函數(shù)進(jìn)行分治，當(dāng)人數(shù)比

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