1、算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告題目：循環(huán)賽日程表院（系）：信息科學(xué)與工程學(xué)院專業(yè)班級(jí)：軟工學(xué)生姓名：學(xué)號(hào):指導(dǎo)教師：2018年1月日至2018年1月丄匕日算法設(shè)計(jì)與分析課程設(shè)計(jì)任務(wù)書一、設(shè)計(jì)題目循環(huán)賽日程表問題描述：設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽。現(xiàn)要設(shè)計(jì)一個(gè)滿足一下要求的比賽日程表。每個(gè)選手必須與其他n-1個(gè)選手各賽一次。每個(gè)選手一天只能參賽一次。循環(huán)賽在n-1天內(nèi)結(jié)束。請(qǐng)按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個(gè)表格。在表中的第i行，第j列處填入第i個(gè)選手在第j天所遇到的選手，其中l(wèi)WiWn,lWjWn-1。2345678234567814365874127856321876567

2、81234587214385634127654321例如：當(dāng)n-4時(shí)，其比賽日程表如下:123(天)1124TT33ZT24tIIid1當(dāng)n=8時(shí)，其比賽日程表如下：1234567（天）1二、設(shè)計(jì)主要內(nèi)容具體要求如下：使用分治策略遞歸算法實(shí)現(xiàn)。使用分治策略非遞歸算法實(shí)現(xiàn)。使用遞推算法實(shí)現(xiàn)。對(duì)各種算法的時(shí)間復(fù)雜度進(jìn)行分析和比較。設(shè)計(jì)出相應(yīng)的菜單，通過菜單的選擇實(shí)現(xiàn)各個(gè)功能三、原始資料無四、要求的設(shè)計(jì)成果實(shí)現(xiàn)該系統(tǒng)功能的程序代碼撰寫符合規(guī)范要求的課程設(shè)計(jì)報(bào)告五、進(jìn)程安排序號(hào)課程設(shè)計(jì)內(nèi)容學(xué)時(shí)分配備注1選題與搜集資料1天2分析與設(shè)計(jì)1天3模塊實(shí)現(xiàn)4天4系統(tǒng)調(diào)試與測(cè)試2天5撰寫課程設(shè)計(jì)報(bào)告2天合計(jì)10天

3、六、主要參考資料呂國(guó)英.算法設(shè)計(jì)與分析.第2版.北京：清華大學(xué)出版社，2011.王曉東.算法設(shè)計(jì)與分析.北京，清華大學(xué)出版社，2009.徐士良.計(jì)算機(jī)常用算法.第2版.北京，清華大學(xué)出版社出版，2010.指導(dǎo)教師(簽名)20年月日目錄TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 常用算法1 HYPERLINK l bookmark6 o Current Document 1.1分治算法1基本概念:1 HYPERLINK l bookmark8 o Current Document 1.2遞推算法2 HYPERLINK l book

4、mark10 o Current Document 問題分析及算法設(shè)計(jì)5 HYPERLINK l bookmark12 o Current Document 2.1分治策略遞歸算法的設(shè)計(jì)5 HYPERLINK l bookmark18 o Current Document 分治策略非遞歸算法的設(shè)計(jì)7遞推策略算法的設(shè)計(jì)8 HYPERLINK l bookmark14 o Current Document 算法實(shí)現(xiàn)9 HYPERLINK l bookmark16 o Current Document 3.1分治策略遞歸算法的實(shí)現(xiàn)93.2分治策略非遞歸算法的實(shí)現(xiàn)10 HYPERLINK l book

5、mark20 o Current Document 遞推策略算法的實(shí)現(xiàn)12 HYPERLINK l bookmark22 o Current Document 測(cè)試和分析154.1分治策略遞歸算法測(cè)試154.2分治策略遞歸算法時(shí)間復(fù)雜度的分析16分治策略非遞歸算法測(cè)試164.4分治策略非遞歸算法時(shí)間復(fù)雜度的分析17時(shí)間復(fù)雜度為：0（5,n-l）17遞推策略算法測(cè)試17 HYPERLINK l bookmark24 o Current Document 遞推策略算法時(shí)間復(fù)雜度的分析18時(shí)間復(fù)雜度為：0（5,n-1）18 HYPERLINK l bookmark26 o Current Docum

6、ent 三種算法的比較18 HYPERLINK l bookmark28 o Current Document 總結(jié)19 HYPERLINK l bookmark30 o Current Document 參考文獻(xiàn)20 常用算法分治算法基本概念:在計(jì)算機(jī)科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之，”就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法（快速排序，歸并排序），傅立葉變換（快速傅立葉變換）任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都

7、與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算。1=2時(shí),只要作一次比較即可排好序n=3時(shí)只要作3次比較即可，。而當(dāng)n較大時(shí)，問題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的?；舅枷爰安呗?分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。分治策略是：對(duì)于一個(gè)規(guī)模為1的問題，若該問題可以容易地解決（比如說規(guī)模1較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合

