1、 計算機算法設計與分析課程設計 分治法解決合并排序問題及動態規劃解決矩陣連乘和最長公共子序列問題及貪心法解決哈夫曼編碼問題一、課程設計目的本次課程設計可以說是我們學完計算機算法設計與分析這門課程后的一次綜合性訓練。 本課程設計的訓練的目的是：1、 鞏固和掌握計算機算法設計和分析課程的基礎知識。2、 培養使用計算機基本算法解決實際問題的能力。3、 提升使用程序設計語言對算法程序的開發、調試和測試能力。4、 對一定的實際問題，能夠設計求解算法并分析算法的效率。5、提高綜合運用算法、程序設計語言等能力。6、掌握文檔的書寫能力。二、課程設計內容1、 分治法（1） 合并排序2、 動態規劃（1） 矩陣連乘

2、（2） 最長公共子序列3、 貪心法（1） 哈夫曼編碼三、概要設計1、 分治法基本思想:將規模為n的問題分解為k個規模較小的子問題，使這些子問題相互獨立可分別求解，再將k個子問題的解合并成原問題的解。如子問題的規模仍很大，則反復分解直到問題小到可直接求解為止。在分治法中,子問題的解法通常與原問題相同。（1） 合并排序問題描述將n個元素排成非遞減順序。算法思路若n為1，算法終止；否則，將n個待排元素分割成k(k=2)個大致相等子集合A, B, 對每一個子集合分別遞歸排序,再將排好序的子集歸并為一個集合。2、 動態規劃基本思想：將問題的求解過程化為多步選擇，在每一步選擇上，列出各種可能的結果(各子問

3、題的可行解)，舍去那些肯定不能成為最優解的局部解。最后一步得到的解必是最優解。求解過程多為自底向上,求解過程產生多個選擇序列, 下一步的選擇依賴上一步的結果，總能得到最優解。（1） 矩陣連乘問題描述給定n個矩陣A1，An，其中Ai與A(i-1)是可相乘的。確定一個計算次序，使計算矩陣連乘積A1An所需計算量最少。例如，三個矩陣連乘，兩種計算順序(A*B)*C，A*(B*C)。設A為100*1的矩陣，B為1*100的矩陣，C為100*1的矩陣, 則 D=A*B為100*100的矩陣, 需乘法次數為10000, D與C相乘，所需乘法次數為1000000, 計算(A*B)*C的總時間長度為10100

4、00。E=B*C需乘法次數為10000, B*C為1*1的矩陣，E與A相乘，所需乘法數為100，計算A*(B*C)的時間長度只有10100。計算(A*B)*C時，還需10000個單元來存儲A*B，而A*(B*C)計算過程中,只需用1個單元來存儲B*C。算法思路將步驟化為多步,自底向上,先求出矩陣鏈長為1的最優計算次序，鏈長為2的最優次序，最優解結構設A1:n= A1An，最優計算次序在Ak和A(k+1)間斷開，則總計算量=A1:k的計算量+Ak+1:n的計算量+A1:k*Ak+1:n則矩陣子鏈A1:k和Ak+1:n的計算次序也必最優。遞推關系設計算Ai:j=AiAj所需最少次數乘法為mij，A

5、i的維數設為matrixi.row*matrixi.col。構造最優解記mij的斷開位置k為sij,在計算出mij后,可由sij遞歸構造相應的最優解。（2） 最長公共子序列問題描述字符序列的子序列是指從給定字符序列中隨意地（不一定連續）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列x=“x0，x1，x(m-1)”，序列y=“y0，y1，y(k-1)”是x的子序列，存在x的一個嚴格遞增下標序列<i0，i1，i(k-1)>，使得對所有的j=0，1，k-1，有xij=yj。算法思路引進一個二維數組c，用cij記錄xi與yj的LCS 的長度，bij記錄cij是通過哪

6、一個子問題的值求得的，以決定搜索的方向。由自底向上進行遞推計算，那么在計算ci,j之前 ci-1j-1，ci-1j與cij-1均已計算出來。此時我們根據xi=yj還是xi!=yj，就可以計算出cij。問題的遞歸式寫成：3、 貪心法基本思想:將問題的求解過程看作一系列選擇，每次選擇都是當前狀態下的局部最優解。每作一次選擇后，所求問題會簡化為一個規模更小的子問題。從而通過每一步的最優解逐步達到整體最優解。（1） 哈夫曼編碼問題描述 通訊過程中需將傳輸的信息轉換為二進制碼。由于英文字母使用頻率不同，若頻率高的字母對應短的編碼，頻率低的字母對應長的編碼，傳輸的數據總量就會降低。要求找到一個編碼方案，使

