數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--最小生成樹(參考版)
2025-01-19 16:10本頁面
【正文】 參考文獻【1】 《算法設(shè)計與分析》 王曉東編著 電子工業(yè)出版社。}結(jié)果分析： 通過代碼和運行結(jié)果，我們能夠看到，首先對二個序列進行動態(tài)分配，將長度較小的字符串作為第一參數(shù)，將長度較大的字符串作為第二個參數(shù)。 ()。}void Display(){LCS(m,n,x,b)。 } else if(b[i][j]==2)LCS(i1,j,x,b)。 if(b[i][j]==1) { LCS(i1,j1,x,b)。 b[i][j]=3。 b[i][j]=2。 b[i][j]=1。j=n。i=m。i++)c[0][i]=0。 for(i=1。i=m。 }}void LCSLength(int m,int n,string x,string y,int **c,int**b){ int i,j。 Realese()。 LCSLength(m,n,x,y,c,b)。C39。c39。}void Interpret(char amp。 } delete[] c。i++) { delete c[i]。 } }void Realese()//釋放指針board{ for(int i=0。i++) { c[i]=new int[n+1]。 for(int i=0。 c=new int*[m+1]。m=()。 cinx。)。cmd!=39。amp。cmd!=39。amp。cmd!=39。amp。 }while(cmd!=39。 cincmd。 cout\tquitq/Q \t\t continuec/C\n。 cout\n\t\t\t\t操 作 提 示。cmd){ system(cls)。 return 0。Q39。amp。q39。 Interpret(cmd)。int main(){ char cmd。void Realese()。void Interpret(char amp。//對數(shù)組b,c動態(tài)分配空間以及對其進行初始化void ReadCommand(char amp。void LCS(int i,int j,string x,int **b)。//x,y用來存放字符序列int **c,**b,m,n。代碼如下：includeiostreamincludestringusing namespace std。調(diào)用函數(shù)ReadCommand進行系統(tǒng)操作屏幕指示，然后利用函數(shù)void Interpret（charamp。調(diào)用函數(shù)void LCSLength（int m,int n,string x,string y,int**c,int**b），將長度較小的字符串作為第一參數(shù)，將長度較大的字符串作為第二個參數(shù)。故此時C[i][j]=0。其中，={, ,…,} ={ , ,…, }。算法設(shè)計：由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。我們可以用一個表來記錄所有已解的子問題的答案。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。在這類問題中，可能會有許多可行解。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。(2)若且，則Z是和Y的最長公共子序列。請使用C語言編程，設(shè)計一個有效的算法解決下述問題：給定2個序列X={, ,…,}，和Y={ , ,…,}，找出X和Y的最長公共子序列。例如，序列={B，C，D，B}是序列={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標序列為{2，3，5，7}。并且可以看到a到b的路徑不是唯一的，及最優(yōu)解不是唯一的。}運行結(jié)果與分析： 根據(jù)運行的結(jié)果我們看到，首先要給布線區(qū)域加一道“圍墻”，從開始點進行標記。 out_path()。 output()。 return。i++) { printf((%d,%d) ,p
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1