实现稀疏矩阵(采用三元组表示)的基本运算实验报告
实现稀疏矩阵（采用三元组表示）的基本运算实验报告
一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求:
（1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组；
（3）输出a + b 的三元组；
（4）输出 a * b 的三元组；
三实验内容:
3.1 稀疏矩阵的抽象数据类型:
ADT SparseMatrix {
数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n;
ai,j∈ElemSet,m和n分别称为矩阵的行数和列数 } 数据关系 : R={ Row , Col }
Row ={
Col ={| 1≤i≤m-1,1≤j≤n}
基本操作:
CreateSMatrix(&M)
操作结果：创建稀疏矩阵M
PrintSMatrix(M)
初始条件：稀疏矩阵M已经存在
操作结果：打印矩阵M
DestroySMatrix(&M)
初始条件：稀疏矩阵M已经存在
操作结果：销毁矩阵M
CopySMatrix(M, &T)
初始条件：稀疏矩阵M已经存在
操作结果：复制矩阵M到T
AddSMatrix(M, N, &Q)
初始条件：稀疏矩阵M、N已经存在
操作结果：求矩阵的和Q=M+N
SubSMatrix(M, N, &Q)
初始条件：稀疏矩阵M、N已经存在
操作结果：求矩阵的差Q=M-N
TransposeSMatrix(M, & T)
初始条件：稀疏矩阵M已经存在
操作结果：求矩阵M的转置T
MultSMatrix(M, N, &Q)
初始条件：稀疏矩阵M已经存在
操作结果：求矩阵的积Q=M*N
}ADT SparseMatrix
3.2存储结构的定义
#define N 4
typedef int ElemType;
#define MaxSize 100 //矩阵中非零元素最多个数typedef struct
{ int r; //行号
int c; //列号
ElemType d; //元素值
} TupNode; //三元组定义
typedef struct
{ int rows; //行数值
int cols; //列数值
int nums; //非零元素个数
TupNode data[MaxSize];
} TSMatrix; //三元组顺序表定义
3.3基本操作实现:
void CreatMat(TSMatrix &t,ElemType A[N][N])
{
int i,j;
t.rows=N;t.cols=N;t.nums=0;
for (i=0;i { for (j=0;j if (A[i][j]!=0) { t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } } } void DispMat(TSMatrix t) { int i; if (t.nums<=0) return; printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums); printf("\t------------------\n"); for (i=0;i printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); } 3.4解题思路： 1.转置矩阵：只要判定原矩阵有值，那么只要遍历一遍原矩阵，把原来矩阵中非0元素行列变换一下赋值到新的矩阵中即可。 2.矩阵加法：用各种 if 判断，区分出矩阵进行加法时的可能情况，分情况处理即可。 3.矩阵乘法：通过 getvalue（c ， i， j）函数查找矩阵c 中i 行j列，所储存的元素的值。然后便是模拟矩阵乘法的过程进行求解。 3.5解题过程： 实验源代码如下： 3.5.1顺序表的各种运算 #include #define N 4 typedef int ElemType; #define MaxSize 100 //矩阵中非零元素最多个数typedef struct { int r; //行号 int c; //列号 ElemType d; //元素值 } TupNode; //三元组定义 typedef struct { int rows; //行数值 int cols; //列数值 int nums; //非零元素个数 TupNode data[MaxSize]; } TSMatrix; //三元组顺序表定义 void CreatMat(TSMatrix &t,ElemType A[N][N]){ int i,j; t.rows=N;t.cols=N;t.nums=0; for (i=0;i { for (j=0;j if (A[i][j]!=0) { t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } } } void DispMat(TSMatrix t){ int i; if (t.nums<=0) return; printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums); printf("\t------------------\n"); for (i=0;i printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d ); } void TranMat(TSMatrix t,TSMatrix &tb){ int p,q=0,v; //q为tb.data的下标 tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums; if (t.nums!=0) { for (v=0;v for (p=0;p if (t.data[p].c==v) { tb.data[q].r=t.data[p].c; tb.data[q].c=t.data[p].r; tb.data[q].d=t.data[p].d; q++; } } } bool MatAdd(TSMatrix a,TSMatrix b,TSMatrix &c){ int i=0,j=0,k=0; ElemType v; if (a.rows!=b.rows || a.cols!=b.cols) return false; //行数或列数不等时不能进行相加运算 c.rows=a.rows;c.cols=a.cols; //c的行列数与a的相同 while (i { if (a.data[i].r==b.data[j].r) //行号相等时 { if(a.data[i].c { c.data[k].r=a.data[i].r;//将a元素添加到c中 c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; } else if (a.data[i].c>b.data[j].c)//a元素的列号大于b 元素的列号 { c.data[k].r=b.data[j].r; //将b元素添加到c中 c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++;j++; } else //a元素的列号等于b元素的列号 { v=a.data[i].d+b.data[j].d; if (v!=0) //只将不为0的结果添加到c中 { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=v; k++; } i++;j++; } } else if (a.data[i].r { c.data[k].r=a.data[i].r; //将a元素添加到c中 c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; } else //a元素的行号大于b元素的行号 { c.data[k].r=b.data[j].r; //将b元素添加到c中 c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++;j++; } c.nums=k; } return true; } int getvalue(TSMatrix c,int i,int j) { int k=0; while (k if (k return(c.data[k].d); else return(0); } bool MatMul(TSMatrix a,TSMatrix b,TSMatrix &c) { int i,j,k,p=0; ElemType s; if (a.cols!=b.rows) //a的列数不等于b的行数时不能进行相乘运算 return false; for (i=0;i for (j=0;j { s=0; for (k=0;k s=s+getvalue(a,i,k)*getvalue(b,k,j); if (s!=0) //产生一个三元组元素 { c.data[p].r=i; c.data[p].c=j; c.data[p].d=s; p++; } } c.rows=a.rows; c.cols=b.cols; c.nums=p; return true; } int main() { ElemType a1[N][N]={ {1,0,3,0}, {0,1,0,0}, {0,0,1,0}, {0,0,1,1}}; ElemType b1[N][N]={ {3,0,0,0}, {0,4,0,0}, {0,0,1,0}, {0,0,0,2}}; TSMatrix a,b,c; CreatMat(a,a1); CreatMat(b,b1); printf("a的三元组:\n");DispMat(a); printf("b的三元组:\n");DispMat(b); printf("a转置为c\n"); TranMat(a,c); printf("c的三元组:\n");DispMat(c); printf("c=a+b\n"); MatAdd(a,b,c); printf("c的三元组:\n");DispMat(c); printf("c=a×b\n"); MatMul(a,b,c); printf("c的三元组:\n");DispMat(c); return 0; } 四实验结果 兰州交通大学 《算法设计与分析》 实验报告3 题目03-动态规划 专业计算机科学与技术 班级计算机科学与技术2016-02班学号201610333 姓名石博洋 第3章动态规划 1. 实验题目与环境 1.1实验题目及要求 (1) 用代码实现矩阵连乘问题。 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。 确定一个计算顺序，使得需要的乘的次数最少。 (2) 用代码实现最长公共子序列问题。 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 。例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 (3) 0-1背包问题。 现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W i，价值为正整数V i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分） 使用动态规划使得装入背包的物品价值之和最大。 1.2实验环境： CPU：Intel(R) Core(TM) i3-2120 3.3GHZ 内存：12GB 操作系统：Windows 7.1 X64 编译环境：Mircosoft Visual C++ 6 2. 问题分析 (1) 分析。 矩 阵 分 析 实 验 报 告 学院：电气学院 专业：控制工程 姓名：XXXXXXXX 学号：211208010001 矩阵分析实验报告 实验题目 利用幂法求矩阵的谱半径 实验目的与要求 1、 熟悉matlab 矩阵实验室的功能和作用； 2、 利用幂法求矩阵的谱半径； 3、 会用matlab 对矩阵分析运算。 实验原理 理念 谱半径定义：设n n A C ?∈，1λ，2λ，3λ， ，j λ， n λ是A 的n 个特征值，称 ()max ||j j A ρλ= 为关于A 的谱半径。 关于矩阵的谱半径有如下结论： 设n n A C ?∈，则 （1）[]()()k k A A ρρ=； （2）2 2()()()H H A A AA A ρρ==。 由于谱半径就是矩阵的主特征值，所以实验换为求矩阵的主特征值。 算法介绍 定义：如果1λ是矩阵A 的特征值，并且其绝对值比A 的任何其他特征值的绝对值大，则称它为主特征值。相应于主特征值的特征向量1V 称为主特征向量。 定义：如果特征向量中最大值的绝对值等于单位值（例如最大绝对值为1），则称其为是归一化的。 通过形成新的向量' 12=c n V （1/）[v v v ]，其中c=v 且1max {},j i n i ≤≤=v v 可将特 征向量 '12n [v v v ]进行归一化。 设矩阵A 有一主特征值λ，而且对应于λ有唯一的归一化特征向量V 。通过下面这个称为幂法（power method ）的迭代过程可求出特征对λ，V ，从下列向量开始： []' 0=111X （1） 用下面递归公式递归地生成序列{}k X ： k k Y AX = k+11 1 k k X Y c += （2） 其中1k c +是k Y 绝对值最大的分量。序列{}k X 和{}k c 将分别收敛到V 和λ： 1lim k X V =和lim k c λ= （3） 注：如果0X 是一个特征向量且0X V ≠，则必须选择其他的初始向量。 幂法定理：设n ×n 矩阵A 有n 个不同的特征值λ1，λ2，···，，λn ，而且它们按绝对 值大小排列，即： 123n λλλλ≥≥≥???≥ (4) 如果选择适当的X 0，则通过下列递推公式可生成序列{[() ()( ) ]}12k k k k n X x x x '=???和 {}k c ： k k Y AX = (5) 和： 11 1k k k X Y c ++= (6) 其中： () 1k k j c x +=且{} ()()1max k k j i i n x x ≤≤= (7) 这两个序列分别收敛到特征向量V 1和特征值λ1。即： 1lim k k X V →∞ =和1lim k k c λ→∞ = (8) 算法收敛性证明 证明：由于A 有n 个特征值，所以有对应的特征向量V j ，j=1，2，···n 。而且它们是 实现稀疏矩阵（采用三元组表示）的基本运算实验报告 一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组； （3）输出a + b 的三元组； （4）输出 a * b 的三元组； 三实验内容: 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系: R={ Row , Col } Row ={ CreateSMatrix(&M) 操作结果：创建稀疏矩阵 M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在 操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在 操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在 操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在 操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在 操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在 操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在 算法设计与分析实验报告 班级：计科0902班 姓名：张华敏 学号：0909090814 矩阵连乘问题 一，实验内容： 二，写一个完整的代码来完整的实现矩阵连乘问题。 三，算法设计： 在矩阵连乘问题中，根据老师所讲和自己看书对动态规划方法的理解，通过最优子结构性质。再结合书上的算法，便可顺利的写出了代码 四，遇到的问题及解决方案： 只根据算法写出具体的实现过程刚开始觉得很难，觉得无从下手，不知道该用什么结构形式来存放各个参数，也不知道该怎样具体的实施算法的细节，但是课本上给出了一段实现代码给了我很大的启发，通过借鉴树上的代码实现再结合自己的努力，才终于完成了矩阵连乘全部的代码实现，包括最少连乘次数以及剖分方法。 五，源代码 package suanfa; public class Juzhen { public void matrixchain(int p[],int m[][],int s[][]){ i nt n=p.length-1; f or(int i=1;i<=n;i++){ m[i][i]=0; } f or(int r=2;r<=n;r++){ for(int i=1;i<=n-r+1;i++){ int j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k 一、课题名称 Malab矩阵特征值 二、目的和意义 1、求矩阵的部分特征值问题具有重要实际意义，如求矩阵谱半径()Aρ=maxλ，稳定性问题往往归于求矩阵按模最小特征值； 2、进一步掌握冪法、反冪法及原点平移加速法的程序设计技巧； 3、问题中的题（5），反应了利用原点平移的反冪法可求矩阵的任何特征值及其特征向量。 三、实验要求 1、掌握冪法或反冪法求矩阵部分特征值的算法与程序设计； 2、会用原点平移法改进算法，加速收敛；对矩阵B=A-PI取不同的P值，试求其效果； 3、试取不同的初始向量，观察对结果的影响；()0υ 4、对矩阵特征值的其它分布，如如何计算。 四、问题描述 五、实验程序设计 幂法 function [lamdba,v]=power_menthod(a,x,epsilon,maxl) k=0; y=a*x; while(k 北京科技大学计算机与通信工程学院 实验报告 实验名称： 学生姓名： 专业： 班级： 学号： 指导教师： 实验成绩：________________________________ 实验地点： 实验时间：2015年05月 一、实验目的与实验要求 1、实验目的 1对比矩阵乘法的串行和并行算法，查看运行时间，得出相应的结论；2观察并行算法不同进程数运行结果，分析得出结论； 2、实验要求 1编写矩阵乘法的串行程序，多次运行得到结果汇总； 2编写基于MPI，分别实现矩阵乘法的并行化。对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。 二、实验设备（环境）及要求 《VS2013》C++语言 MPICH2 三、实验内容与步骤 实验1，矩阵乘法的串行实验 （1）实验内容 编写串行程序，运行汇总结果。 （2）主要步骤 按照正常的矩阵乘法计算方法，在《VS2013》上编写矩阵乘法的串行程序，编译后多次运行，得到结果汇总。 实验2矩阵乘法的并行化实验 3个总进程 5个总进程 7个总进程 9个进程 16个进程 四：实验结果与分析（一）矩阵乘法并行化 矩阵并行化算法分析： 并行策略：1间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程1：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此O(n)=(n); 2间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程3：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此T(n)=O(n); 矩阵连乘问题《算法分析与设计》 设计性实验报告 课程名称：《算法分析与设计》矩阵连乘问题实验题目：长：组员一：成 二：成员成员三：数学与计算机科学系别：系专业班级：指导教师：实验日期： 一、实验目的和要求 实验目的 熟悉动态规划算法设计思想和设计步骤，掌握基 本的程序设计方法，培养学生用计算机解决实际问题的能力。 实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可 以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行 实验，要求在学期末形成完整的项目程序设计报告。 二、实验内容提要 矩阵连乘问题给定n个矩阵{A,A,…,A}， 其中，Ai与Ai+1是可乘的，n21A,A,…,A。由于矩阵乘法满足结n-1。考查这n个矩阵的连乘积i=1,2，…，n12合律，故计算矩阵的连乘积可以有 许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反 复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可 递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。 三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问 题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降- 1 - 矩阵乘积Ai Ai+1…Aj简记为A[i:j]。 南京林业大学 实验报告 基于AT89C51 单片机4x4矩阵键盘接口电路设计 课程机电一体化设计基础 院系机械电子工程学院 班级 学号 姓名 指导老师杨雨图 2013年9月26日 一、实验目的 1、掌握键盘接口的基本特点，了解独立键盘和矩 阵键盘的应用方法。 2、掌握键盘接口的硬件设计方法，软件程序设计 和贴士排错能力。 3、掌握利用Keil51软件对程序进行编译。 4、用Proteus软件绘制“矩阵键盘扫描”电路，并用测试程序进行仿真。 5、会根据实际功能，正确选择单片机功能接线，编制正确程序。对实验结果 能做出分析和解释，能写出符合规格的实验报告。 二、实验要求 通过实训，学生应达到以下几方面的要求： 素质要求 1.以积极认真的态度对待本次实训，遵章守纪、团结协作。 2.善于发现数字电路中存在的问题、分析问题、解决问题，努力培养独立 工作能力。 能力要求 1.模拟电路的理论知识 2.脉冲与数字电路的理念知识 3.通过模拟、数字电路实验有一定的动手能力 4.能熟练的编写8951单片机汇编程序 5.能够熟练的运用仿真软件进行仿真 三、实验工具 1、软件：Proteus软件、keil51。 2、硬件：PC机，串口线，并口线，单片机开发板 四、实验内容 1、掌握并理解“矩阵键盘扫描”的原理及制作，了解各元器件的参数及格 元器件的作用。 2、用keil51测试软件编写AT89C51单片机汇编程序 3、用Proteus软件绘制“矩阵键盘扫描”电路原理图。 4、运用仿真软件对电路进行仿真。 五．实验基本步骤 1、用Proteus绘制“矩阵键盘扫描”电路原理图。 2、编写程序使数码管显示当前闭合按键的键值。 3、利用Proteus软件的仿真功能对其进行仿真测试，观察数码管的显示状 态和按键开关的对应关系。 4、用keil51软件编写程序，并生成HEX文件。 5、根据绘制“矩阵键盘扫描”电路原理图，搭建相关硬件电路。 6、用通用编程器或ISP下载HEX程序到MCU。 7、检查验证结果。 六、实验具体内容 使用单片机的P1口与矩阵式键盘连接时，可以将P1口低4位的4条端口线定义为行线，P1口高4位的4条端口线定义为列线，形成4*4键盘，可以配置16个按键，将单片机P2口与七段数码管连接，当按下矩阵键盘任意键时，数码管显示该键所在的键号。 1、电路图 专业课程设计I报告（2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主 控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：软件12K1 学生姓名：吴旭 学号：121909020124 成绩： 指导老师：刘老师实验日期：2014.11.14 一、实验内容 矩阵连乘问题，给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,A n。 二、主要思想 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号 的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A k和A k+1之间将矩阵链断开，1n,则其相应的完全加括号方式为((A1…A k)(A k+1…A n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计 算结果相乘得到A[1:n]。 2、建立递归关系 设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1i n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。 当i=j时，A[i:j]=A i为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。 当i 数学实验报告 学院： 班级： 学号： 姓名： 完成日期： 实验四矩阵的运算 （一）投入产出分析 一．实验目的 1.理解投入产出分析中的基本概念和模型； 2.从数学和投入产出理论的角度，理解矩阵乘法、逆矩 阵等的含义。 二．问题描述 设国民经济由农业、制造业和服务业三个部门构成，已知某年它们之间的投入产出关系、部需求、初始投入等如表1-1所示 表1-1国民经济三产部门之间的投入产出表 根据表回答下列问题： （1）如果农业、制造业、服务业外部需求为50,150,100，问三个部门总产出分别为多少？ （2）如果三个部门的外部需求分别增加一个单位，问 他们的总产出分别为多少? 三.实验过程 1．问题（1）的求解 （1）求直接消耗矩阵A 根据直接消耗的计算公式 a ij=x ij/x j 和各部门中间需求; x n a n 运行如下代码可得直接消耗系数表。 X=[15 20 30;30 10 45;20 60 0]; X_colsum=[100 200 150]; X_rep=repmat(X_colsum,3,1) A=X./ X_rep 运行结果为： A = 0.1500 0.1000 0.2000 0.3000 0.0500 0.3000 0.2000 0.3000 0 （2）求解 根据公式 X=(I-A)-1y 在运行如下代码 y=[50;150;100]; n=size(y,1); W=eye(n)-A; X=W\y 运行结果为 X = 139.2801 267.6056 208.1377 即三个部门的总产出分别为139.2801,267.6056, 208.1377亿元。 2．问题2求解 设外部需求由y增加至y+Δy，则产出x的增量为 Δx=(I-A)-1(y+Δy)- (I-A)-1y=(I-A)-1Δy 利用问题（1）求得的I-A矩阵，再运行如下的MATLAB 代码可得问题的结果： dx=inv(W) 运行结果: dx = 1.3459 0.2504 0.3443 0.5634 1.2676 0.4930 0.4382 0.4304 1.2167 《算法设计与分析》实验报告 目录 一、实验内容描述和功能分析. 二、算法过程设计. 三、程序调试及结果（附截图）. 四、源代码（附源代码）. 一、实验内容描述和功能分析. 1.矩阵连乘问题 内容描述：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 功能分析：输入包含多组测试数据。第一行为一个整数C，表示有C 组测试数据，接下来有2*C行数据，每组测试数据占2行，每组测试数据第一行是1个整数n，表示有n个矩阵连乘,接下来一行有n+1 个数,表示是n个矩阵的行及第n个矩阵的列,它们之间用空格隔开。输出应该有C行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数。 例如：输入：1输出：7500 3 10 100 5 50 2.Pebble Merging 内容描述：在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务： 对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。 功能分析：输入由多组测试数据组成。每组测试数据输入的第1 行是正整数n，1≤n≤100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。 对应每组输入，输出的第1 行中的数是最小得分；第2 行中的数是最大得分。 例如：输入：4 输出：43 4 4 5 9 54 二、算法过程设计. 1.矩阵连乘问题 矩阵连乘问题是通过设置数组，利用数组的横竖坐标来进行矩阵对应行与列的计算。 2.Pebble Merging 这个问题也是跟数组相关，通过寻找数组中的最大和最小值来进行计算。 三、程序调试及结果（附截图）. 1.矩阵连乘问题 2.Pebble Merging MATLAB 程序设计实验 班级：电信1104班 姓名：龙刚 学号：1404110427 实验内容：了解MA TLAB 基本使用方法和矩阵的操作 一．实验目的 1.了解MA TLAB 的基本使用方法。 2.掌握MA TLAB 数据对象的特点和运算规则。 3.掌握MA TLAB 中建立矩阵的方法和矩阵的处理方法。 二．实验内容 1. 浏览MATLAB 的start 菜单，了解所安装的模块和功能。 2. 建立自己的工作目录，使用MA TLAB 将其设置为当前工作目录。使用path 命令和工作区浏览两种方法。 3. 使用Help 帮助功能，查询inv 、plot 、max 、round 等函数的用法和功能。使用help 命令和help 菜单。 4. 建立一组变量，如x=0:pi/10:2*pi ，y=sin(x)，在命令窗口显示这些变量；在变量窗口打开这些变量，观察其值并使用绘图菜单绘制y 。 5. 分多行输入一个MA TLAB 命令。 6. 求表达式的值 ()6210.3424510w -=+? ()22tan b c a e abc x b c a ππ++ -+=++，a=3.5，b=5，c=-9.8 ()220.5ln 1t z e t t =++，21350.65i t -??=??-?? 7.已知 1540783617A --????=??????，831253320B -????=????-?? 求 A+6B ，A 2-B+I A*B ，A.*B ，B*A A/B ，B/A [A,B]，[A([1,3], :); B^2] 8.已知 23100.7780414565532503269.5454 3.14A -????-??=????-?? 输出A 在[10,25]范围内的全部元素 取出A 的前三行构成矩阵B ，前两列构成矩阵C ，右下角3x2子矩阵构成矩阵D ，B 与C 的乘积构成矩阵E 分别求表达式E 专业课程设计I报告（ 2011 / 2012 学年第二学期） 题目稀疏矩阵的转换 专业软件工程 学生姓名张鹏宇 班级学号 09003018 指导教师张卫丰 指导单位计算机学院软件工程系 日期 2012年6月18号 指导教师成绩评定表 附件： 稀疏矩阵的转换 一、课题内容和要求 1．问题描述 设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 二、设计思路分析 （1）设计函数建立稀疏矩阵，初始化值。 （2）设计函数输出稀疏矩阵的值。 （3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。 （4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。 （5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。 （6）构造函数进行稀疏矩阵的转置，并输出结果。 （7）退出系统。 三、概要设计 为了实现以上功能，可以从3个方面着手设计。 1．主界面设计 为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计 本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计 本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的加法： 此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。 （2）稀疏矩阵的乘法： 此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始 实验报告 --矩阵运算 一．实验目的。 1.通过实践加强对程序设计语言课程知识点的理解和掌握，培养对课程知识综合运用能力、实际分析问题能力及编程能力，养成良好的编程习惯。 2.通过实践进一步领会程序设计的特点和应用，提高运用C++ 语言以及面向对象知识解决实际问题的能力。 3.通过实践掌握用C++ 语言编写面向对象的实用程序的设计方法，对面向对象方法和思想增加感性的认识； 4.学会利用C++程序设计语言编写出一些短小、可靠的Windows实用程序，切实提高面向对象的程序设计能力。为后续的相关课程的学习打下基础。 二．实验要求。 1.学会建立模板类； 2.实现矩阵的“加”、“减”、“乘”、“数乘”、“转置”； 3.动态存分配并用随机数填充； 4.注意“加”、“减”、“乘”要进行条件的判断； 三．设计思路。 3.1算法基本流程 1)获取用户输入的矩阵1的行数和列数,动态生成一个一维数组 2)利用随机数生成数组成员,并利用两个循环输出数组,使其符合矩阵的格式 3)矩阵2同矩阵1的处理方法 4)通过两个矩阵的行数和列数比较来判断能否进行加减乘等运算,如不能,输出相关信息 5)如能够进行计算,则利用数组进行相应运算,并按照正确格式输出 6)通过改变一维数组中元素的顺序来实现转置并输出 3.2算法流程图 四．基本界面。 五．关键代码。 5.1关键类的声明 class CMatrixclass { public: CMatrixclass() { int m_Row = 0; //行 int m_Col = 0; //列 m_pElements = NULL; //一维数组 湖南涉外经济学院计算机科学与技术专业 《算法设计与分析》课程 矩阵连乘备忘录算法 实验报告 班级： 学号： 姓名： 教师： 成绩： 2012年5月 【实验目的】 1 掌握动态规划算法和备忘录方法； 2 利用动态规划备忘录思想实现矩阵连乘； 3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到 O(nlgn) 【系统环境】 Windows 07 平台 【实验工具】 VC++6.0中文企业版 【问题描述】 描述：给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式。 例：矩阵连乘积A1A2A3A4可以有一下五种不同的完全加括号方式： （A1（A2（A3A4））） （A1（（A2A3）A4）） （（A1A2）（A3A4）） （（A1（A2A3））A4） （（（A1A2）A3）A4） 【实验原理】 原理：1、矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。 2、利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。 思路：m初始化为0，表示相应的子问题还位被计算。在调用LookupChain时，若m[i][j]>0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。 方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。 【源程序代码】 #include 课程设计任务书 学生姓名：专业班级： 指导教师：夏红霞工作单位：计算机科学与技术学院题目: 稀疏矩阵乘法的运算 课程设计要求: 1、熟练掌握基本的数据结构； 2、熟练掌握各种算法； 3、运用高级语言编写质量高、风格好的应用程序。 课程设计任务: 1、系统应具备的功能： （1）设计稀疏矩阵的存储结构 （2）建立稀疏矩阵 （3）实现稀疏矩阵的乘法 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排：2010年7月5日－9日（第19周） 7月5日查阅资料 7月6日系统设计，数据结构设计，算法设计 7月7日 -8日编程并上机调试 7月9日撰写报告 7月10日验收程序，提交设计报告书。 指导教师签名： 2010年7月4日系主任（或责任教师）签名： 2010年7月4日 目录 1.摘要 (1) 2.关键字 (1) 3.引言 (1) 4. 问题描述 (1) 5. 系统设计 (1) 6. 数据结构 (3) 7. 算法描述 (3) 8. 测试结果与分析 (4) 9. 源代码 (12) 10. 总结 (29) 11.参考文献 (29) 稀疏矩阵乘法的运算 1.摘要：在一些数值计算中，一些二维矩阵的乘法运算很常见，我们经常采用线性代数中的知识进行运算，然而对一些含有非零元很少的二维矩阵也采用相同的方法时，就会发现那样的方法不仅需要很多的空间来存储0，造成空间复杂度比较大，而且算法的时间复杂度也较大。因此需要采取其他的方法来解决这个问题，由于0在乘法中其结果总是0，所以可以考虑采用三元组的方式去存储稀疏矩阵中的非零元，这样在计算过程中不仅需要的内存空间减少了，而且运算的速率也提高了。 2.关键字：稀疏矩阵乘法二维矩阵算法复杂度 3.引言：随着科学技术的发展，人们对矩阵的运算的几率越来越大，特别是高新科技研究中对矩阵的运算更是常见。但是如何高效的并占内存少的进行矩阵运算就是一个急需解决的问题。本文主要对稀疏矩阵的存储以及稀疏矩阵的乘法运算进行了研究和探讨。 4.问题描述：在一些数值计算中，一些二维矩阵的乘法运算很常见，我们经常采用线性代数中的知识进行运算，然而对一些含有非零元很少的二维矩阵也采用相同的方法时，就会发现那样的方法不仅需要很多的空间来存储0，造成空间复杂度比较大，而且算法的时间复杂度也较大。为了减少空间和时间复杂度，可以根据给定的二维数组的数据设计稀疏矩阵的存储结构，然后根据设计的稀疏矩阵存储结构建立一个稀疏矩阵，最后获得两个二维数组得到他们各自的稀疏矩阵，计算这两个稀疏矩阵的乘积。 5.系统设计： 5.1 设计目标：通过一定的数据结构，存储含有少量数据的矩阵，把他们存入一个稀疏矩阵中，然后实现稀疏矩阵的乘法运算。[基本要求]设计稀疏矩阵的存储结构；建立稀疏矩阵；实现稀疏矩阵的乘法 科技大学计算机与通信工程学院 实验报告 实验名称： 学生： 专业： 班级： 学号： 指导教师： 实验成绩：________________________________ 实验地点： 实验时间：2015年05月 一、实验目的与实验要求 1、实验目的 1对比矩阵乘法的串行和并行算法，查看运行时间，得出相应的结论；2观察并行算法不同进程数运行结果，分析得出结论； 2、实验要求 1编写矩阵乘法的串行程序，多次运行得到结果汇总； 2编写基于MPI，分别实现矩阵乘法的并行化。对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。 二、实验设备（环境）及要求 《VS2013》C++语言 MPICH2 三、实验容与步骤 实验1，矩阵乘法的串行实验 （1）实验容 编写串行程序，运行汇总结果。 （2）主要步骤 按照正常的矩阵乘法计算方法，在《VS2013》上编写矩阵乘法的串行程序，编译后多次运行，得到结果汇总。 实验2矩阵乘法的并行化实验 3个总进程 5个总进程 7个总进程 9个进程 16个进程 四：实验结果与分析（一）矩阵乘法并行化 矩阵并行化算法分析： 并行策略：1间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程1：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此O(n)=(n); 2间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程3：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此T(n)=O(n); 动态规划算法实验报告 ————————————————————————————————作者: ————————————————————————————————日期: 实验标题 1、矩阵连乘 2、最长公共子序列３、最大子段和 4、凸多边形最优三角剖分 5、流水作业调度 6、0－１背包问题 7、最优二叉搜索树 实验目的掌握动态规划法的基本思想和算法设计的基本步骤。 实验内容与源码1、矩阵连乘 #inclｕde算法分析_实验报告3
矩阵分析实验报告
实现稀疏矩阵(采用三元组表示)的基本运算实验报告
算法分析与设计实验报告
矩阵特征值实验报告
矩阵乘法的并行化 实验报告
矩阵连乘问题算法分析与设计
矩阵键盘设计实验报告
稀疏矩阵的运算(完美版)
矩阵连乘实验报告
数学实验矩阵的运算
算法分析实验三报告
MATLAB矩阵实验报告
稀疏矩阵的运算(完美版)
矩阵运算实验报告
矩阵连乘备忘录算法
稀疏矩阵乘法的运算
矩阵乘法的并行化实验报告
动态规划算法实验报告