7、傳輸的數據量最少。哈夫曼編碼就是一種最佳編碼方案。算法思路1)以n個字母為結點構成n棵僅含一個點的二叉樹集合，字母的頻率即為結點的權。2)每次從二叉樹集合中找出兩個權最小者合并為一棵二叉樹：增加一個根結點將這兩棵樹作為左右子樹。新樹的權為兩棵子樹的權之和。3) 反復進行步驟2)直到只剩一棵樹為止。四、詳細設計與實現1、合并排序例： 序列分解過程： 8 4 7 3 6 5 2 8 4 7 3 6 5 2 8 4 7 3 6 5 2 初始序列a a0 a1 a2 a3 a4 a5 a6 8 4 7 3 6 5 2 排序后歸并到b 4 8 7 3 6 5 2 復制到a 4 8 7 3 6 5 2 排

8、序后歸并到b 3 4 7 8 2 5 6 復制到a 3 4 7 8 2 5 6 排序后歸并到b 2 3 4 5 6 7 8 復制到a 2 3 4 5 6 7 8 最終結果為： 2 3 4 5 6 7 8C+實現代碼為：#include <iostream>using namespace std;void Merge(int a,int b,int l,int m,int r)/合并al:m和bm+1:r存入到bl:r中int i=l,j=m+1,k=l;while (i<=m)&&(j<=r)if (ai<=aj)bk+=ai+;else bk+=

9、aj+;if (i>m)for(int q=j;q<=r;q+)bk+=aq;else for(int q=i;q<=m;q+)bk+=aq;void Copy(int a,int b,int s,int n)for(int i=s;i<=n;i+)ai=bi;void MergeSort(int a,int left,int right)int i;if(left<right)/至少有2個元素 i=(left+right)/2;/取中點int b100;MergeSort(a,left,i);/遞歸調用分別對兩個字問題排序MergeSort(a,i+1,righ

10、t);Merge(a,b,left,i,right);/合并到數組bCopy(a,b,left,right);/復制回數組aint main()int a100;int n,i;cout<<"輸入元素個數n:"cin>>n;cout<<"輸入一維數組a"<<n<<":"for( i=0;i<n;i+)cin>>ai;MergeSort(a,0,n-1);cout<<"輸出排序為:"for ( i=0;i<n;i+)cou

11、t<<ai<<' 'cout<<endl;return 0;運行截圖：2、矩陣連乘例：A1A2A3A4A5A630*3535*1515*55*1010*2020*25結果為：(A1(A2A3)(A4A5)A6)C+實現代碼：#include<iostream>#define MAX 100using namespace std;struct Matrix /矩陣int row; /矩陣行數int col; /矩陣列數;/矩陣Matrix matrixMAX;/mij存儲Ai到Aj的最小乘法次數int mMAXMAX;/sij存儲A

12、i到Aj之間加括號的位置int sMAXMAX;/矩陣個數int n;void MaxtrixChain(Matrix matrixMAX,int n,int mMAXMAX,int sMAXMAX)/計算m和sfor(int r=2;r<=n;r+)for(int i=1;i<=n-r+1;i+)int j=i+r-1;mij=mi+1j+matrixi.row*matrixi.col*matrixj.col;sij=i;for(int k=i+1;k<j;k+)int t=mik+mk+1j+matrixi.row*matrixk.col*matrixj.col;if(t

13、<mij)mij=t;sij=k;void matrixMultiply(Matrix matrixMAX,int n)bool flag=false;/標識矩陣的階數是否要重新輸入int i;cout<<"請輸入每個矩陣行數與列數:"<<endl;for(i=1;i<=n;i+)cout<<"A"<<i<<"行數："cin>>matrixi.row;cout<<"A"<<i<<"列數：

