循環(huán)賽日程表實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上天津工程師范學(xué)院算法與程序計(jì) -課程設(shè)計(jì)報(bào)告 班級：計(jì)科0813班學(xué)號：姓名：設(shè)計(jì)時(shí)間：2009.12.2112.25一課程設(shè)計(jì)名稱：循環(huán)賽日程表二.實(shí)驗(yàn)內(nèi)容問題描述:設(shè)有n位選手參加網(wǎng)球循環(huán)賽，n=2k，循環(huán)賽共進(jìn)行n-1天，每位選手要與其他n-1位選手比賽一場，且每位選手每天比賽一場，不能輪空，按一下要求為比賽安排日程，（1） 每位選手必須與其他n-1格選手格賽一場；（2） 每個(gè)選手每天只能賽一場；（3） 循環(huán)賽一共進(jìn)行n-1天；請按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個(gè)表。在表中的第i行和第j列處填入第i個(gè)選手在第j天所遇到的選手，其中1in,1jn-1

2、。三.實(shí)驗(yàn)?zāi)康?.運(yùn)用分治法，設(shè)計(jì)解決上述問題的算法，設(shè)計(jì)出比賽日程表，在表中的第i行和第j列處填入第i個(gè)選手在第j天所遇到的選手（其中1in,1jn-1）。2.掌握分治算法的應(yīng)用。四算法原理運(yùn)用分治法，將原問題劃分為較小問題，然后由較小問題的解得出原問題的解。1.分治法:對于一個(gè)規(guī)模為n的問題，若該問題可以容易的解決（比如說規(guī)模n較?。瑒t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題形式相同，遞歸的解決這些子問題，然后將個(gè)子問題的解合并，得到原問題的解。2.分治法的解題步驟（由三個(gè)步驟組成）l 劃分（divide）：將原問題分解為若干個(gè)規(guī)模較小、相互獨(dú)立、與原問

3、題形式相同的子問題。l 解決（conquer）：若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。l 合并（conbine）：將各子問題的解合并為原問題的解五問題分析假設(shè)n位選手順序編號為1，2，3n，比賽的日程表是一個(gè)n行n-1列的表格。i行j列的表格內(nèi)容是第i號選手在第j天的比賽對手。根據(jù)分而治之的原則，可從其中以半選手的比賽日程，導(dǎo)出全體n位選手的的日程，最終細(xì)分到只有兩位選手的比賽日程出發(fā)。六設(shè)計(jì)步驟1.先設(shè)計(jì)主函數(shù)（main函數(shù)），然后設(shè)計(jì)兩個(gè)函數(shù)，分別是安排賽事進(jìn)行填制表格的函數(shù)（void arrangement(int n,int N,int k,int a100100)函數(shù)）

4、和輸出到屏幕函數(shù)（void print(int n,int a100100)）。2.在主函數(shù)（main（）里調(diào)用void arrangement（）函數(shù)，對比賽日程進(jìn)行安排，根據(jù)分而治之原則，繪制比賽日程表格，然后調(diào)用void print（）函數(shù)，將安排好的比賽日程輸出到屏幕上。七關(guān)鍵數(shù)據(jù)結(jié)構(gòu)1.運(yùn)用一個(gè)二維數(shù)組aij，對安排好的賽事日程進(jìn)行排列和保存，并在屏幕上輸出。2.使用二維數(shù)組的原因：因?yàn)楦鶕?jù)題目要求，比賽日程表是一個(gè)n行n-1列的表格，用aij代表第i號選手在第j天遇到的對手，所以用一個(gè)二維數(shù)組表示。八程序結(jié)構(gòu) 程序主要由三個(gè)函數(shù)組成：（1）main（）函數(shù)（主函數(shù)），（2）void

5、 arrangement()函數(shù)（本程序的核心函數(shù)），（3）print函數(shù)（輸出函數(shù)）1.main（）函數(shù)傳值調(diào)用void arrangement（）函數(shù)int k;輸入k值main()計(jì)算參賽人數(shù)n值計(jì)算參賽人數(shù)n=2k調(diào)用print()函數(shù)，輸出到屏幕結(jié)束2.void arrangement()函數(shù)void arrangement(int n,int N,int k,int a100100)NNYNYNYYNYint i=1i<=Ni+a1i=ii+m=1s=1s<=k?N=N/2int t=1t<=N?int i=m+1i<=2*mj=m+1j<=m+1ai

6、j+(t-1)*m*2 = ai-mj+(t-1)*m*2-maij+(t-1)*m*2-m = ai-mj+(t-1)*m*2j+i+t+s+m=m*2結(jié)束3.print（）函數(shù)i+NNYYvoid print(int n,int a100100)int i=1i<=nint j=1j<=nj+cout<<setw(4)<<setfill(' ')<<aijcout<<endl“”結(jié)束九關(guān)鍵程序功能及其實(shí)現(xiàn)的說明1. .main（）函數(shù)（1）函數(shù)功能：在屏幕上輸入k值，計(jì)算參賽人數(shù)n，然后調(diào)用void arrange

