3尋找最長(zhǎng)公共子序列(動(dòng)態(tài)規(guī)劃)

1、 天津商業(yè)大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告 開(kāi)課實(shí)驗(yàn)室： 403 機(jī)房 開(kāi)課時(shí)間 2015年 3 月 1日 實(shí)驗(yàn)報(bào)告 2015年 6月 1 日 學(xué)院名稱(chēng)信息工程學(xué)院年級(jí)、專(zhuān)業(yè)、班計(jì)科1303班學(xué)號(hào)20134390姓名吳雪婷同組姓名 無(wú)課程名稱(chēng)算法分析與設(shè)計(jì)實(shí)驗(yàn)項(xiàng)目名稱(chēng)尋找最長(zhǎng)公共子序列（動(dòng)態(tài)規(guī)劃）指導(dǎo)教師楊亮實(shí)驗(yàn)類(lèi)型 驗(yàn)證 綜合 設(shè)計(jì) 創(chuàng)新成績(jī)實(shí)驗(yàn)報(bào)告內(nèi)容一般包括以下幾個(gè)內(nèi)容：1、目的要求 2、儀器用具及材料（儀器名稱(chēng)及主要規(guī)格、用具名稱(chēng)） 3、實(shí)驗(yàn)內(nèi)容及原理（簡(jiǎn)單但要抓住要點(diǎn)，寫(xiě)出依據(jù)原理） 4、操作方法與實(shí)驗(yàn)步驟 5、數(shù)據(jù)圖表格（照片） 6、實(shí)驗(yàn)過(guò)程原始記錄 7數(shù)據(jù)處理及結(jié)果（按實(shí)驗(yàn)要求處理數(shù)據(jù)、結(jié)論）

2、8、討論（對(duì)實(shí)驗(yàn)中存在的問(wèn)題、進(jìn)一步的想法等進(jìn)行討論）一、實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)對(duì)最長(zhǎng)公共子序列的編程實(shí)現(xiàn)，增強(qiáng)對(duì)動(dòng)態(tài)規(guī)劃方法的了解。二、實(shí)驗(yàn)內(nèi)容編程用動(dòng)態(tài)規(guī)劃的自底向上的方法求解兩個(gè)序列的最長(zhǎng)公共子序列問(wèn)題（要求粘貼代碼和實(shí)驗(yàn)結(jié)果截圖）。三、實(shí)驗(yàn)步驟和過(guò)程在最優(yōu)化問(wèn)題的求解過(guò)程中，通常會(huì)出現(xiàn)大量重復(fù)計(jì)算問(wèn)題，當(dāng)遇到此類(lèi)問(wèn)題的時(shí)候，如果我們又可以容易的找到它的最優(yōu)子結(jié)構(gòu)，那么就可以嘗試使用動(dòng)態(tài)規(guī)劃方法求解，動(dòng)態(tài)規(guī)劃方法中可以使用自底向上法和自頂向下記錄法兩種方法來(lái)減少重復(fù)的運(yùn)算量，從而達(dá)到提高運(yùn)算效率的目的。實(shí)驗(yàn)代碼：#include <stdio.h>#define SIZE 5int p

3、SIZE+1 =20,100,5,30,500,1000;int dataSIZESIZE;int dirSIZESIZE;void multiple();int main(int argc,char* argv)multiple();printf("The minimiu eperation is %dn",data0SIZE-1);printf("Hello World!n");return 0;void multiple()int i,j,k,q,r,minm,index,temp;for(i=0;i<SIZE;i+) dataii = 0;

4、for(j=1;j<SIZE;j+)for(k=0;k<SIZE-j;k+)q = k + j; minm=10000000000;index = 0; for(r=k;r<q;r+)temp = datakr + datar+1q + pk*pr+1*pq+1;if(temp< minm)minm =temp;index =r; datakq = minm;dirkq = index;printf("The %d iteration n",j);for (i=0;i<SIZE;i+)for(k=0;k<SIZE;k+)printf(" %5d ",dataik);printf("n");printf("The direction matrix is n",j);for (i=0;i<SIZE;i+)for(k=0;k<SIZE;k+)printf(" %5d ",dirik);printf("n");注1.每個(gè)實(shí)驗(yàn)項(xiàng)目一份實(shí)驗(yàn)報(bào)告。2.實(shí)驗(yàn)報(bào)告第一頁(yè)學(xué)生必須使用規(guī)定的實(shí)驗(yàn)報(bào)告紙書(shū)寫(xiě)，附頁(yè)用實(shí)驗(yàn)報(bào)告附頁(yè)紙或A4