14、"cin>>matrixi.col; /檢查Ai的列數是否等于Ai+1的行數for(i=1;i<n;i+)if(matrixi.col!=matrixi+1.row)cout<<"輸入的矩陣不可乘，請重新輸入!"<<endl;flag=true;break;if(flag)matrixMultiply(matrix,n);/打印加括號后的void traceback(int i,int j)if(i=j)cout<<"A"<<i;elsecout<<"(&q

15、uot;traceback(i,sij);traceback(sij+1,j);cout<<")"void main()/變量m,s初始化memset(m,0,sizeof(m);memset(s,0,sizeof(s);cout<<"請輸入矩陣的個數:"<<endl;cin>>n;matrixMultiply(matrix,n);MaxtrixChain(matrix,n,m,s);cout<<"加括號之后:"<<endl;traceback(1,n);cout

16、<<endl;運行截圖：3、最長公共子序列例：x="cbwdabh" y="sdabwyz" cij： bij：最終結果為：dabC+實現代碼：#include<iostream>using namespace std;#define MAX 100void LCSLength(char *x,char *y,int m,int n,int cMAXMAX,int bMAXMAX)/用b對c中的元素分成三類 int i, j; for(i=0;i<=m;i+) ci0=0; for(j=1;j<=n;j+) c0j=0

17、; for(i=1;i<=m;i+) for(j=1;j<=n;j+) if(xi-1=yj-1)/第一類c中的元素 cij=ci-1j-1+1; bij=1; else if(ci-1j>=cij-1)/第二類c中元素 cij=ci-1j; bij=2; else/第三類c中元素 cij=cij-1; bij=3; void LCS(int bMAXMAX,char *x,int i,int j) if(i=0|j=0) return; if(bij=1)/輸出第一類元素對應的x LCS(b,x,i-1,j-1); cout<<xi-1; else if(bij

18、=2)/輸出第二類元素對應的x LCS(b,x,i-1,j); else/輸出第三類元素對應的x LCS(b,x,i,j-1);void main()char xMAX; char yMAX ; cout<<"輸入字符串x:"<<endl; cin>>x; cout<<"輸入字符串y:"<<endl; cin>>y; int bMAXMAX; int cMAXMAX; int m,n; m=strlen(x); n=strlen(y);LCSLength(x,y,m,n,c,b);c

19、out<<"最長公共子序列為:"<<endl; LCS(b,x,m,n);cout<<endl;運行截圖：4、Hufman編碼例： a b c d e f頻率：45 13 12 16 9 51695141213455525301000001001111acbfed哈夫曼樹為：結果為：a:0 b:101 c:100 d:111 e:1101 f:1100C+實現代碼：#include<iostream> #include<string>#define MAX 32767;using namespace std;typ

20、edef struct/定義哈夫曼結點結構體int weight;/權值int flag;/標識是否有父母結點int parent;/父母結點int lchild; /左孩子結點int rchild;/右孩子結點 hnodetype;typedef struct /定義哈夫曼編碼結構體int bit10;/定義編碼數組int start;char leaf; hcodetype;void huffman(char cha,int m,int n)int i,j,m1,m2,x1,x2,c,p;hnodetype *huffnode=new hnodetype2*n-1;/動態分配結構體空間hc

21、odetype *huffcode=new hcodetypen,cd;/定義for(i=0;i<2*n-1;i+) /對哈夫曼結點結構體初始化huffnodei.weight=0;huffnodei.parent=0;huffnodei.flag=0;huffnodei.lchild=-1;huffnodei.rchild=-1;for(i=0;i<n;i+)/給結構體進行賦值huffnodei.weight=mi;/給哈夫曼結點賦權值huffcodei.leaf=chai;/給哈夫曼編碼葉子賦字符for(i=0;i<n-1;i+)/找出最小的兩個頻率樹并合并出一個新的樹m

22、1=m2=MAX;x1=x2=0;for(j=0;j<n+i;j+)if (huffnodej.weight<=m1&&huffnodej.flag=0)m2=m1; x2=x1; m1=huffnodej.weight; x1=j; else if(huffnodej.weight<=m2&&huffnodej.flag=0) m2=huffnodej.weight; x2=j;huffnodex1.parent=n+i;huffnodex2.parent=n+i;huffnodex1.flag=1;huffnodex2.flag=1;huf

23、fnoden+i.weight=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; huffnoden+i.rchild=x2;for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=0)/構建哈夫曼編碼權值if(huffnodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-;c=p;p=huffnodec.parent; cout<<huffcodei.leaf<<":"for(j=cd.start+1;j<n;j+)/輸出編碼值huffcodei.bitj=cd.bitj;cout<<cd.bitj;cout<<endl;huffcodei.start=cd.start;delete huffcode;/釋放空間delete huffnode;/釋放空間void main()int i=0,n,m100,k;char cha100;cout<<"輸入的總字符n:"cin>>n;k=n;for(i