使用分治策略遞歸和非遞歸和遞推算法解決循環(huán)賽日程表課程設(shè)計(jì)報(bào)告

1、<p><b>　　《算法設(shè)計(jì)與分析》</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　題 目： 循環(huán)賽日程表 </p><p>　　院 （系）： 信息科學(xué)與工程學(xué)院 </p><p>　　專業(yè)班級(jí)：

2、 軟工 </p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號(hào)： </p><p>　　指導(dǎo)教師： </p><p>　　2018 年 1 月 8 日至

3、2018 年 1 月 19 日</p><p>　　算法設(shè)計(jì)與分析 課程設(shè)計(jì)任務(wù)書</p><p><b>　　目 錄</b></p><p><b>　　1 常用算法1</b></p><p><b>　　1.1分治算法1</b></p>&

4、lt;p><b>　　基本概念:1</b></p><p><b>　　1.2遞推算法2</b></p><p>　　2 問題分析及算法設(shè)計(jì)5</p><p>　　2.1分治策略遞歸算法的設(shè)計(jì)5</p><p>　　2.2 分治策略非遞歸算法的設(shè)計(jì)7</p><p

5、>　　2.3 遞推策略算法的設(shè)計(jì)8</p><p><b>　　3 算法實(shí)現(xiàn)9</b></p><p>　　3.1分治策略遞歸算法的實(shí)現(xiàn)9</p><p>　　3.2 分治策略非遞歸算法的實(shí)現(xiàn)10</p><p>　　3.3 遞推策略算法的實(shí)現(xiàn)12</p><p>　　4 測(cè)試和分

6、析15</p><p>　　4.1分治策略遞歸算法測(cè)試15</p><p>　　4.2分治策略遞歸算法時(shí)間復(fù)雜度的分析16</p><p>　　4.3 分治策略非遞歸算法測(cè)試16</p><p>　　4.4分治策略非遞歸算法時(shí)間復(fù)雜度的分析17</p><p>　　時(shí)間復(fù)雜度為：O(5^(n-1))17&l

7、t;/p><p>　　4.5 遞推策略算法測(cè)試17</p><p>　　4.6 遞推策略算法時(shí)間復(fù)雜度的分析18</p><p>　　時(shí)間復(fù)雜度為：O(5^(n-1))18</p><p>　　4.7 三種算法的比較18</p><p><b>　　5 總結(jié)19</b></p>

8、<p><b>　　參考文獻(xiàn)20</b></p><p><b>　　1 常用算法</b></p><p><b>　　1.1分治算法</b></p><p><b>　　基本概念:</b></p><p>　　在計(jì)算機(jī)科學(xué)中，分治法是一種很

9、重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡(jiǎn)單的直接求解，原問題的解即子問題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)…… </p><p>　　任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)

10、算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算。n=2時(shí)，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可，…。而當(dāng)n較大時(shí)，問題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的。</p><p><b>　　基本思想及策略:</b></p><p>　　分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的

11、相同問題，以便各個(gè)擊破，分而治之。 </p><p>　　分治策略是：對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。 </p><p>　　如果原問題可分割成k個(gè)子問題，1<k≤n，且這些子

12、問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。</p><p><b>　　分治法

13、適用的情況:</b></p><p>　　分治法所能解決的問題一般具有以下幾個(gè)特征： </p><p>　　1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決 </p><p>　　2) 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 </p><p>　　3) 利用該問題分解出的子問題的解可以合并為該問

14、題的解； </p><p>　　4) 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。</p><p><b>　　1.2遞推算法</b></p><p>　　遞推算法是一種根據(jù)遞推關(guān)系進(jìn)行問題求解的方法。遞推關(guān)系可以抽象為一個(gè)簡(jiǎn)單的數(shù)學(xué)模型，即給定一個(gè)數(shù)的序列a0，a1...，an若存在整數(shù)n0，使當(dāng)n>n0

