《計算機(jī)算法設(shè)計與分析》課程設(shè)計

1、<p>　　用分治法解決快速排序問題及用動態(tài)規(guī)劃法解決最優(yōu)二叉搜索樹問題及用回溯法解決圖的著色問題</p><p><b>　　課程設(shè)計目的：</b></p><p>　　《計算機(jī)算法設(shè)計與分析》這門課程是一門實(shí)踐性非常強(qiáng)的課程，要求我們能夠?qū)⑺鶎W(xué)的算法應(yīng)用到實(shí)際中，靈活解決實(shí)際問題。通過這次課程設(shè)計，能夠培養(yǎng)我們獨(dú)立思考、綜合分析與動手的能力，并能加深對課

2、堂所學(xué)理論和概念的理解，可以訓(xùn)練我們算法設(shè)計的思維和培養(yǎng)算法的分析能力。</p><p><b>　　二、課程設(shè)計內(nèi)容：</b></p><p><b>　　1、分治法：</b></p><p><b>　　（2）快速排序；</b></p><p><b>　　2、動

3、態(tài)規(guī)劃：</b></p><p>　?。?）最優(yōu)二叉搜索樹；</p><p><b>　　3、回溯法：</b></p><p><b>　?。?）圖的著色。</b></p><p><b>　　三、概要設(shè)計：</b></p><p><

4、b>　　分治法—快速排序：</b></p><p>　　分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。分治法的條件：</p><p>　　該問題的規(guī)?？s小到一定的程度就可以容易地解決；</p><p>　　（2) 該問題可以分解為若干個

5、規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；</p><p>　　（3) 利用該問題分解出的子問題的解可以合并為該問題的解；</p><p>　?。?) 該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。</p><p>　　抽象的講，分治法有兩個重要步驟：</p><p><b>　?。?）將問題拆開；

6、</b></p><p><b>　　（2）將答案合并；</b></p><p>　　動態(tài)規(guī)劃—最優(yōu)二叉搜索樹：</p><p>　　動態(tài)規(guī)劃的基本思想是將問題分解為若干個小問題，解子問題，然后從子問題得到原問題的解。設(shè)計動態(tài)規(guī)劃法的步驟： </p><p>　　找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2）遞

