您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C語言如何實(shí)現(xiàn)矩陣連乘”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C語言如何實(shí)現(xiàn)矩陣連乘”吧!
動(dòng)態(tài)規(guī)劃法
題目描述:給定n個(gè)矩陣{A1,A2....An},其中Ai與Ai+1是可以相乘的,判斷這n個(gè)矩陣通過加括號的方式相乘,使得相乘的次數(shù)最少!
以矩陣鏈ABCD為例
按照矩陣鏈長度遞增計(jì)算最優(yōu)值
矩陣鏈長度為1時(shí),分別計(jì)算出矩陣鏈A、B、C、D的最優(yōu)值
矩陣鏈長度為2時(shí),分別計(jì)算出矩陣鏈AB、BC、CD的最優(yōu)值
矩陣鏈長度為3時(shí),分別計(jì)算出矩陣鏈ABC、BCD的最優(yōu)值
矩陣鏈長度為4時(shí),計(jì)算出矩陣鏈ABCD的最優(yōu)值
動(dòng)歸方程:
分析:
k為矩陣鏈斷開的位置
d數(shù)組存放矩陣鏈計(jì)算的最優(yōu)值,d[i][j]是以第i個(gè)矩陣為首,第j個(gè)矩陣為尾的矩陣鏈的最優(yōu)值,i > 0
m數(shù)組內(nèi)存放矩陣鏈的行列信息,m[i-1]和m[i]分別為第i個(gè)矩陣的行和列(i = 1、2、3...)
c語言實(shí)現(xiàn)代碼:
#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; //記錄相乘的矩陣個(gè)數(shù)變量 for(i=1;i<=n;i++){ m[i][i]=0; //當(dāng)一個(gè)矩陣相乘時(shí),相乘次數(shù)為 0 } //矩陣個(gè)數(shù)從兩個(gè)開始一次遞增 for(r=2;r<=n;r++){ //從某個(gè)矩陣開始 for(i=1;i<=n-r+1;i++){ //到某個(gè)矩陣的結(jié)束 j=i+r-1; //拿到從 i 到 j 矩陣連乘的次數(shù) m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; //拿到矩陣連乘斷開的位置 s[i][j]=i; //尋找加括號不同,矩陣連乘次數(shù)的最小值,修改 m 數(shù)組,和斷開的位置 s 數(shù)組 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}; //存儲矩陣的行和列數(shù)組 int m[N][N]={0}; //存儲矩陣與矩陣相乘的最小次數(shù) int s[N][N]={0}; //存儲矩陣與矩陣相乘斷開的位置 printf("請輸入矩陣個(gè)數(shù):\n"); scanf("%d",&n); for(i=1;i<=n;i++){ printf("請輸入第%d個(gè)矩陣的行和列(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矩陣相乘的最小次數(shù)矩陣為:\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("矩陣最小相乘次數(shù)為:%d\n",m[1][n]); return 0; }
到此,相信大家對“C語言如何實(shí)現(xiàn)矩陣連乘”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。