15、時(shí)可以用等號(hào)將an與其前面的某些項(xiàng)ai聯(lián)系起來,這樣的式子成為遞推公式。遞推算法是一種簡(jiǎn)單的算法，通過已知條件利用特點(diǎn)的遞推關(guān)系可以得出中間推論，直至得到問題的最終結(jié)果，遞推算法分為順推法和逆推法兩種，順推法則是在不知道初始條件的情況下，從問題的結(jié)果除非經(jīng)遞推關(guān)系逐步推算出問題的解，這個(gè)問題的解也是問題的初始條件。       </p><p>

16、;　　遞歸法是從已知條件出發(fā)，一步步地遞推出未知項(xiàng)，直到問題的解。遞歸也是遞推的一種，只不過它是對(duì)待解問題的遞推，知道把一個(gè)負(fù)責(zé)的問題遞推為簡(jiǎn)單的易解問題，然后再一步步返回，從而得到原問題的解。嚴(yán)格來講，遞歸不僅僅是一種問題求解方法，更是一種編程技術(shù)，許多算法可以通過遞歸技術(shù)來編程實(shí)現(xiàn)。在計(jì)算機(jī)科學(xué)中，人們把程序直接或間接調(diào)用自身的過程稱為遞歸。過程或函數(shù)直接調(diào)用自身的遞歸成為直接遞歸，間接調(diào)用自身的遞歸稱為間接遞歸。在問題求解中，采用

17、遞歸算法有兩個(gè)重要的好處：一是容易證明算法有兩個(gè)重要的好處，其次是代碼實(shí)現(xiàn)簡(jiǎn)潔，代碼編程量少。不足是程序運(yùn)行效率較低。        </p><p>　　遞推算法的基本思想是把一個(gè)復(fù)雜龐大的計(jì)算過程轉(zhuǎn)化為簡(jiǎn)單過程的多次重復(fù)。該算法利用了計(jì)算機(jī)速度快和自動(dòng)化的特點(diǎn)。 </p><p>　　而遞歸法的思

18、想是從已知條件出發(fā)，一步步地遞推出未知項(xiàng)，直到問題的解。</p><p>　　五種典型的遞推關(guān)系:</p><p>　　1.Fibonacci數(shù)列</p><p>　　在所有的遞推關(guān)系中，F(xiàn)ibonacci數(shù)列應(yīng)該是最為大家所熟悉的。在最基礎(chǔ)的程序設(shè)計(jì)語言 Logo語言中，就有很多這類的題目。而在較為復(fù)雜的Basic、Pascal、C語言中，F(xiàn)ibonacci數(shù)

19、列類的題目因?yàn)榻夥ㄏ鄬?duì)容易一些，逐漸退出了競(jìng)賽的舞臺(tái)。可是這不等于說Fibonacci數(shù)列沒有研究?jī)r(jià)值，恰恰相反，一些此類的題目還是能給我們一定的啟發(fā)的。 </p><p>　　Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”(又稱“Fibonacci問題”)。 </p><p>　　問題的提出：有雌雄一對(duì)兔子，假定過兩個(gè)月便可繁殖

