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

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

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

3、和A(k1)間斷開，則總計(jì)算量=A[1:k]的計(jì)算量A[k1:n]的計(jì)算量A[1:k]A[k1:n]則矩陣子鏈A[1:k]和A[k1:n]的計(jì)算次序也必最優(yōu)。[遞推關(guān)系]設(shè)計(jì)算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]在計(jì)算出m[i][j]后可由s[i][j]遞歸構(gòu)造相應(yīng)的最優(yōu)解。（2）最長(zhǎng)公共子序列[問題描述]字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列x=“x0，x1，…，x(m1)”，序列y=“y0，y1，…，y(k1)”是x的子序列，存在x的一個(gè)嚴(yán)格遞增下標(biāo)序列，使得對(duì)

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