8、并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。如果原問題可分割成k個(gè)子問題，l327643218765最后是第三部分的填充12345678214365873427/5643265567J2346572、437856341287654321這樣循環(huán)，直到填充完畢遞歸算法解：NimZ2NiiNiLIIFlowCnartaklTsrlikhm2).aij)i-HnZ2j-niZ2;i-k+in.?ai|j-aHn/2|j-in/2;2.2分治策略非遞歸算法的設(shè)計(jì)分治策略同上。非遞歸算法解：ftQNni十十Nn汁十Flowchartitinn-l;iiics-lMultiplex2.3遞推策略算法的設(shè)

9、計(jì)遞推策略： 算法實(shí)現(xiàn)分治策略遞歸算法的實(shí)現(xiàn)#include#include#includeconstintMAX=1024;/intaMAXMAX;/二位數(shù)組intNumber=2,g_K=1;clock_tstart,finish;/開始和結(jié)束時(shí)間doubleduration;/程序運(yùn)行時(shí)間voidTestl(intk,intm);/分治策略遞歸實(shí)現(xiàn)intmain(void)printf(請(qǐng)輸入指數(shù)kn);while(scanf(%d,&g_K)=0)fflush(stdin);for(inty=1;yg_K;y+)Number*=2;printf(參賽人員)；for(intz=1;zNu

10、mber;z+)printf(day%d,z);system(cls);start=clock();for(inti=0;i10000;i+)Test1(1,Number);finish=clock();duration=finish-start;/Menu();for(i=1;i=Number;i+)/for(intj=l;j二Number;j+)/第一列為參賽人員printf(%d,aij);printf(n);printf(程序循環(huán)10000次所用的時(shí)間：lfmsn,duration);return0;voidTestl(intk,intm)/采用分治策略遞歸實(shí)現(xiàn)inti,j;if(m=

11、2)/只有兩個(gè)人的時(shí)候ak1=k;ak+11=k+1;elseTest1(k,m/2);Test1(k+m/2,m/2);for(i=k;ik+m/2;i+)/一次填充半個(gè)子表上半部分的表格for(j=m/2+1;j=m;j+)/左右對(duì)稱填充aij=ai+m/2j-m/2;/填充表格for(i=k+m/2;ik+m;i+)for(j=m/2+1;j=m;j+)aij=ai-m/2j-m/2;分治策略非遞歸算法的實(shí)現(xiàn)#include#include#includeconstintMAX=1024;/intaMAXMAX;/二位數(shù)組intNumber=2,g_K=1;clock_tstart,fi

12、nish;/開始和結(jié)束時(shí)間doubleduration;/呈序運(yùn)行時(shí)間voidTest2(intk);/分治策略非遞歸實(shí)現(xiàn)intmain(void)printf(請(qǐng)輸入指數(shù)kn);while(scanf(%d,&g_K)=0)fflush(stdin);printf(請(qǐng)輸入“整數(shù)”kn);for(inty=1;yg_K;y+)Number*=2;printf(參賽人員)；for(intz=1;zNumber;z+)printf(day%d,z);system(cls);start=clock();for(inti=0;i10000;i+)Test2(g_K);finish=clock();du

13、ration=finish-start;for(i=1;i=Number;i+)for(intj=l;j二Number;j+)/第一列為參賽人員printf(%d,aij);printf(n);printf(程序循環(huán)10000次所用的時(shí)間：lfmsn,duration);return0;voidTest2(intk)/分治策略非遞歸方式實(shí)現(xiàn)inti,j;intn;n二Number;/拷貝參賽選手人數(shù)for(i=1;i=n;i+)a1i=i;intm=1;/填充初始位置for(ints=1;s=k;s+)n/=2;for(intt=1;t=n;t+)for(i=m+1;i=2*m;i+)for(

14、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;遞推策略算法的實(shí)現(xiàn)#include#include#includeconstintMAX=1024;/intaMAXMAX;/二位數(shù)組intNumber=2,g_K=1;clock_tstart,finish;/開始和結(jié)束時(shí)間doubleduration;/程序運(yùn)行時(shí)間 voidTest3(intk);/寸推策略實(shí)現(xiàn)intmain(void)printf(請(qǐng)輸入指數(shù)kn);while(scanf(%d,&g_K)=0)fflus

15、h(stdin);printf(請(qǐng)輸入“整數(shù)”kn);for(inty=1;yg_K;y+)Number*=2;printf(參賽人員)；for(intz=1;zNumber;z+)printf(day%d,z);system(cls);start=clock();for(inti=0;i10000;i+)Test3(Number);finish=clock();duration=finish-start;for(i=1;i=Number;i+)for(intj=l;j二Number;j+)/第一列為參賽人員printf(%d,aij);printf(n);printf(程序循環(huán)10000次所

16、用的時(shí)間：lfmsn,duration);return0;voidTest3(intnum)/遞推算法實(shí)現(xiàn)a11=1;intn,n0,i,j,k,k0;n0=1;n=2;k二g_K;/人數(shù)for(k0=1;k0=k;k0+)for(i=n0+1;i=n;i+)for(j=1;j=n;j+)aij=ai-n0j+n0;for(j=n0+1;j=n;j+)for(i=1;i=n0;i+)aij=aij-n0+n0;for(j=n0+1;j=n;j+)for(i=n0+1;i=n;i+)aij=aij-n0-n0;n0=n;n=n*2;測(cè)試和分析4.1分治策略遞歸算法測(cè)試給出輸入情況：請(qǐng)輸入指數(shù)kI

17、循環(huán)賽日程表輸入2:分治策略非遞歸算法輸入3:遞推策略算法得到輸出結(jié)果：參賽人員dayldai/2dai/3day4dai/5day?1234567821436587341278564321876556781234658721437856341287654321程序循壞10000次所用的時(shí)間:6.000000msPressanvkevtocontinue4.2分治策略遞歸算法時(shí)間復(fù)雜度的分析遞歸算法的優(yōu)點(diǎn)是結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，贏此為設(shè)計(jì)算法、調(diào)試程序帶來很大的方便。遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)計(jì)算時(shí)間的還是占用存儲(chǔ)空間的都比非遞歸算法要多。時(shí)間復(fù)雜