20、雌雄各一的一對(duì)小兔子。問過n個(gè)月后共有多少對(duì)兔子？ 　　</p><p>　　解：設(shè)滿x個(gè)月共有兔子Fx對(duì)，其中當(dāng)月新生的兔子數(shù)目為Nx對(duì)。第x-1個(gè)月留下的兔子數(shù)目設(shè)為Fx-1對(duì)。則： </p><p>　　Fx=Nx+ Fx-1 　　 </p><p>　　Nx=Fx-2 (即第x-2個(gè)月的所有兔子到第x個(gè)月都有繁殖能力） 　　 </p>

21、<p>　　∴ Fx=Fx-1+Fx-2 邊界條件：F0=0，F(xiàn)1=1 </p><p>　　由上面的遞推關(guān)系可依次得到： 　　　</p><p>　　F2=F1+F0=1，F(xiàn)3=F2+F1=2，F(xiàn)4=F3+F2=3，F(xiàn)5=F4+F3=5，……。 </p><p>　　Fabonacci數(shù)列常出現(xiàn)在比較簡(jiǎn)單的組合計(jì)數(shù)問題中，例如以前的競(jìng)賽中出現(xiàn)的“骨

22、牌覆蓋”問題。在優(yōu)選法中，F(xiàn)ibonacci數(shù)列的用處也得到了較好的體現(xiàn)。</p><p>　　2.Hanoi塔問題</p><p>　　問題的提出：Hanoi塔由n個(gè)大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個(gè)圓盤由大到小依次套在a柱上，如圖3-11所示。 </p><p>　　要求把a(bǔ)柱上n個(gè)圓盤按下述規(guī)則移到c柱上：</p><

23、p>　　(1)一次只能移一個(gè)圓盤； 　　</p><p>　　(2)圓盤只能在三個(gè)柱上存放； 　　</p><p>　　(3)在移動(dòng)過程中，不允許大盤壓小盤。 　　</p><p>　　問將這n個(gè)盤子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤次？ 　　 </p><p>　　解：設(shè)hn為n個(gè)盤子從a柱移到c柱所需移動(dòng)的盤次。顯然

24、，當(dāng)n=1時(shí)，只需把a(bǔ) 柱上的盤子直接移動(dòng)到c柱就可以了，故h1=1。當(dāng)n=2時(shí)，先將a柱上面的小盤子移動(dòng)到b柱上去；然后將大盤子從a柱移到c 柱；最后，將b柱上的小盤子移到c柱上，共記3個(gè)盤次，故h2=3。以此類推，當(dāng)a柱上有n(n2)個(gè)盤子時(shí)，總是先借助c柱把上面的n-1個(gè)盤子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤子移動(dòng)到c柱上；總共移動(dòng)hn-1+1+hn-1個(gè)盤次。 　　 </p&

25、gt;<p>　　∴hn=2hn-1+1 邊界條件：h1=1</p><p><b>　　3.平面分割問題</b></p><p>　　問題的提出：設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。 </p><p>　　解：設(shè)an為n條封閉曲線把

26、平面分割成的區(qū)域個(gè)數(shù)。 由圖3-13可以看出：a2-a1=2；a3-a2=4；a4-a3=6。</p><p>　　從這些式子中可以看出an-an-1=2(n-1)。當(dāng)然，上面的式子只是我們通過觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來試著證明一下。當(dāng)平面上已有n-1條曲線將平面分割成an-1個(gè)區(qū)域后，第n-1條曲線每與曲線相交一次，就會(huì)增加一個(gè)區(qū)域，因?yàn)槠矫嫔弦延辛薾-1條封閉曲線，且第n

27、條曲線與已有的每一條閉曲線恰好相交于兩點(diǎn)，且不會(huì)與任兩條曲線交于同一點(diǎn)，故平面上一共增加2(n-1)個(gè)區(qū)域，加上已有的an-1個(gè)區(qū)域，一共有an-1+2(n-1)個(gè)區(qū)域。所以本題的遞推關(guān)系是an=an-1+2(n-1)，邊界條件是a1=1。</p><p>　　4.Catalan數(shù)</p><p>　　Catalan數(shù)首先是由Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問題時(shí)

28、得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問題中。 </p><p>　　問題的提出：在一個(gè)凸n邊形中，通過不相交于n邊形內(nèi)部的對(duì)角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用hn表示，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方案(圖3-14)，故h5=5。求對(duì)于一個(gè)任意的凸n邊形相應(yīng)的hn。</p><p>　　5.第二類Stirling數(shù)</p><p>　　n

29、個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)。 </p><p>　　根據(jù)定義來推導(dǎo)帶兩個(gè)參數(shù)的遞推關(guān)系——第二類Stirling數(shù)。 </p><p>　　解：設(shè)有n個(gè)不同的球，分別用b1,b2,……bn表示。從中取出一個(gè)球bn，bn的放法有以下兩種： 　　 </p><p>　?、賐n獨(dú)自占

30、一個(gè)盒子；那么剩下的球只能放在m-1個(gè)盒子中，方案數(shù)為S2(n-1,m-1)； 　　 </p><p>　?、赽n與別的球共占一個(gè)盒子；那么可以事先將b1,b2,……bn-1這n-1個(gè)球放入m個(gè)盒子中，然后再將球bn可以放入其中一個(gè)盒子中，方案數(shù)為mS2(n-1,m)。 </p><p>　　綜合以上兩種情況，可以得出第二類Stirling數(shù)定理： 　　　 </p>&

