矩阵连乘

今天药忘吃喽~ 2022-07-15 07:56 207阅读 0赞

# 递归： #

#include<stdio.h>
    #define N 6
    int m[N][N]; //最小乘法次数
    int RecurMatrixChain(int P[],int i,int j) {
    	m[i][j]= 100000;
    	if(i== j)
    		m[i][j]=0;
    	else {
    		for(int k=i; k<j; k++) {
    			int q=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+P[i]*P[k+1]*P[j+1];
    			if(q<m[i][j]) {
    				m[i][j]=q;
    			}
    		}
    	}
    	return m[i][j];
    }
    int main() {
    	int P[N+1]= {30,35,15,5,10,20,25};
    	for(int i=0; i<N; i++)
    		m[i][i]=0;
    	printf("%d",RecurMatrixChain(P,0,N-1));
    	return 0;
    }

# 动态规划： #

#include <stdio.h>
    #define N 6
    int m[6][6];//最优解
    void matrix(int p[]) {
    	int i;
    	int j;
    	for(i=2; i<=6; i++)
    		for(j=0; j<6-i+1; j++) {
    			m[j][j+i-1]=1000000;
    			int k;
    			for(k=0; k<i-1; k++) {
    				if(m[j][j+i-1]>m[j][j+k]+m[j+k+1][j+i-1]+p[j]*p[j+k+1]*p[j+i])
    				 {
    					m[j][j+i-1]=m[j][j+k]+m[j+k+1][j+i-1]+p[j]*p[j+k+1]*p[j+i];
    				}
    			}
    		}
    }
    int main() {
    	int p[7]= {30,35,15,5,10,20,25};
    	for(int i=0; i<6; i++)
    		m[i][i]=0;
    	matrix(p);
    	printf("%d\n",m[0][5]);
    	return 0;
    }

# 备忘录： #

#include <stdio.h>
    #define N 6
    int m[N][N],s[N][N];//最优解
    int p[7]= {30,35,15,5,10,20,25};
    int lookupChain(int i, int j) {
    	if(m[i][j]>0) return m[i][j];
    	if(i==j) return 0;
    	int u=lookupChain(i+1, j) + p[i-1]*p[i]*p[j];
    	s[i][j] = i;
    	for(int k=i+1; k<j; k++) {
    		int t = lookupChain(i,k) + lookupChain(k+1, j) + p[i-1]*p[k]*p[j];
    		if(t<u) {
    			u=t;
    			s[i][j] = k;
    		}
    	}
    	m[i][j] = u;
    	return u;
    }
    int memoizedmatrixChain(int n) {
    	for(int i=1; i<=n; i++)
    		for(int j=i; j<=n; j++)
    			m[i][j] = 0;
    	return lookupChain(1, n);
    }
    int main() {
    	for(int i=0; i<6; i++)
    		m[i][i]=0;
    	printf("%d\n",memoizedmatrixChain(N));
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，207人围观）

还没有评论，来说两句吧...

相关阅读

相关矩阵连乘问题

文章目录算法思想状态转移方程算法代码 -------------------- 算法思想从小到大找不同的连乘矩阵的分割点，将所有分割点

超、凢脫俗/ 2022年12月28日 14:17/ 0 赞/ 186 阅读

相关 1020 矩阵连乘

Description 两个矩阵A(r行s列)和B(s行t列)相乘, 乘法代价为rst. 现给定N(N<=500)个矩阵连乘问题, 请计算最小乘法代价。 Input

待我称王封你为后i/ 2022年09月12日 00:56/ 0 赞/ 168 阅读

相关动态规划-矩阵连乘

特征：计算A\[i:j\]的最优次序所包含的计算矩阵子链 A\[i:k\]和A\[k+1:j\]的次序也是最优的。 ![20140304203120937][] 如计

缺乏、安全感/ 2022年08月25日 11:52/ 0 赞/ 167 阅读

相关矩阵连乘问题

问题描述：给定一组可以连乘的矩阵，求最佳相乘顺序，使得总的计算次数最少。参考代码：方法一：动态规划 include <stdio.h>

矫情吗；*/ 2022年08月02日 07:19/ 0 赞/ 186 阅读

相关矩阵连乘

递归： include<stdio.h> define N 6 int m[N][N]; //最小乘法次数 int RecurMatrix

今天药忘吃喽~/ 2022年07月15日 07:56/ 0 赞/ 208 阅读

相关 fibonacci扩展+矩阵连乘

dhu1757 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1757][http_acm.hdu.edu.cn_showpr

秒速五厘米/ 2022年06月17日 09:37/ 0 赞/ 193 阅读

相关构造矩阵+矩阵连乘+fibonacci

hdu1021 链接：[点击打开链接][Link 1] 题目解析：ACMer都喜欢一题多解，这样会使自己的境界不一样！方法一：找规律；小乔出嫁了—周期；循环节。

我会带着你远行/ 2022年06月17日 06:49/ 0 赞/ 229 阅读

相关矩阵连乘（动态规划）

题目描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数

系统管理员/ 2022年06月05日 07:51/ 0 赞/ 214 阅读

相关矩阵连乘问题

<table style="max-width:100%;border-spacing:0px;width:1650px;margin-bottom:20px;backgrou

矫情吗；*/ 2022年05月29日 13:46/ 0 赞/ 191 阅读

相关矩阵连乘动态规划

　　题目描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘

布满荆棘的人生/ 2021年11月29日 17:56/ 0 赞/ 290 阅读