18、度分析：迭代處理的循環(huán)體內(nèi)部3個(gè)循環(huán)語句，每個(gè)循環(huán)語句都是一個(gè)嵌套的for循環(huán)，且它們的執(zhí)行次數(shù)相同，基本語句是最內(nèi)層循環(huán)體的賦值語句，即填寫比賽日程表的元素?；緢?zhí)行語句的執(zhí)行次數(shù)是：T(n)=21*21=41所以時(shí)間復(fù)雜度為O(4k)分治策略非遞歸算法測(cè)試給出輸入情況:得到輸出結(jié)果:參賽人員day?da3day4da5daGday?1234567821436587341278564321876556781234658721437856341287654321程序循壞10000所用的時(shí)間:4.000000msPressanykeytocontinue4.4分治策略非遞歸算法時(shí)間復(fù)雜度的分析時(shí)

19、間復(fù)雜度為：O(5,n-1)遞推策略算法測(cè)試給出輸入情況:遞推策略算法時(shí)間復(fù)雜度的分析時(shí)間復(fù)雜度為：0(13)三種算法的比較分治遞歸：適用于分解后的小規(guī)模問題很好解決的問題分治非遞歸：適用于分治遞歸算法設(shè)計(jì)過于復(fù)雜的問題遞推：適用于可根據(jù)已有結(jié)果推出結(jié)果的問題通過對(duì)比可知分治非遞歸效率最高。分治遞歸更簡(jiǎn)便，效率差些，遞推的時(shí)間復(fù)雜度最大，效率最低。5總結(jié)在這次課程設(shè)計(jì)當(dāng)中，我了解到了我的不足，如算法的不完善、不細(xì)心和耐心不是很好等等。不細(xì)心的我在調(diào)試程序時(shí)，老是因?yàn)槟硞€(gè)書寫錯(cuò)誤導(dǎo)致錯(cuò)誤；對(duì)這些錯(cuò)誤，我不得不花大量的時(shí)間去更正，并且還要重復(fù)檢查是否出現(xiàn)雷同的錯(cuò)誤而導(dǎo)致程序不能運(yùn)行。但是通過這次課

20、程設(shè)計(jì)，我的這些缺點(diǎn)有些改善。我在寫新的程序時(shí)，首先要考慮的深入一點(diǎn)、仔細(xì)一點(diǎn)，這樣要修改程序的時(shí)間就會(huì)少很多。并且也不會(huì)因?yàn)樽约翰患?xì)心而導(dǎo)致的浪費(fèi)時(shí)間的情況出現(xiàn)。在進(jìn)行程序設(shè)計(jì)時(shí)，要注意想好思路。即要有恰當(dāng)模塊名、變量名、常量名、子程序名等。將每個(gè)功能的模塊，即函數(shù)名要清晰的表述出來，使用戶能夠一目了然此程序的功能。當(dāng)然適當(dāng)?shù)慕o寫注釋，也是方便用戶的理解。還有在編寫程序時(shí)要注意對(duì)程序的適當(dāng)分配，便于用戶看懂程序，也便于自己檢查城市。但是完成任何一個(gè)較大的程序，都需要掌握一定的編程基礎(chǔ)，需要不斷的探索和求知過程，這樣對(duì)自己編程能力的提高有較大的幫助。當(dāng)然，任何程序必須經(jīng)過計(jì)算機(jī)的調(diào)試，看是否調(diào)試成功，發(fā)現(xiàn)錯(cuò)誤，一個(gè)個(gè)，一步步去解決，這樣就能從錯(cuò)誤中進(jìn)步。通過課程設(shè)計(jì)加強(qiáng)了我的動(dòng)手能力，以及提升了局部和統(tǒng)一考慮問題的思維方式。回顧起此次課程設(shè)計(jì)，至今我仍感慨頗多，的確，從從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，在整整半個(gè)月的日子里，