分治法解決合并排序問(wèn)題及動(dòng)態(tài)規(guī)劃解決矩陣連乘和最長(zhǎng)公共子序列問(wèn)題及貪心法解決哈夫曼編碼問(wèn)題

1、 計(jì)算機(jī)算法設(shè)計(jì)與分析課程設(shè)計(jì) 分治法解決合并排序問(wèn)題及動(dòng)態(tài)規(guī)劃解決矩陣連乘和最長(zhǎng)公共子序列問(wèn)題及貪心法解決哈夫曼編碼問(wèn)題一、課程設(shè)計(jì)目的本次課程設(shè)計(jì)可以說(shuō)是我們學(xué)完計(jì)算機(jī)算法設(shè)計(jì)與分析這門(mén)課程后的一次綜合性訓(xùn)練。 本課程設(shè)計(jì)的訓(xùn)練的目的是：1、 鞏固和掌握計(jì)算機(jī)算法設(shè)計(jì)和分析課程的基礎(chǔ)知識(shí)。2、 培養(yǎng)使用計(jì)算機(jī)基本算法解決實(shí)際問(wèn)題的能力。3、 提升使用程序設(shè)計(jì)語(yǔ)言對(duì)算法程序的開(kāi)發(fā)、調(diào)試和測(cè)試能力。4、 對(duì)一定的實(shí)際問(wèn)題，能夠設(shè)計(jì)求解算法并分析算法的效率。5、提高綜合運(yùn)用算法、程序設(shè)計(jì)語(yǔ)言等能力。6、掌握文檔的書(shū)寫(xiě)能力。二、課程設(shè)計(jì)內(nèi)容1、 分治法（1） 合并排序2、 動(dòng)態(tài)規(guī)劃（1） 矩陣連乘

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

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

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

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

6、一個(gè)子問(wèn)題的值求得的，以決定搜索的方向。由自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算ci,j之前 ci-1j-1，ci-1j與cij-1均已計(jì)算出來(lái)。此時(shí)我們根據(jù)xi=yj還是xi!=yj，就可以計(jì)算出cij。問(wèn)題的遞歸式寫(xiě)成：3、 貪心法基本思想:將問(wèn)題的求解過(guò)程看作一系列選擇，每次選擇都是當(dāng)前狀態(tài)下的局部最優(yōu)解。每作一次選擇后，所求問(wèn)題會(huì)簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題。從而通過(guò)每一步的最優(yōu)解逐步達(dá)到整體最優(yōu)解。（1） 哈夫曼編碼問(wèn)題描述 通訊過(guò)程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進(jìn)制碼。由于英文字母使用頻率不同，若頻率高的字母對(duì)應(yīng)短的編碼，頻率低的字母對(duì)應(yīng)長(zhǎng)的編碼，傳輸?shù)臄?shù)據(jù)總量就會(huì)降低。要求找到一個(gè)編碼方案，使

7、傳輸?shù)臄?shù)據(jù)量最少。哈夫曼編碼就是一種最佳編碼方案。算法思路1)以n個(gè)字母為結(jié)點(diǎn)構(gòu)成n棵僅含一個(gè)點(diǎn)的二叉樹(shù)集合，字母的頻率即為結(jié)點(diǎn)的權(quán)。2)每次從二叉樹(shù)集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹(shù)：增加一個(gè)根結(jié)點(diǎn)將這兩棵樹(shù)作為左右子樹(shù)。新樹(shù)的權(quán)為兩棵子樹(shù)的權(quán)之和。3) 反復(fù)進(jìn)行步驟2)直到只剩一棵樹(shù)為止。四、詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)1、合并排序例： 序列分解過(guò)程： 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 復(fù)制到a 4 8 7 3 6 5 2 排

8、序后歸并到b 3 4 7 8 2 5 6 復(fù)制到a 3 4 7 8 2 5 6 排序后歸并到b 2 3 4 5 6 7 8 復(fù)制到a 2 3 4 5 6 7 8 最終結(jié)果為： 2 3 4 5 6 7 8C+實(shí)現(xiàn)代碼為：#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個(gè)元素 i=(left+right)/2;/取中點(diǎn)int b100;MergeSort(a,left,i);/遞歸調(diào)用分別對(duì)兩個(gè)字問(wèn)題排序MergeSort(a,i+1,righ

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

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

