源文件：http://pan.baidu.com/share/link?shareid=481923&uk=3912660076
//Main:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace MatrixMultiplication { class Program { static void Main(string[] args) { Console.WriteLine("Please enter numbers of Matix:"); int Mnum = Convert.ToInt32(Console.ReadLine()); MatrixMultiplication obj = new MatrixMultiplication(Mnum + 1); int[,] MatrixThree = obj.NormalRecursionMatrixMultiplication(obj.MatrixChain); obj.ShowMatrix(MatrixThree); obj.BottomUpNotRecursionMatrixMultiplication(obj.MatrixChain); Console.WriteLine(); obj.TopDownRecursionMatrixMultiplication(obj.MatrixChain); Console.ReadKey(); } } }
//Class
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace MatrixMultiplication { class MatrixMultiplication { // bool ErrorTorF; private int[,] MatrixOne; private int[,] MatrixTwo; private int[,] MatrixThree; private int index = 1;// private string[] An;//矩阵链字符格式化 private string LParenthesis = "("; private string RParenthesis = ")"; //数据仓库啊...哈哈 private int[,] initMatrixCalcData;//0行0列除外 1行1列：完全加括号矩阵链1~1计算量... private int[,] MatrixChainValue;//0行除外 1行：第一个矩阵... 列：连续维数值 private int[,] TracePoint;//row：始矩阵，col：末矩阵，最小矩阵链计算量的断开位置。 public int[,] MatrixChain { get { return MatrixChainValue; } } public MatrixMultiplication(int initMatrixChain) { //牺牲储存空间... MatrixChainValue = new int[initMatrixChain, 2];//n个矩阵n+1行 0行不在其中 InitializeArray(); } //储存各矩阵为几行几列矩阵 private void InitializeArray() { An = new string[MatrixChainValue.GetLength(0)]; //i表示第i个矩阵... for (int i = 1; i < MatrixChainValue.GetLength(0); i++) { An[i] = "Ａ" + i.ToString(); Error://0,row 0,col ; 1,row 1,col ; ... Console.WriteLine("Please enter the size of the {0} Matrix(row and low):", i); int row = Convert.ToInt32(Console.ReadLine()); MatrixChainValue[i, 0] = row;//行值 int col = Convert.ToInt32(Console.ReadLine()); MatrixChainValue[i, 1] = col;//列值 if (i > 1 && MatrixChainValue[i, 0] != MatrixChainValue[i - 1, 1]) { Console.WriteLine("Error !"); goto Error; } } Console.WriteLine("Dispaly Matrix Chain:"); Console.WriteLine(); for (int i = 1; i < An.Length; i++) { Console.Write("{0,8}", An[i]); } Console.WriteLine(); for (int i = 1; i < MatrixChainValue.GetLength(0); i++) { Console.Write("{0,4}{1,5}", MatrixChainValue[i, 0], " "); if (i == (MatrixChainValue.GetLength(0) - 1)) Console.Write("{0,4}", MatrixChainValue[i, 1]); } Console.WriteLine(); } /// <summary> /// 普通矩阵相乘 /// </summary> /// <param name="MatrixChain">保存矩阵的行和列数(去掉重复的)</param> /// <returns>最终矩阵</returns> public int[,] NormalRecursionMatrixMultiplication(int[,] MatrixChain) { if (index < MatrixChain.GetLength(0)) { if (index == 1) { MatrixOne = new int[MatrixChain[index, 0], MatrixChain[index++, 1]]; MatrixTwo = new int[MatrixChain[index, 0], MatrixChain[index++, 1]]; } else { MatrixOne = MatrixThree; MatrixTwo = new int[MatrixChain[index, 0], MatrixChain[index++, 1]]; } MatrixThree = new int[MatrixOne.GetLength(0), MatrixTwo.GetLength(1)]; for (int i = 0; i < MatrixOne.GetLength(0); i++)//第一个矩阵的行 { for (int j = 0; j < MatrixTwo.GetLength(1); j++)//第二个矩阵的列 { int temp = 0; for (int k = 0; k < MatrixTwo.GetLength(0); k++)//第一个矩阵的列同增，第二个矩阵的行同增。一的列或二的行为index { temp += MatrixOne[i, k] * MatrixTwo[k, j]; } MatrixThree[i, j] = temp; } } NormalRecursionMatrixMultiplication(MatrixChain); } return MatrixThree; } /// <summary> /// 动态规划自底向上 ///非递归这里不记录非最优的值... /// </summary> /// <param name="MatrixChain">保存矩阵的行和列数(去掉重复的)</param> public void BottomUpNotRecursionMatrixMultiplication(int[,] MatrixChain) { //储存链矩阵的计算量 initMatrixCalcData = new int[MatrixChain.GetLength(0), MatrixChain.GetLength(0)]; //储存断点 TracePoint = new int[MatrixChain.GetLength(0), MatrixChain.GetLength(0)]; //单个矩阵计算量为 0 ，看做完全加括号矩阵 for (int i = 1; i < initMatrixCalcData.GetLength(0); i++) initMatrixCalcData[i, i] = 0; //本质在填充最优二维表initMatriCalcData...假设5个矩阵 //i表示矩阵链跨度最长为整个矩阵链-1(这里是"<")i：max:4 for (int i = 1; i < initMatrixCalcData.GetLength(0) - 1; i++) { //j表示起始矩阵，j+i表示终止矩阵=1+4=5 for (int j = 1; j + i < initMatrixCalcData.GetLength(0); j++)//矩阵链 { //保存矩阵链不同分割位置的计算量 int tempinitMatrixCalcData = 0; //k表示断点位置,从起始矩阵开始 for (int k = j; k < j + i; k++) { //在矩阵链中对每个合适的断点位置计算矩阵的计算量（左链+左*右+右链） //初始tempinitMatrixCalcData一下 tempinitMatrixCalcData = initMatrixCalcData[j, k] + MatrixChainValue[j, 0] * MatrixChainValue[k, 1] * MatrixChainValue[j + i, 1] + initMatrixCalcData[k + 1, j + i]; if (k == j) { //假设最小计算量的分割位置是第一个 initMatrixCalcData[j, j + i] = tempinitMatrixCalcData; TracePoint[j, j + i] = j; } //记录最小计算量的断点(矩阵链为2 时只有一种可能) if (tempinitMatrixCalcData < initMatrixCalcData[j, j + i]) { //存在其他最小分割点计算量 TracePoint[j, j + i] = k; initMatrixCalcData[j, j + i] = tempinitMatrixCalcData; } } } } //最后输出计算量最小的矩阵链相乘次序。 DynamicProgramming(1, MatrixChainValue.GetLength(0) - 1, TracePoint); Show(); } /// <summary> /// 动态规划自顶向下 /// </summary> /// <param name="MatrixChain">保存矩阵的行和列数(去掉重复的)</param> public void TopDownRecursionMatrixMultiplication(int[,] MatrixChain) { //储存链矩阵的计算量 initMatrixCalcData = new int[MatrixChain.GetLength(0), MatrixChain.GetLength(0)]; //单个矩阵计算量为 0 ，看做完全加括号矩阵 //储存断点 TracePoint = new int[MatrixChain.GetLength(0), MatrixChain.GetLength(0)]; //for (int i = 1; i < initMatrixCalcData.GetLength(0); i++) // initMatrixCalcData[i, i] = 0; Recursion(1, MatrixChainValue.GetLength(0) - 1, initMatrixCalcData, TracePoint); //最后输出计算量最小的矩阵链相乘次序。 DynamicProgramming(1, MatrixChainValue.GetLength(0) - 1, TracePoint); Show(); }//得到最小值 1 6 private int Recursion(int startMatrix, int endMatrix, int[,] initMatrixCalcData, int[,] TracePoint) { if (startMatrix == endMatrix) return 0; //i表示断点 for (int i = startMatrix; i < endMatrix; i++) { // 1 int tempMatrixCalcData = Recursion(startMatrix, i, initMatrixCalcData, TracePoint) + MatrixChainValue[startMatrix, 0] * MatrixChainValue[i/*2*/, 1] * MatrixChainValue[endMatrix, 1] + Recursion(i + 1, endMatrix, initMatrixCalcData, TracePoint); if (i == startMatrix) { //假设最小计算量的分割位置是第一个 initMatrixCalcData[startMatrix, endMatrix] = tempMatrixCalcData; TracePoint[startMatrix, endMatrix] = startMatrix; } //记录最小计算量的断点(矩阵链为2 时只有一种可能) if (tempMatrixCalcData < initMatrixCalcData[startMatrix, endMatrix]) { //存在其他最小分割点计算量 TracePoint[startMatrix, endMatrix] = i; initMatrixCalcData[startMatrix, endMatrix] = tempMatrixCalcData; } } return initMatrixCalcData[startMatrix, endMatrix]; } /// <summary> /// 对矩阵进行加括号 /// </summary> /// <param name="startMatrix"></param> /// <param name="endMatrix"></param> /// <param name="TracePoint">记录的断点</param> private void DynamicProgramming(int startMatrix, int endMatrix, int[,] TracePoint) { if (startMatrix == endMatrix) return; //startMatrix表示起始矩阵，endMatrix表示终止矩阵. //先左后右 DynamicProgramming(startMatrix, TracePoint[startMatrix, endMatrix], TracePoint); DynamicProgramming(TracePoint[startMatrix, endMatrix] + 1, endMatrix, TracePoint); //以矩阵链的分割从外向内输出(重新定义赋值)==括住子矩阵链 //先右后左 //后进（内）先出（外）... An[startMatrix] = LParenthesis + An[startMatrix]; //An[TracePoint[startMatrix, endMatrix]] += RParenthesis; //这内两个结合外两个是为自身加括号的 //An[TracePoint[startMatrix, endMatrix] + 1] = LParenthesis + An[TracePoint[startMatrix, endMatrix] + 1]; An[endMatrix] += RParenthesis; } private void Show() { Console.WriteLine("Result:"); Console.WriteLine("Minimum Calculation is: {0}", initMatrixCalcData[1, MatrixChainValue.GetLength(0) - 1]); for (int i = 1; i < An.Length; i++) { Console.Write(An[i]); } } /// <summary> /// 输出相乘后的矩阵 /// </summary> /// <param name="Matrix">最终得到的矩阵</param> public void ShowMatrix(int[,] Matrix) { for (int j = 0; j < Matrix.GetLength(0); j++) { for (int i = 0; i < MatrixThree.GetLength(1); i++) { Console.Write(" {0}", Matrix[j, i]); } Console.WriteLine(); } } } }
//运行结果
由于重复用运一个An,第二个会出项多余的括号.......出现0没有实现数据的输入...
