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

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

2、8、討論（對實驗中存在的問題、進一步的想法等進行討論）一、實驗目的通過對最長公共子序列的編程實現(xiàn)，增強對動態(tài)規(guī)劃方法的了解。二、實驗內(nèi)容編程用動態(tài)規(guī)劃的自底向上的方法求解兩個序列的最長公共子序列問題（要求粘貼代碼和實驗結(jié)果截圖）。三、實驗步驟和過程在最優(yōu)化問題的求解過程中，通常會出現(xiàn)大量重復計算問題，當遇到此類問題的時候，如果我們又可以容易的找到它的最優(yōu)子結(jié)構(gòu)，那么就可以嘗試使用動態(tài)規(guī)劃方法求解，動態(tài)規(guī)劃方法中可以使用自底向上法和自頂向下記錄法兩種方法來減少重復的運算量，從而達到提高運算效率的目的。實驗代碼：#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.每個實驗項目一份實驗報告。2.實驗報告第一頁學生必須使用規(guī)定的實驗報告紙書寫，附頁用實驗報告附頁紙或A4