7、ment()函數(shù)和print（）函數(shù)。（2）函數(shù)實(shí)現(xiàn)：先定義一個(gè)k，然后在鍵盤上輸入一個(gè)k值，并賦值給k（假設(shè)輸入3）；運(yùn)用for循環(huán)，計(jì)算參賽人數(shù)n的值for (int i=1;i<=k;i+) n *= 2;可得n=8，即有八個(gè)人參賽。然后調(diào)用void arrangement()函數(shù)和print（）函數(shù)，并傳值。2.void arrangement()函數(shù)(1)函數(shù)功能：對所有運(yùn)動員的賽程進(jìn)行安排，并將其存入數(shù)組內(nèi)。(2)函數(shù)實(shí)現(xiàn)：由main（）函數(shù)得到k值為3，n值為8用一個(gè)for循環(huán)輸出日程表的第一行for(int i=1;i<=N;i+) a1i = i；12345678

8、然后定義一個(gè)m值，m初始化為1，m用來控制每一次填充表格時(shí)i（i表示行）和j（j表示列）的起始填充位置。用一個(gè)for循環(huán)將問題分成幾部分，對于k=3，n=8，將問題分成3大部分，第一部分為，根據(jù)已經(jīng)填充的第一行，填寫第二行，第二部分為，根據(jù)已經(jīng)填充好的第一部分，填寫第三四行，第三部分為，根據(jù)已經(jīng)填充好的前四行，填寫最后四行。for (int s=1;s<=k;s+) N/=2;用一個(gè)for循環(huán)對中提到的每一部分進(jìn)行劃分for(int t=1;t<=N;t+)對于第一部分，將其劃分為四個(gè)小的單元，即對第二行進(jìn)行如下劃分 同理，對第二部分（即三四行），劃分為兩部分，第三部分同理最后，根

9、據(jù)以上for循環(huán)對整體的劃分和分治法的思想，進(jìn)行每一個(gè)單元格的填充。填充原則是：對角線填充for(int i=m+1;i<=2*m;i+)/i控制行for(int j=m+1;j<=2*m;j+) /j控制列 aij+(t-1)*m*2 = ai-mj+(t-1)*m*2-m;/*右下角的值等于左上角的值 */ aij+(t-1)*m*2-m = ai-mj+(t-1)*m*2;/*左下角的值等于右上角的值 */ 例：由初始化的第一行填充第二行1234567821436587由s控制的第一部分填完。然后是s+，進(jìn)行第二部分的填充123456782143658734127856432

10、18765最后是第三部分的填充1234567821436587341278564321876556781234658721437856341287654321這樣循環(huán)，直到填充完畢，a數(shù)組被賦予新值。3.print（）函數(shù)（1）函數(shù)功能：將安排好的賽事日程，即二維數(shù)組ann-1輸出到屏幕。（2）函數(shù)主要功能實(shí)現(xiàn)：函數(shù)主要運(yùn)用一個(gè)for循環(huán)，將二維數(shù)組ann-1輸出到屏幕。for( int i=1;i<=n;i+)/控制行cout<<setw(3)<<setfill(' ')<<ai1<<"|"for(in

11、t j=2;j<=n;j+) /控制列 cout<<setw(4)<<setfill(' ')<<aij; cout<<endl;十程序運(yùn)行結(jié)果十一.體會程序主要運(yùn)用了：數(shù)據(jù)輸入、函數(shù)調(diào)用、函數(shù)傳值、for循環(huán)以及二維數(shù)組等主要結(jié)構(gòu)和功能。根據(jù)分治算法，將本問題進(jìn)行了由小規(guī)模到大規(guī)模的求解設(shè)計(jì)，程序設(shè)計(jì)的關(guān)鍵點(diǎn)在于如何對問題進(jìn)行劃分和填充公式的歸納。在劃分時(shí)，主要運(yùn)用了兩個(gè)for循環(huán)；在填充時(shí)，運(yùn)用了兩個(gè)for循環(huán)。通過這次程序設(shè)計(jì)，加深了對分治算法的認(rèn)識。解決具體問題時(shí)，程序故重要，但一個(gè)好的算法更加重要。本程序的得意之處

12、在于，經(jīng)過仔細(xì)研究，找到了劃分的方法，并推導(dǎo)出了表格填充的兩個(gè)公式。不足之處也在此，即花費(fèi)了很長時(shí)間來推導(dǎo)這個(gè)，對算法掌握還不夠熟練。十二.工具軟件及運(yùn)行環(huán)境1.工具軟件：Microsoft Visual C+ 6.02.運(yùn)行環(huán)境：Win32 Console Application專心-專注-專業(yè)附：#include<iostream>#include<iomanip>using namespace std;void print(int n,int a100100);void arrangement(int n,int N,int k,int a100100);int

13、main() int k; int a100100; int n=1; cout<<"請輸入 k"<<endl; cin >> k; for (int i=1;i<=k;i+) n *= 2;/n=2k cout<<"參賽人數(shù)"<<n<<endl; int N=n; arrangement(n, N, k, a); print(n,a); void arrangement(int n,int N,int k,int a100100)for(int i=1;i<=N;i+)

14、 a1i = i;int m =1;for (int s=1;s<=k;s+) N/=2; for(int t=1;t<=N;t+) for(int i=m+1;i<=2*m;i+)for(int j=m+1;j<=2*m;j+) aij+(t-1)*m*2=ai-mj+(t-1)*m*2-m; aij+(t-1)*m*2-m=ai-mj+(t-1)*m*2; m *= 2; void print(int n,int a100100)cout<<"-"<<"循環(huán)賽日程表"<<"-"<<endl;cout<<endl;cout<<"日期"for(int p=1;p<n;p+)cout<<setw(4)<<setfill('-')<