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

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

2、的能力。3、提升使用程序設計語言對算法程序的開發(fā)、調試和測試能力。4、對一定的實際問題，能夠設計求解算法并分析算法的效率。5、提高綜合運用算法、程序設計語言等能力。6、掌握文檔的書寫能力。二、課程設計內容二、課程設計內容1、分治法（1）合并排序2、動態(tài)規(guī)劃（1）矩陣連乘（2）最長公共子序列3、貪心法（1）哈夫曼編碼三、概要設計三、概要設計1、分治法基本思想:《計算機算法設計與分析》課程設計3設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)。[遞推關系]設計算A[i:j]=Ai…Aj所需最少次數乘法為m[i][j]，Ai的維數設為matrix[i].rowmatrix[i].col。???????????????jijijimjkicolmatrix[j].colmatrix[k].rowmatrix[i].1][j]

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

5、所有的j=0，1，…，k1，有xij=yj。[算法思路]引進一個二維數組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]均已計算出來。此時我們根據x[i]=y[j]還是x[i]!=y[j]，就可以計算出c[i][j]。問題的遞歸式寫成：ji