C語言矩陣連乘 (動態規劃)詳解。本站提示廣大學習愛好者:(C語言矩陣連乘 (動態規劃)詳解)文章只能為提供參考,不一定能成為您想要的結果。以下是C語言矩陣連乘 (動態規劃)詳解正文
投稿:lqh
這篇文章主要介紹了C語言矩陣連乘 (動態規劃)詳解的相關資料,需要的朋友可以參考下動態規劃法
題目描述:給定n個矩陣{A1,A2....An},其中Ai與Ai+1是可以相乘的,判斷這n個矩陣通過加括號的方式相乘,使得相乘的次數最少!
以矩陣鏈ABCD為例
按照矩陣鏈長度遞增計算最優值
矩陣鏈長度為1時,分別計算出矩陣鏈A、B、C、D的最優值
矩陣鏈長度為2時,分別計算出矩陣鏈AB、BC、CD的最優值
矩陣鏈長度為3時,分別計算出矩陣鏈ABC、BCD的最優值
矩陣鏈長度為4時,計算出矩陣鏈ABCD的最優值
動歸方程:
分析:
k為矩陣鏈斷開的位置
d數組存放矩陣鏈計算的最優值,d[i][j]是以第i個矩陣為首,第j個矩陣為尾的矩陣鏈的最優值,i > 0
m數組內存放矩陣鏈的行列信息,m[i-1]和m[i]分別為第i個矩陣的行和列(i = 1、2、3...)
c語言實現代碼:
#include <stdio.h> #define N 20 void MatrixChain(int p[N],int n,int m[N][N],int s[N][N]){ int i,j,t,k; int r; //記錄相乘的矩陣個數變量 for(i=1;i<=n;i++){ m[i][i]=0; //當一個矩陣相乘時,相乘次數為 0 } //矩陣個數從兩個開始一次遞增 for(r=2;r<=n;r++){ //從某個矩陣開始 for(i=1;i<=n-r+1;i++){ //到某個矩陣的結束 j=i+r-1; //拿到從 i 到 j 矩陣連乘的次數 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; //拿到矩陣連乘斷開的位置 s[i][j]=i; //尋找加括號不同,矩陣連乘次數的最小值,修改 m 數組,和斷開的位置 s 數組 for(k=i+1;k<j;k++){ t=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; } } } } } int main(void){ int n,n1,m1,i,j=2; int p[N]={0}; //存儲矩陣的行和列數組 int m[N][N]={0}; //存儲矩陣與矩陣相乘的最小次數 int s[N][N]={0}; //存儲矩陣與矩陣相乘斷開的位置 printf("請輸入矩陣個數:\n"); scanf("%d",&n); for(i=1;i<=n;i++){ printf("請輸入第%d個矩陣的行和列(n1*m1 格式):",i); scanf("%d*%d",&n1,&m1); if(i==1){ p[0]=n1; p[1]=m1; } else{ p[j++]=m1; } } printf("\n記錄矩陣行和列:\n"); for(i=0;i<=n;i++){ printf("%d ",p[i]); } printf("\n"); MatrixChain(p,n,m,s); printf("\n矩陣相乘的最小次數矩陣為:\n"); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d ",m[i][j]); } printf("\n"); } printf("\n矩陣相乘斷開的位置矩陣為:\n"); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d ",s[i][j]); } printf("\n"); } printf("矩陣最小相乘次數為:%d\n",m[1][n]); return 0; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!