C语言矩阵连乘 (动态规划)详解

2024-02-08 07:31:33

动态规划法

题目描述：给定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;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

矩阵的行主序与列主序的分析

1.矩阵在内存中的存储不管是D3D还是OpenGL,使用的矩阵都是线性代数标准的矩阵,只是在存储方式上有所不同.分别为:行主序(Direct3D),列主序(OpenGL) 存储顺序说明了线性代数中的矩阵如何在线性的内存数组中存储. 例如:内存中使用一个二维数组m存储矩阵,第i行第j列的表示方法分别为: 行主序:m[i][j] 列主序:m[j][i] 线性代数意义的同一个矩阵,在d3d 和 openGL 中的存储顺序线代:a11,a12,a13,a14
C语言实现矩阵翻转(上下翻转、左右翻转)

C语言实现矩阵翻转上下翻转与左右翻转实例代码: #include <stdio.h> void matrix (int m, int n, int t) { int arr[m][n]; int i, j, k; for (i = 0; i < m; i++){ for (j = 0; j < n; j++){ scanf("%d", &arr[i][j]); } } if (t == 0){//左右翻转 for (i = 0; i < m;
C++中实现矩阵的加法和乘法实例

C++中实现矩阵的加法和乘法实例实现效果图: 实例代码: #include<iostream> using namespace std; class Matrix { int row;//矩阵的行 int col;//矩阵的列 int **a;//保存二维数组的元素 public: Matrix();//默认构造函数 Matrix(int r, int c); Matrix(const Matrix &is);//拷贝构造函数 void Madd(const Matrix &
C++实现稀疏矩阵的压缩存储实例

什么是稀疏矩阵呢,就是在M*N的矩阵中,有效值的个数远小于无效值的个数,并且这些数据的分布没有规律.在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据.我们在这里使用三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后次序依次存放.下面我们来看一下代码实现. #include<iostream> #include<vector> #include<assert.h> using namespace std; template<class T> c
PHP使用数组实现矩阵数学运算的方法示例

本文实例讲述了PHP使用数组实现矩阵数学运算的方法.分享给大家供大家参考,具体如下: 矩阵运算就是对两个数据表进行某种数学运算,并得到另一个数据表. 下面的例子中我们创建了一个基本完整的矩阵运算函数库,以便用于矩阵操作的程序中. 来自 PHP5 in Practice (U.S.)Elliott III & Jonathan D.Eisenhamer <?php // A Library of Matrix Math functions. // All assume a Matrix de
C语言实现稀疏矩阵

本文实例为大家分享了C语言实现稀疏矩阵的具体代码,供大家参考,具体内容如下 #include "stdio.h" #define maxsize 10 typedef struct { int i,j; //非零元素的行.列 int v; //非零元素的值 }Triple; typedef struct { Triple data[maxsize]; int m,n; //矩阵的行.列 }TSMarix; InitTriple(TSMarix *M) { int i,j,k,v,t;
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数组存放矩阵链计算的最优值,
C语言指针与数组的详解及区别

C语言指针与数组的详解及对比通俗理解数组指针和指针数组数组指针: eg:int( *arr)[10]; 数组指针通俗理解就是这个数组作为指针,指向某一个变量. 指针数组: eg:int*arr[10]; 指针数组简言之就是存放指针的数组: --数组并非指针&&指针并非数组 (1)定义一个外部变量: eg:int value=10; int *p=&value; 举例:当需要在一个函数中用这个变量时:externa int*p;而非extern int p[]; 分析:当用:e
C语言动态内存分配的详解

C语言动态内存分配的详解 1.为什么使用动态内存分配数组在使用的时候可能造成内存浪费,使用动态内存分配可以解决这个问题. 2. malloc和free C函数库提供了两个函数,malloc和free,分别用于执行动态内存分配和释放. (1)void *malloc(size_t size); malloc的参数就是需要分配的内存字节数.malloc分配一块连续的内存.如果操作系统无法向malloc提供更多的内存,malloc就返回一个NULL指针. (2)void free(void *poi
C语言memset函数使用方法详解

C语言memset函数使用方法详解一.函数原形 void * memset(void*s, int ch,size_t n) 二.函数作用将以s内存地址为首的连续n个字节的内容置成ch,一般用来对大量结构体和数组进行清零三.常见错误 1.搞反了 ch 和 n的位置对char[20]清零,一定是 memset(a,0,20); 2.过度使用memset 3.其实这个错误严格来讲不能算用错memset,但是它经常在使用memset的场合出现 int fun(strucy someth
C/C++语言宏定义使用实例详解

C/C++语言宏定义使用实例详解 1. #ifndef 防止头文件重定义在一个大的软件工程里面,可能会有多个文件同时包含一个头文件,当这些文件编译链接成一个可执行文件时,就会出现大量"重定义"的错误.在头文件中实用#ifndef #define #endif能避免头文件的重定义. 方法:例如要编写头文件test.h 在头文件开头写上两行: #ifndef TEST_H #define TEST_H //一般是文件名的大写头文件结尾写上一行: #endif 这样一个工程文件里同时
Java语言实现数据结构栈代码详解

近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是
易语言的输入字类型详解

在程序中书写输入字时,可以使用一个半角符号来引导该输入字,以指定其类型.各输入字的类型引导符号为: 首拼及全拼输入字: 分号(";") 如: ;qz(1.23) 或 ;quzheng(1.23) 双拼输入字: 冒号(":") 如: :quvg(1.23) 英文输入字: 单引号(" '") 如: 'int(1.23) 系统具有一个当前默认输入法状态,如果某输入字前没有加上类型引导符号,则默认是属于该输入法的输入字.系统安装完毕后,当前默认输入法为&
易语言操作数据库“取错误信息”命令详解

如果执行某数据库命令失败,在其后执行本命令可以取回错误信息文本.如果该数据库命令执行成功,执行本命令将返回空文本. 语法: 文本型取错误信息 () 例程: 说明: 首先把要操作的数据库打开,然后执行"写()"命令,程序将改写"改写字段编辑框"中输入的字段名,改写内容为"改写内容编辑框"的内容.如果改写成功,会弹出信息框显示"写入数据成功":如果改写失败,会弹出信息框提示失败,将本次操作的错误码和错误信息取出,并显示在信息框中
易语言“是否支持多用户”命令详解

检查本支持库所提供的数据库功能是否支持多用户同时对数据库操作.如果支持,返回真,否则返回假. 语法: 逻辑型是否支持多用户 () 例程: 说明: 是否支持多用户命令,是检查当前的数据库,是否支持多用户同时进行操作,在检查数据库前,要先把待检查的数据库打开,如果本数据库支持多用户则返回真,否则,返回假. 用存放返回值的变量存放是否支持多用户命令的返回值,最后,用信息框查看本命令的返回值.如果此数据库支持多用户,信息框会显示"真",否则,显示"假". 到此这篇关于易语
易语言操作数据库“替换打开”命令详解

打开指定的数据库文件.成功返回真,并自动关闭当前数据库后将当前数据库设置为此数据库,失败返回假. 语法: 逻辑型替换打开 (数据库文件名,［在程序中使用的别名］,［是否只读］,［共享方式］,［保留参数1］,［数据库密码］,［索引文件表］,- ) 参数名描述数据库文件名必需的:文本型. 在程序中使用的别名可选的:文本型.别名为在后面的程序中引用本数据库时可使用的另一个名称.欲引用一个已经被打开的数据库可以使用该数据库本身的名称(数据库名称为数据库文件名的无路径和后缀部分.譬如 c:\m

C语言矩阵连乘 (动态规划)详解

相关推荐

随机推荐