7、歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；（3）以自底向上的方式計算出最優(yōu)值；（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。</p><p><b>　　回溯法—圖的著色</b></p><p>　　回溯法的基本思想是確定了解空間的組織結(jié)構(gòu)后，回溯法就是從開始節(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始節(jié)點(diǎn)就成為一個活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。

8、在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)就成為一個新的或節(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說，這個節(jié)點(diǎn)，這個結(jié)點(diǎn)不再是一個活結(jié)點(diǎn)。此時，應(yīng)往回（回溯）移動至最近一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結(jié)點(diǎn)為止。</p><p>　　四、詳

9、細(xì)設(shè)計與實(shí)現(xiàn)：</p><p><b>　　分治法—快速排序</b></p><p>　　快速排序是基于分治策略的另一個排序算法。其基本思想是，對于輸入的子數(shù)組,按以下三個步驟進(jìn)行排序：</p><p>　?。?）、分解(divide) 以元素為基準(zhǔn)元素將劃分為三段，和，使得中任何一個元素都小于，而中任何一個元素大于等于，下標(biāo)在劃分過程中確定。

10、</p><p>　　（2）、遞歸求解(conquer) 通過遞歸調(diào)用快速排序算法分別對和進(jìn)行排序。</p><p>　?。?）、合并(merge) 由于和的排序都是在原位置進(jìn)行的，所以不必進(jìn)行任何合并操作就已經(jīng)排好序了。</p><p>　　算法實(shí)現(xiàn)題: 現(xiàn)將數(shù)列{23 21 34 45 65 76 86 46 30 39 89 20 2

11、 3 8 47 38 54 59 40}進(jìn)行快速排序。</p><p><b>　　源程序如下：</b></p><p>　　#include <iostream></p><p>　　using namespace std;</p><p>　　#define size 20 </p&g

12、t;<p>　　int partition(int data[],int p,int r) </p><p><b>　　{ </b></p><p>　　int n=data[p],i=p+1,j=r,temp; </p><p>　　//將<n的元素交換到左邊區(qū)域</p><p>　　//將>

13、;n的元素交換到右邊區(qū)域</p><p>　　while(true) </p><p><b>　　{ </b></p><p>　　while(data[i]<n) ++i; </p><p>　　while(data[j]>n) --j;</p><p><b>　　if

14、(i>=j) </b></p><p><b>　　break; </b></p><p>　　temp=data[i]; data[i]=data[j]; data[j]=temp; </p><p><b>　　} </b></p><p>　　data[p]=data[

15、j]; </p><p>　　data[j]=n; </p><p>　　return j; </p><p><b>　　}</b></p><p>　　void quick_sort(int data[],int p,int r) </p><p>　　{ if(p>=r)

16、 </p><p><b>　　return; </b></p><p>　　int q=partition(data,p,r); </p><p>　　quick_sort(data,p,q-1); //對左半段排序</p><p>　　quick_sort(data,q+1,r); //對右半段排序</p>

17、;<p><b>　　} </b></p><p>　　int main() </p><p><b>　　{ </b></p><p>　　int i,n,data[size];</p><p>　　printf("請輸入要排列的數(shù)目（<=20）：");&l

18、t;/p><p>　　scanf("%d",&n);</p><p>　　printf("請輸入要排列的數(shù)列：\n");</p><p>　　for(i=0;i<n;++i) </p><p>　　scanf("%d",&data[i]); </p>

19、<p>　　quick_sort(data,0,n-1);</p><p>　　printf("排列后的數(shù)列為：\n"); </p><p>　　for(i=0;i<n;++i) </p><p>　　printf( "%d ",data[i]); </p><p&g

20、t;　　printf("\n");</p><p>　　return 0; </p><p><b>　　} </b></p><p><b>　　運(yùn)行結(jié)果如下：</b></p><p><b>　　圖1</b></p><p>　　

21、動態(tài)規(guī)劃—最優(yōu)二叉搜索樹</p><p>　　1、最優(yōu)二叉搜索樹問題描述和分析：</p><p>　　設(shè)是有序集，且，表示有序集S的二叉搜索樹利用二叉樹的結(jié)點(diǎn)存儲有序集中的元素。它具有下述性質(zhì)：存儲于每個結(jié)點(diǎn)中的元素x大于其左子樹中任一結(jié)點(diǎn)所存儲的元素，小于其右子樹中任一結(jié)點(diǎn)所存儲的元素。二叉樹的葉結(jié)點(diǎn)是形如的開區(qū)間，在表示S的二叉搜索樹中搜索元素x，返回的結(jié)果有兩種情況：</p&g

22、t;<p>　?。?）在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到。</p><p>　?。?）在二叉搜索樹的葉結(jié)點(diǎn)中確定。</p><p>　　設(shè)在第(1)中情形中找到元素的概率為；在第(2)種情形中確定的概率為。其中約定。顯然有：</p><p>　　稱為集合S的存取概率分布。</p><p>　　在表示S的二叉搜索樹T中，設(shè)存儲元素的結(jié)點(diǎn)深

23、度為；葉結(jié)點(diǎn)的結(jié)點(diǎn)深度為，則：</p><p>　　表示在二叉搜索樹T中進(jìn)行一次搜索所需要的平均比較次數(shù)，p又成為二叉搜索樹T的平均路長。在一般情況下，不同的二叉搜索樹的平均路長是不相同的。</p><p>　　最優(yōu)二叉搜索樹問題是對于有序集S及其存取概率分布，在所有表示有序集S的二叉搜索樹中找到一棵具有最小平均路長的二叉搜索樹。</p><p>　　2、最優(yōu)子結(jié)構(gòu)

24、性質(zhì)：</p><p>　　二叉搜索樹T的一棵含有結(jié)點(diǎn)和葉結(jié)點(diǎn)的子樹可以看作是有序集關(guān)于全集合的一棵二叉搜索樹，其存取概率為以下的條件概率：</p><p><b>　　式中，。</b></p><p>　　設(shè)是有序集關(guān)于存取概率的一棵最優(yōu)二叉搜索樹，其平均路長為。的根結(jié)點(diǎn)存儲元素。其左右子樹和的平均路長分別為和。由于和中結(jié)點(diǎn)深度是它們在中的結(jié)

25、點(diǎn)深度減1，故有：</p><p>　　由于是關(guān)于集合的一棵二叉搜索樹，故。若，則用替換可得到平均路長比更小的二叉搜索樹。這與是最優(yōu)二叉搜索樹矛盾。故是一棵最優(yōu)二叉搜索樹。同理可證也是一棵最優(yōu)二叉搜索樹。因此最優(yōu)二叉搜索樹問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。</p><p>　　3、遞歸計算最優(yōu)值：</p><p>　　最優(yōu)二叉搜索樹的平均路長為，則所求的最優(yōu)值為。由最優(yōu)二叉搜

26、索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計算的遞歸式如下：</p><p><b>　　初始時，。</b></p><p>　　記為，則為所求的最優(yōu)值。</p><p><b>　　計算的遞歸式為：</b></p><p>　　據(jù)此，可設(shè)計出解最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法。</p><

27、p>　　算法實(shí)現(xiàn)題: 給出標(biāo)識符集{1,2,3}={do,if,stop}存取概率，若b1=0.4 b2=0.2 b3=0.05 a0=0.2 a1=0.05 a2=0.05 a3=0.05構(gòu)造一棵最優(yōu)二叉搜索樹</p><p><b>　　源程序如下：</b></p><p>　　#include<iostream></p>

28、<p>　　using namespace std;</p><p>　　void OptimalBinarySearchTree(float a[],float b[],int n,float m[][20],int s[][20],float w[][20])</p><p>　　{

29、 //求解最優(yōu)值的方法</p><p>　　int i,r,k;</p><p><b>　　float t;</b></p><p>　　for(i=0;i<=n;i++){</p><p>　　w[i+1][i]=a[i];

30、//搜索不到的點(diǎn),最優(yōu)解為0</p><p>　　m[i+1][i]=0; </p><p><b>　　}</b></p><p>　　for(r=0;r<n;r++)</p><p>　　for(i=1;i<=n-r;i++){</p><p>　　int

31、j=i+r; //左子樹為空</p><p>　　w[i][j]=w[i][j-1]+a[j]+b[j];</p><p>　　m[i][j]=m[i+1][j];</p><p>　　s[i][j]=i;</p><p>　　for(k=i+1;k<=j;k++){

32、</p><p>　　t=m[i][k-1]+m[k+1][j];</p><p>　　if(t<m[i][j])</p><p>　　{ //以k為根節(jié)點(diǎn)，左子樹不為空</p><p>　　m[i][j]=t;</p><p>　　s[i][j

33、]=k; </p><p>　　} </p><p><b>　　} </b></p><p>　　m[i][j]+=w[i][j]; }</p><p>　　for(i=1;i<=n;i++

34、)</p><p>　　for(int j=1;j<=n;j++)</p><p>　　cout<<"s["<<i<<"]["<<j<<"]="<<s[i][j]<<endl;</p><p><b>　　}