31、lt;p>　　【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n>1,m1) </p><p>　　邊界條件可以由定義2推導(dǎo)出： 　　　 </p><p>　　S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。</p><p>　　2 問題分析及算法設(shè)計(jì)</p>&l

32、t;p>　　2.1分治策略遞歸算法的設(shè)計(jì)</p><p>　　從本問題的具體情況出發(fā)，根據(jù)分治算法思想，設(shè)計(jì)出本問題的分治遞歸算法</p><p>　　按分治策略，可將所有選手分成兩組。n個(gè)選手的比賽日程表，可以通過n/2個(gè)選手的比賽日程表，可以通過n/4個(gè)選手設(shè)計(jì)日程表來決定；……；直到為2個(gè)選手的比賽日程表。這樣比賽日程表的設(shè)計(jì)就變得很簡(jiǎn)單，這時(shí)只要讓兩個(gè)選手互相比賽即可，這樣可

33、以形成n/2組2個(gè)選手的比賽日程表（如表1、表2）。然后再反過來在兩個(gè)選手的日程表上為4個(gè)選手設(shè)計(jì)比賽日程表（如表3）。然后再類推到8個(gè)、16個(gè)、……、2k個(gè)選手。</p><p>　　對(duì)所有運(yùn)動(dòng)員的賽程進(jìn)行安排，并將其存入數(shù)組內(nèi):</p><p>　　對(duì)于第一部分，將其劃分為四個(gè)小的單元，即對(duì)第二行進(jìn)行如下劃分:</p><p>　　同理，對(duì)第二部分（即三四行），

34、劃分為兩部分，第三部分同理</p><p>　　由初始化的第一行填充第二行:( 填充原則是對(duì)角線填充)</p><p>　　由 s控制的第一部分填完。然后是s++，進(jìn)行第二部分的填充</p><p>　　最后是第三部分的填充</p><p>　　這樣循環(huán)，直到填充完畢</p><p><b>　　遞歸算法解：

35、</b></p><p>　　2.2 分治策略非遞歸算法的設(shè)計(jì)</p><p><b>　　分治策略同上。</b></p><p><b>　　非遞歸算法解：</b></p><p>　　2.3 遞推策略算法的設(shè)計(jì)</p><p><b>　　遞推策略：

36、</b></p><p><b>　　3 算法實(shí)現(xiàn)</b></p><p>　　3.1分治策略遞歸算法的實(shí)現(xiàn)</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#includ

37、e <time.h></p><p>　　const int MAX = 1024;//</p><p>　　int a[MAX][MAX];//二位數(shù)組</p><p>　　int Number=2,g_K=1;</p><p>　　clock_t start, finish;//開始和結(jié)束時(shí)間</p><p

38、>　　double duration;//程序運(yùn)行時(shí)間</p><p>　　void Test1(int k,int m);//分治策略 遞歸實(shí)現(xiàn)</p><p>　　int main(void)</p><p><b>　　{ </b></p><p>　　printf("請(qǐng)輸入指數(shù)k\n&quo

39、t;);</p><p>　　while(scanf("%d",&g_K)==0){</p><p>　　fflush(stdin);</p><p><b>　　}</b></p><p>　　for (int y=1;y<g_K;y++)</p><p>　　

40、Number*=2;</p><p>　　printf("參賽人員");</p><p>　　for(int z=1;z<Number;z++){</p><p>　　printf(" day%d",z);</p><p><b>　　}</b></p><

41、;p>　　system("cls");</p><p>　　start=clock();</p><p>　　for(int i=0;i<10000;i++)</p><p>　　Test1(1,Number);</p><p>　　finish=clock();</p><p>　　d

42、uration=finish-start;</p><p><b>　　//Menu();</b></p><p>　　for( i=1;i<=Number;i++)//</p><p><b>　　{</b></p><p>　　for(int j=1;j<=Number;j++)//

