動(dòng)態(tài)規(guī)劃矩陣連乘算法-文庫吧資料
2025-07-28 00:49本頁面
【正文】 in(i+1,j,m,s,p)+p[i1]*p[i]*p[j]。}int LookupChain(int i,int j,int **m,int **s,int *p){ if(m[i][j]0) { return m[i][j]。 j++) { m[i][j]=0。 i++) { for(int j=1。}int MemoizedMatrixChain(int n,int **m,int **s,int *p){ for(int i=1。 Traceback(1,6,s)。 } cout矩陣的最少計(jì)算次數(shù)為：MemoizedMatrixChain(6,m,s,p)endl。i++) { s[i] = new int[L]。 for(int i=0。 int **s = new int *[L]。void Traceback(int i,int j,int **s)。int LookupChain(int i,int j,int **m,int **s,int *p)。//3d12 矩陣連乘 備忘錄遞歸實(shí)現(xiàn)//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25//p[06]={30,35,15,5,10,20,25}include include iostream using namespace std。若記錄項(xiàng)中存儲(chǔ)的已不是初始化時(shí)存入的特殊值，則表示該子問題已被計(jì)算過，相應(yīng)的記錄項(xiàng)中存儲(chǔ)的是該子問題的解答。在求解的過程中，對(duì)每個(gè)帶求的子問題，首先查看其相應(yīng)的記錄項(xiàng)。備忘錄方法用表格保存已解決的子問題答案，在下次需要解決此子問題時(shí)，只要簡單查看該子問題的解答，而不必重新計(jì)算。 7. 設(shè)算法中判斷語句和賦值語句為常數(shù)時(shí)間，則由算法的遞歸部分可得關(guān)于T(n)的遞歸不等式：5.6. 從上圖可以看出很多子問題被重復(fù)運(yùn)算。 cout and A(s[i][j]+1),jendl。 Traceback(s[i][j]+1,j,s)。}void Traceback(int i,int j,int **s){ if(i==j) return。 s[i][j]=k。 k++) { int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i1]*p[k]*p[j]。 for(int k=i+1。 int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i1]*p[i]*p[j]。 return 0。 cout矩陣最優(yōu)計(jì)算次序?yàn)椋篹ndl。i++) { s[i] = new int[L]。 for(int i=0。//構(gòu)造最優(yōu)解int main(){ int p[L]={30,35,15,5,10,20,25}。int RecurMatrixChai
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1