算法 矩陣連乘_第1頁
算法 矩陣連乘_第2頁
算法 矩陣連乘_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

矩陣連乘1題目分析將矩陣連乘積簡記為A[i:j]，這里i≤j計算A[i:j]的最優次序所包含的計算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優的。該問題可用動態規劃算法求解算法構造設計算A[i:j]，1≤i≤j≤n，所需要的最少數乘次數m[i,j]，則原問題的最優值為m[1,n]當i=j時，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當i<j時，可以遞歸地定義m[i,j]為：2算法實現#include<iostream>usingnamespacestd;//計算最優值voidMatrixChain(int*p,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++){for(i=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//選取最優for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//記錄最優斷開位置if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}}//構造最優解---按順序由內而外voidTraceback(inti,intj,int**s){if(i==j){return;}Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<"MultiplyA"<<i<<","<<s[i][j];cout<<"andA"<<(s[i][j]+1)<<","<<j<<endl;}//主函數intmain(){inti;intn;//參與連乘的矩陣個數int*p;//矩陣Ai的列數或Ai-1的行數int**m;//紀錄Ai-Aj的矩陣連乘的最小代價int**s;//紀錄Ai-Aj之間得到最小連乘代價時的分割點cout<<"輸入矩陣的個數："<<endl<<endl;cin>>n;p=newint[n+1];cout<<endl<<"請分別輸入每一個矩陣的行列數："<<endl<<endl;for(i=0;i<=n;i++){cin>>p[i];}m=newint*[n+1];//分配空間for(i=0;i<=n;i++){m[i]=newint[n+1];}s=newint*[n+1];//分配空間for(i=0;i<=n;i++){s[i]=newint[n+1];}cout<<endl<<"計算順序如下所示："<<endl<<endl;MatrixChain(p,n,m,s);Traceback(1,n,s);}3運行結果輸入矩陣的個數：6請分別輸入每一個矩陣的行列數：3035155102025計算順序如下所示：MultiplyA2,2andA3,3MultiplyA1,1and

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論