35、</b></p><p>　　void print(int i,int j,int s[][20],int S[]) //遞歸輸出結(jié)果</p><p><b>　　{</b></p><p>　　if(j>=i){ </p><p>　　int k=s

36、[i][j];</p><p>　　cout<<"(";</p><p>　　print(i,k-1,s,S);</p><p>　　cout<<")";</p><p>　　cout<<" "<<S[k]<<"

37、 ";</p><p>　　cout<<"(";</p><p>　　print(k+1,j,s,S);</p><p>　　cout<<")";</p><p><b>　　}</b></p><p><b>　

38、　}</b></p><p>　　int main()</p><p>　　{ //主函數(shù)</p><p><b>　　int n,i;</b></p><p>　　float a[20],b[20],m[

39、20][20],w[20][20];</p><p>　　int s[20][20],S[20];</p><p>　　cout<<"請輸入有序集元素的個數(shù)n："<<endl;</p><p><b>　　cin>>n;</b></p><p>　　cout<

40、<"請輸入有序集各元素的值S[i](一共"<<n<<"個):"<<endl;</p><p>　　for(i=1;i<=n;i++)</p><p>　　cin>>S[i];</p><p>　　cout<<"請輸入概率數(shù)組a的各元素的值a[i]

41、(一共"<<n+1<<"個):"<<endl;</p><p>　　for(i=0;i<=n;i++)</p><p>　　cin>>a[i];</p><p>　　cout<<"請輸入概率數(shù)組b的各元素的值b[i](一共"<<n<&

42、lt;"個):"<<endl;</p><p>　　for(i=1;i<=n;i++)</p><p>　　cin>>b[i];</p><p>　　OptimalBinarySearchTree(a,b,n,m,s,w);</p><p>　　cout<<"最優(yōu)值即平均

43、步長為："<<m[1][n]<<endl;</p><p><b>　　}</b></p><p><b>　　運(yùn)行結(jié)果如下：</b></p><p><b>　　圖2</b></p><p><b>　　回溯法—圖的著色</b

44、></p><p>　　1、圖的m著色問題描述：</p><p>　　給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個頂點(diǎn)著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點(diǎn)著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。</

45、p><p><b>　　2、算法設(shè)計：</b></p><p>　　一般連通圖的可著色法問題并不僅限于平面圖。給定圖和m種顏色，如果這個圖不是m可著色，則給出否定答案；如果這個圖是m可著色的，找出所有不同的著色方法</p><p>　　下面根據(jù)回朔法的遞歸描述框架設(shè)計圖的m著色算法。用圖的鄰接矩陣a表示無向量連通圖。若屬于圖的邊集E，則，否則。整數(shù)

46、1，2，…，m用來表示m種不同顏色。頂點(diǎn)所有顏色用表示，數(shù)組是問題的解向量。問題的解空間可表示為一棵高度為n+1的完全m叉樹。解空間樹的第層中每一結(jié)點(diǎn)都有m個兒子，每個兒子相應(yīng)于的m個可能的著色之一。 第n+1層結(jié)點(diǎn)均為葉結(jié)點(diǎn)。 </p><p>　　在下面的解圖的m可著色問題的回溯法中，搜索解空間中第層子樹。類的數(shù)據(jù)成員記錄解空間中結(jié)點(diǎn)信息，以減少傳給的參數(shù)。記錄當(dāng)前已找到的m著色方案數(shù)。</p>

47、<p>　　在算法中，當(dāng)時，算法搜索至葉結(jié)點(diǎn)，得到新的m著色方案，當(dāng)前找到的m著色方案數(shù)則增1。而當(dāng)時,當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個解空間中內(nèi)部結(jié)點(diǎn).該結(jié)點(diǎn)有共m個兒子結(jié)點(diǎn).對當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一兒子結(jié)點(diǎn),有方法ok檢查其可行性,并以深度優(yōu)先的方式遞歸的對可行子樹搜索,或減去不可行樹。</p><p>　　算法實(shí)現(xiàn)題: 給定如圖3所示的一個無向連通圖G，現(xiàn)有4種不同的顏色，用這4種顏色為圖G的各頂點(diǎn)著色，每

48、個頂點(diǎn)著一種顏色。要求：G中每條邊的2個頂點(diǎn)著有不同的顏色。問一共有多少種著色方案？</p><p><b>　　圖3</b></p><p><b>　　源程序如下：</b></p><p>　　#include <iostream></p><p>　　using namespace

49、 std;</p><p>　　int n; //圖的頂點(diǎn)個數(shù)</p><p>　　int m; //可用顏色數(shù)</p><p>　　int i,j;

50、 </p><p>　　int a[10][10]; //程序中使用時從下標(biāo)1開始;程序中用于存儲圖的鄰接矩陣</p><p>　　int x[10]; //用于存儲當(dāng)前解</p><p>　　long sum;

51、 //當(dāng)前已找到的可著色方案數(shù)</p><p>　　bool Ok(int k)</p><p><b>　　{</b></p><p>　　for(int j=1;j<=n;j++)</p><p><b>　　{</b></p><p

52、>　　if((a[k][j]==1)&&(x[j]==x[k])) //a[k][j]==1表示的是第k點(diǎn)和第j點(diǎn)是相連的</p><p>　　return false;</p><p><b>　　}</b></p><p>　　return true;</p><p><b&g

53、t;　　}</b></p><p>　　void Backtrack(int t)</p><p><b>　　{</b></p><p>　　if(t>n) //t是表示的第t行葉結(jié)點(diǎn)；圖的m著色共有n個結(jié)點(diǎn)</p><p><b>　　{<

54、;/b></p><p><b>　　sum++;</b></p><p>　　cout<<" 第"<<sum<<"種解決方案為 ：\n";</p><p>　　for(int i=1;i<=n;i++)</p><p>

55、;<b>　　{</b></p><p>　　cout<<x[i]<<" "; </p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p&

56、gt;<p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(int i=1;i<=m;i++)</p><p><b>　　{</b></p><p><b>　　x[t]=i;</b>

57、;</p><p><b>　　if(Ok(t))</b></p><p><b>　　{</b></p><p>　　Backtrack(t+1); //判斷t+1結(jié)點(diǎn)的顏色是不是正確</p><p><b>　　}</b></

58、p><p>　　x[t]=0; //把t+1結(jié)點(diǎn)的顏色換一種</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

59、t;　　long mColoring(int mm)</p><p><b>　　{</b></p><p><b>　　m=mm;</b></p><p><b>　　sum=0;</b></p><p>　　Backtrack(1);</p><p>

60、;　　return sum;</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　cout<<"\n\t==========圖的m著色問題============\n";<

61、;/p><p>　　cout<<"輸入圖的頂點(diǎn)數(shù)與可用的顏色數(shù) :\n";</p><p>　　cin>>n>>m;</p><p>　　cout<<"\n==========輸入圖的鄰接矩陣\n";</p><p>　　for(i=1;i<=n;i++

62、)</p><p>　　for(j=1;j<=n;j++)</p><p>　　cin>>a[i][j];</p><p>　　cout<<"\n==========判斷可著色性\n";</p><p>　　mColoring(m);</p><p>　　if(sum=

63、=0)</p><p>　　cout<<" 無可行方案！"<<endl;</p><p>　　cout<<"-------------------------------------------------------------------------------"<<endl;</p>

64、<p>　　cout<<n<<" 個頂點(diǎn)"<<"按所給的鄰接關(guān)系著 "<<m<<" 種顏色，總的著色方案有 "<<sum<<" 個\n";</p><p><b>　　}</b></p><p&g

65、t;<b>　　運(yùn)行結(jié)果如下：</b></p><p><b>　　圖4</b></p><p><b>　　圖5</b></p><p><b>　　五、總結(jié)：</b></p><p>　　通過本次課程設(shè)計，使我對快速排序、最優(yōu)二叉搜索樹以及圖的m著色設(shè)

66、計的基本過程的設(shè)計方法、步驟、思路、有了一定的了解與認(rèn)識。在這次課程設(shè)計過程中，我認(rèn)識到只是知道課本上的理論知識是遠(yuǎn)遠(yuǎn)不夠的，我們還必須要深切的理解每個算法的思想，并且能夠利用c++語言去編寫相關(guān)的代碼，經(jīng)過不斷的修改、調(diào)試，使之能解決相應(yīng)的問題，最終能運(yùn)用到實(shí)際案例中去。 </p><p>　　對我們來說，實(shí)際能力的培養(yǎng)至關(guān)重要，而這種實(shí)際能力的培養(yǎng)單靠課堂教學(xué)是遠(yuǎn)遠(yuǎn)不夠的，必須從課堂走向?qū)嵺`。而這次的課程設(shè)計