43、第一列為參賽人員</p><p>　　printf(" %d",a[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("程序循環(huán)10000次所用的時(shí)間：%lfms\n",du

44、ration);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void Test1(int k,int m)//采用分治策略遞歸實(shí)現(xiàn)</p><p><b>　　{</b></p><p

45、><b>　　int i,j;</b></p><p>　　if(m==2)//只有兩個(gè)人的時(shí)候</p><p><b>　　{</b></p><p>　　a[k][1]=k;</p><p>　　a[k+1][1]=k+1;</p><p><b>　　}

46、</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　Test1(k,m/2);</p><p>　　Test1(k+m/2,m/2);</p><p><b>　　}</b>&l

47、t;/p><p>　　for(i=k;i<k+m/2;i++)//一次填充半個(gè)子表 上半部分的表格</p><p>　　for(j=m/2+1;j<=m;j++)//左右對(duì)稱填充</p><p>　　a[i][j]=a[i+m/2][j-m/2];//填充表格</p><p>　　for(i=k+m/2;i<k+m;i++)&l

48、t;/p><p>　　for(j=m/2+1;j<=m;j++)</p><p>　　a[i][j]=a[i-m/2][j-m/2];</p><p><b>　　}</b></p><p>　　3.2 分治策略非遞歸算法的實(shí)現(xiàn)</p><p>　　#include <stdio.h>

49、;</p><p>　　#include <stdlib.h></p><p>　　#include <time.h></p><p>　　const int MAX = 1024;//</p><p>　　int a[MAX][MAX];//二位數(shù)組</p><p>　　int Number=

50、2,g_K=1;</p><p>　　clock_t start, finish;//開始和結(jié)束時(shí)間</p><p>　　double duration;//程序運(yùn)行時(shí)間</p><p>　　void Test2(int k);//分治策略 非遞歸實(shí)現(xiàn)</p><p>　　int main(void)</p><p>

51、;<b>　　{ </b></p><p>　　printf("請(qǐng)輸入指數(shù)k\n");</p><p>　　while(scanf("%d",&g_K)==0){</p><p>　　fflush(stdin);</p><p>　　printf("請(qǐng)輸入“整

52、數(shù)”k\n");</p><p><b>　　}</b></p><p>　　for (int y=1;y<g_K;y++)</p><p>　　Number*=2;</p><p>　　printf("參賽人員");</p><p>　　for(int z=1

53、;z<Number;z++){</p><p>　　printf(" day%d",z);</p><p><b>　　}</b></p><p>　　system("cls");</p><p>　　start=clock();</p><p>　　

54、for(int i=0;i<10000;i++)</p><p>　　Test2(g_K);</p><p>　　finish=clock();</p><p>　　duration=finish-start;</p><p>　　for( i=1;i<=Number;i++)</p><p><b&

55、gt;　　{</b></p><p>　　for(int j=1;j<=Number;j++)//第一列為參賽人員</p><p>　　printf(" %d",a[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b&g

56、t;</p><p>　　printf("程序循環(huán)10000次所用的時(shí)間：%lfms\n",duration);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void Test2(int k){//分治策略非

57、遞歸方式實(shí)現(xiàn)</p><p>　　int i,j; </p><p><b>　　int n; </b></p><p>　　n=Number;//拷貝參賽選手人數(shù) </p><p>　　for(i=1;i<=n;i++) </p><p>　　a[1][i]=i; </p&g

58、t;<p>　　int m=1; //填充初始位置</p><p>　　for(int s=1;s<=k;s++) </p><p><b>　　{ </b></p><p><b>　　n/=2; </b></p><p>　　for(int t=1;t<=n;t

59、++) </p><p><b>　　{ </b></p><p>　　for(i = m+1 ; i <= 2*m ; i++) </p><p><b>　　{ </b></p><p>　　for(j = m+1 ; j <=2*m ; j++) </p>

60、<p><b>　　{ </b></p><p>　　a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m]; </p><p>　　a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]; </p><p><b>　　} </b>&l

61、t;/p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　m*=2; </b></p><p><b>　　} </b></p><p><b>　　}</b

62、></p><p>　　3.3 遞推策略算法的實(shí)現(xiàn)</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <time.h></p><p>　　const int MAX =

63、1024;//</p><p>　　int a[MAX][MAX];//二位數(shù)組</p><p>　　int Number=2,g_K=1;</p><p>　　clock_t start, finish;//開始和結(jié)束時(shí)間</p><p>　　double duration;//程序運(yùn)行時(shí)間</p><p>　　v

64、oid Test3(int k);//對(duì)推策略實(shí)現(xiàn)</p><p>　　int main(void)</p><p><b>　　{ </b></p><p>　　printf("請(qǐng)輸入指數(shù)k\n");</p><p>　　while(scanf("%d",&g_K)=

65、=0){</p><p>　　fflush(stdin);</p><p>　　printf("請(qǐng)輸入“整數(shù)”k\n");</p><p><b>　　}</b></p><p>　　for (int y=1;y<g_K;y++)</p><p>　　Number*=2;