12、i到Aj之間加括號(hào)的位置int sMAXMAX;/矩陣個(gè)數(shù)int n;void MaxtrixChain(Matrix matrixMAX,int n,int mMAXMAX,int sMAXMAX)/計(jì)算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;/標(biāo)識(shí)矩陣的階數(shù)是否要重新輸入int i;cout<<"請(qǐng)輸入每個(gè)矩陣行數(shù)與列數(shù):"<<endl;for(i=1;i<=n;i+)cout<<"A"<<i<<"行數(shù)："cin>>matrixi.row;cout<<"A"<<i<<"列數(shù)：

14、"cin>>matrixi.col; /檢查Ai的列數(shù)是否等于Ai+1的行數(shù)for(i=1;i<n;i+)if(matrixi.col!=matrixi+1.row)cout<<"輸入的矩陣不可乘，請(qǐng)重新輸入!"<<endl;flag=true;break;if(flag)matrixMultiply(matrix,n);/打印加括號(hào)后的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<<"請(qǐng)輸入矩陣的個(gè)數(shù):"<<endl;cin>>n;matrixMultiply(matrix,n);MaxtrixChain(matrix,n,m,s);cout<<"加括號(hào)之后:"<<endl;traceback(1,n);cout

16、<<endl;運(yùn)行截圖：3、最長(zhǎng)公共子序列例：x="cbwdabh" y="sdabwyz" cij： bij：最終結(jié)果為：dabC+實(shí)現(xiàn)代碼：#include<iostream>using namespace std;#define MAX 100void LCSLength(char *x,char *y,int m,int n,int cMAXMAX,int bMAXMAX)/用b對(duì)c中的元素分成三類(lèi) 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)/第一類(lèi)c中的元素 cij=ci-1j-1+1; bij=1; else if(ci-1j>=cij-1)/第二類(lèi)c中元素 cij=ci-1j; bij=2; else/第三類(lèi)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)/輸出第一類(lèi)元素對(duì)應(yīng)的x LCS(b,x,i-1,j-1); cout<<xi-1; else if(bij

18、=2)/輸出第二類(lèi)元素對(duì)應(yīng)的x LCS(b,x,i-1,j); else/輸出第三類(lèi)元素對(duì)應(yīng)的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<<"最長(zhǎng)公共子序列為:"<<endl; LCS(b,x,m,n);cout<<endl;運(yùn)行截圖：4、Hufman編碼例： a b c d e f頻率：45 13 12 16 9 51695141213455525301000001001111acbfed哈夫曼樹(shù)為：結(jié)果為：a:0 b:101 c:100 d:111 e:1101 f:1100C+實(shí)現(xiàn)代碼：#include<iostream> #include<string>#define MAX 32767;using namespace std;typ

20、edef struct/定義哈夫曼結(jié)點(diǎn)結(jié)構(gòu)體int weight;/權(quán)值int flag;/標(biāo)識(shí)是否有父母結(jié)點(diǎn)int parent;/父母結(jié)點(diǎn)int lchild; /左孩子結(jié)點(diǎn)int rchild;/右孩子結(jié)點(diǎn) hnodetype;typedef struct /定義哈夫曼編碼結(jié)構(gòu)體int bit10;/定義編碼數(shù)組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;/動(dòng)態(tài)分配結(jié)構(gòu)體空間hc

21、odetype *huffcode=new hcodetypen,cd;/定義for(i=0;i<2*n-1;i+) /對(duì)哈夫曼結(jié)點(diǎn)結(jié)構(gòu)體初始化huffnodei.weight=0;huffnodei.parent=0;huffnodei.flag=0;huffnodei.lchild=-1;huffnodei.rchild=-1;for(i=0;i<n;i+)/給結(jié)構(gòu)體進(jìn)行賦值huffnodei.weight=mi;/給哈夫曼結(jié)點(diǎn)賦權(quán)值huffcodei.leaf=chai;/給哈夫曼編碼葉子賦字符for(i=0;i<n-1;i+)/找出最小的兩個(gè)頻率樹(shù)并合并出一個(gè)新的樹(shù)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)/構(gòu)建哈夫曼編碼權(quán)值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