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

1、《計算機算法設(shè)計與分析》課程設(shè)計1分治法解決合并排序問題及動態(tài)規(guī)劃解決分治法解決合并排序問題及動態(tài)規(guī)劃解決矩陣連乘和最長公共子序列問題及貪心法矩陣連乘和最長公共子序列問題及貪心法解決哈夫曼編碼問題解決哈夫曼編碼問題一、課程設(shè)計目的一、課程設(shè)計目的本次課程設(shè)計可以說是我們學(xué)完《計算機算法設(shè)計與分析》這門課程后的一次綜合性訓(xùn)練。本課程設(shè)計的訓(xùn)練的目的是：1、鞏固和掌握計算機算法設(shè)計和分析課程的基礎(chǔ)知識。2、培養(yǎng)使用計算機基本算法解決實際問題

2、的能力。3、提升使用程序設(shè)計語言對算法程序的開發(fā)、調(diào)試和測試能力。4、對一定的實際問題，能夠設(shè)計求解算法并分析算法的效率。5、提高綜合運用算法、程序設(shè)計語言等能力。6、掌握文檔的書寫能力。二、課程設(shè)計內(nèi)容二、課程設(shè)計內(nèi)容1、分治法（1）合并排序2、動態(tài)規(guī)劃（1）矩陣連乘（2）最長公共子序列3、貪心法（1）哈夫曼編碼三、概要設(shè)計三、概要設(shè)計1、分治法基本思想:《計算機算法設(shè)計與分析》課程設(shè)計3設(shè)A[1:n]=A1…An，最優(yōu)計算次序在Ak

3、和A(k1)間斷開，則總計算量=A[1:k]的計算量A[k1:n]的計算量A[1:k]A[k1:n]則矩陣子鏈A[1:k]和A[k1:n]的計算次序也必最優(yōu)。[遞推關(guān)系]設(shè)計算A[i:j]=Ai…Aj所需最少次數(shù)乘法為m[i][j]，Ai的維數(shù)設(shè)為matrix[i].rowmatrix[i].col。???????????????jijijimjkicolmatrix[j].colmatrix[k].rowmatrix[i].1][j]

4、m[km[i][k]min0]][[[構(gòu)造最優(yōu)解]記m[i][j]的斷開位置k為s[i][j]在計算出m[i][j]后可由s[i][j]遞歸構(gòu)造相應(yīng)的最優(yōu)解。（2）最長公共子序列[問題描述]字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列x=“x0，x1，…，x(m1)”，序列y=“y0，y1，…，y(k1)”是x的子序列，存在x的一個嚴格遞增下標序列，使得對

5、所有的j=0，1，…，k1，有xij=yj。[算法思路]引進一個二維數(shù)組c[][]，用c[i][j]記錄x[i]與y[j]的LCS的長度，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的，以決定搜索的方向。由自底向上進行遞推計算，那么在計算c[ij]之前c[i1][j1]，c[i1][j]與c[i][j1]均已計算出來。此時我們根據(jù)x[i]=y[j]還是x[i]!=y[j]，就可以計算出c[i][j]。問題的遞歸式寫成：ji