66、</p><p>　　printf("參賽人員");</p><p>　　for(int z=1;z<Number;z++){</p><p>　　printf(" day%d",z);</p><p><b>　　}</b></p><p>　　sy

67、stem("cls");</p><p>　　start=clock();</p><p>　　for(int i=0;i<10000;i++)</p><p>　　Test3(Number);</p><p>　　finish=clock();</p><p>　　duration=fini

68、sh-start;</p><p>　　for( i=1;i<=Number;i++)</p><p><b>　　{</b></p><p>　　for(int j=1;j<=Number;j++)//第一列為參賽人員</p><p>　　printf(" %d",a[i][j]);&l

69、t;/p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("程序循環(huán)10000次所用的時(shí)間：%lfms\n",duration);</p><p><b>　　return 0;</b></p

70、><p><b>　　}</b></p><p>　　void Test3(int num){//遞推算法實(shí)現(xiàn)</p><p>　　a[1][1]=1;</p><p>　　int n,n0,i,j,k,k0;</p><p><b>　　n0=1;</b></p>

71、<p><b>　　n=2;</b></p><p>　　k=g_K;//人數(shù)</p><p>　　for (k0=1;k0<=k;k0++){</p><p>　　for (i=n0+1;i<=n;i++){</p><p>　　for (j=1;j<=n;j++){</p>

72、<p>　　a[i][j]=a[i-n0][j]+n0;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for (j=n0+1;j<=n;j++){</p><p>　　for (i=1;i<=n0;i++)</p&

73、gt;<p><b>　　{</b></p><p>　　a[i][j]=a[i][j-n0]+n0;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for (j=n0+1;j<=n;j++){</

74、p><p>　　for (i=n0+1;i<=n;i++){</p><p>　　a[i][j]=a[i][j-n0]-n0;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　n0=n;</b>

75、;</p><p><b>　　n=n*2;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4 測(cè)試和分析</b></p><p>　　4.1分治策略遞歸算法測(cè)試

76、</p><p><b>　　給出輸入情況：</b></p><p><b>　　得到輸出結(jié)果：</b></p><p>　　4.2分治策略遞歸算法時(shí)間復(fù)雜度的分析</p><p>　　遞歸算法的優(yōu)點(diǎn)是結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，贏此為設(shè)計(jì)算法、調(diào)試程序帶來很大的方便

77、。</p><p>　　遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)計(jì)算時(shí)間的還是占用存儲(chǔ)空間的都比非遞歸算法要多。</p><p><b>　　時(shí)間復(fù)雜度分析：</b></p><p>　　迭代處理的循環(huán)體內(nèi)部3個(gè)循環(huán)語句，每個(gè)循環(huán)語句都是一個(gè)嵌套的for循環(huán)，且它們的執(zhí)行次數(shù)相同，基本語句是最內(nèi)層循環(huán)體的賦值語句，即填寫比賽日程表的元素?；緢?zhí)行語句

78、的執(zhí)行次數(shù)是：</p><p>　　T(n)= 21*21=41</p><p>　　所以時(shí)間復(fù)雜度為O(4k)</p><p>　　4.3 分治策略非遞歸算法測(cè)試</p><p><b>　　給出輸入情況:</b></p><p><b>　　得到輸出結(jié)果:</b><

79、/p><p>　　4.4分治策略非遞歸算法時(shí)間復(fù)雜度的分析</p><p>　　時(shí)間復(fù)雜度為：O(5^(n-1)) </p><p>　　4.5 遞推策略算法測(cè)試</p><p><b>　　給出輸入情況:</b></p><p><b>　　得到輸出結(jié)果:</b></p&

80、gt;<p>　　4.6 遞推策略算法時(shí)間復(fù)雜度的分析</p><p>　　時(shí)間復(fù)雜度為：O(n^3) </p><p>　　4.7 三種算法的比較</p><p>　　分治遞歸：適用于分解后的小規(guī)模問題很好解決的問題</p><p>　　分治非遞歸：適用于分治遞歸算法設(shè)計(jì)過于復(fù)雜的問題</p><p>

81、　　遞推：適用于可根據(jù)已有結(jié)果推出結(jié)果的問題</p><p>　　通過對(duì)比可知分治非遞歸效率最高。分治遞歸更簡(jiǎn)便，效率差些，遞推的時(shí)間復(fù)雜度最大，效率最低。</p><p><b>　　5 總結(jié)</b></p><p>　　在這次課程設(shè)計(jì)當(dāng)中，我了解到了我的不足，如算法的不完善、不細(xì)心和耐心不是很好等等。不細(xì)心的我在調(diào)試程序時(shí)，老是因?yàn)槟硞€(gè)書寫

82、錯(cuò)誤導(dǎo)致錯(cuò)誤；對(duì)這些錯(cuò)誤，我不得不花大量的時(shí)間去更正，并且還要重復(fù)檢查是否出現(xiàn)雷同的錯(cuò)誤而導(dǎo)致程序不能運(yùn)行。但是通過這次課程設(shè)計(jì)，我的這些缺點(diǎn)有些改善。我在寫新的程序時(shí)，首先要考慮的深入一點(diǎn)、仔細(xì)一點(diǎn)，這樣要修改程序的時(shí)間就會(huì)少很多。并且也不會(huì)因?yàn)樽约翰患?xì)心而導(dǎo)致的浪費(fèi)時(shí)間的情況出現(xiàn)。  </p><p>　　在進(jìn)行程序設(shè)計(jì)時(shí)，要注意想好思路。即要有恰當(dāng)模塊名、變量名、常量名、子程序名等。將每個(gè)功能的模

83、塊，即函數(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)步。  </p>

84、<p>　　通過課程設(shè)計(jì)加強(qiáng)了我的動(dòng)手能力，以及提升了局部和統(tǒng)一考慮問題的思維方式。回顧起此次課程設(shè)計(jì)，至今我仍感慨頗多，的確，從從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，在整整半個(gè)月的日子里，可以學(xué)到很多很多的的東西，同時(shí)不僅可以鞏固了以前所學(xué)過的知識(shí)，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識(shí)。通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來，從理論中得出結(jié)

85、論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過程中遇到問題，可以說得是困難重重，這畢竟第一次做的，難免會(huì)遇到過各種各樣的問題，同時(shí)在設(shè)計(jì)的過程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過的知識(shí)理解得不夠深刻，掌握得不夠牢固，比如說結(jié)構(gòu)體??通過這次課程設(shè)計(jì)之后，一定把以前所學(xué)過的知識(shí)重新溫故。  </p><p>　　通過這次的課程設(shè)計(jì)，我學(xué)到了怎么樣從一個(gè)實(shí)際問題出發(fā)，建立模型

86、，找到相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法，實(shí)際運(yùn)行，反復(fù)調(diào)試和修改，最終實(shí)現(xiàn)功能。在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練，學(xué)會(huì)數(shù)據(jù)組織的方法，把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來并用軟件解決問題，培養(yǎng)了良好的程序設(shè)計(jì)技能。 </p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]　楊克昌．計(jì)算機(jī)常用算法與程序

87、設(shè)計(jì)案例教程．第2版．北京：清華大學(xué)出版社，2011．</p><p>　　[2]　呂國(guó)英．算法設(shè)計(jì)與分析．第2版．北京：清華大學(xué)出版社，2011．</p><p>　　[3] 王曉東：計(jì)算機(jī)算法分析與設(shè)計(jì)，電子工業(yè)出版社，2006. </p><p>　　[4] 嚴(yán)蔚敏吳偉民：數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，1997.</p>