下面的代码是对《算法导论》(第二版)第十五章第二节内容的实现。这个算法的时间复杂度是O(n3)(n的3次方)。
下面的网址是网上很常见的一个c++的算法实现: http://blog.csdn.net/ujs_abc/archive/2008/02/01/2076876.aspx
public class MatrixOrder2
{
private static String name = "ABCDEF";
private static int[] a = {30, 35, 15, 5, 10, 20, 25};
private static int len = a.length - 1;
private static int[][] m = new int[len][len];
private static int[][] s = new int[len][len];
public static void main(String[] args)
{
System.out.print("最少需要的计算次数:");
Compute(a, m, s);
System.out.println();
System.out.print("矩阵相乘的顺序为: ");
Display(s, name, 0, len-1);
}
public static void Compute(int[] a, int[][] m, int[][] s)
{
int t = 0;
int min = 0;
int temp = 0;
for(int i=2; i<a.length; i++)
{
for(int j=0; j<a.length-i; j++)
{
t = j + i - 1;
m[j][t] = Integer.MAX_VALUE;
for(int k=j; k<t; k++)
{
temp = m[j][k] + m[k+1][t] + a[j]*a[k+1]*a[t+1];
if(temp < m[j][t])
{
min = temp;
m[j][t] = temp;
s[j][t] = k;
}
}
}
}
System.out.print(min);
}
public static void Display(int[][] s, String name, int i, int j)
{
if(i == j)
{
System.out.print(name.charAt(i));
}
else
{
System.out.print("(");
Display(s, name, i, s[i][j]);
Display(s, name, s[i][j]+1, j);
System.out.print(")");
}
}
}
分享到:
相关推荐
用C++实现的矩阵链相乘算法,并包含大量的注释,对理解程序很有帮助
矩阵乘法 链矩阵乘法的动态规划算法的实现
以行逻辑链接的三元组为结构,实现稀疏矩阵的压缩存储,对压缩后的矩阵进行转置,两矩阵相加相乘。判断所给矩阵是否为稀疏矩阵,java实现
像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java编写的显示器显示模式检测程序 2个目标文件 内容...
像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java编写的显示器显示模式检测程序 2个目标文件 内容...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置...
矩阵链乘法 计算与'n'个矩阵相乘所需的最小标量乘法数...实现递归,动态编程和算法的简化版本,以解决矩阵链乘法。 比较所有三种算法的运行时间,以了解这些方法之间的区别。 注意:最佳Paranthesization的代码将更新
3.矩阵链乘法 4.最优二叉查找树 greedy:贪心算法 leetcode: LeetCode上的题目 methodofprogramming: 编程之美上的例子以及习题 第一章:字符 AlternateStr: 输入三个字符串s1、s2和s3,判断第三个字符串s3是否由前两...
算法设计技巧10.1 贪婪算法10.1.1 一个简单的调度问题10.1.2 哈夫曼编码10.1.3 近似装箱问题10.2 分治算法10.2.1 分治算法的运行时间10.2.2 最近点问题10.2.3 选择问题10.2.4 一些算术问题的理论改进10.3 动态规划...
算法设计技巧10.1 贪婪算法10.1.1 一个简单的调度问题10.1.2 哈夫曼编码10.1.3 近似装箱问题10.2 分治算法10.2.1 分治算法的运行时间10.2.2 最近点问题10.2.3 选择问题10.2.4 一些算术问题的理论改进10.3 动态规划...
矩阵链乘法 该程序找到了最有效的乘法矩阵的方法。 该程序实现的复杂度为O(n ^ 3),并用O(n)括住最终输出 输入规范:第一行包含n,下一行包含a0,...,an,以空格分隔。 假定所有数字都是正数且适合int且n最多为...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7 实例1 开发第一个Java...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7...
算法设计技巧10.1 贪婪算法10.1.1 一个简单的调度问题10.1.2 哈夫曼编码10.1.3 近似装箱问题10.2 分治算法10.2.1 分治算法的运行时间10.2.2 最近点问题10.2.3 选择问题10.2.4 一些算术问题的理论改进10.3 动态规划...
Java范例开发大全(全书源程序),目录如下: 第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境...
10.3 动态规划 10.3.1 用一个表代替递归 10.3.2 矩阵乘法的顺序安排 10.3.3 最优二叉查找树 10.3.4 所有点对最短路径 10.4 随机化算法 10.4.1 随机数发生器 10.4.2 跳跃表 10.4.3 素性测试 10.5 回溯算法 10.5.1 ...
第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7 实例1 开发第一个Java...
10.1.3 近似装箱问题 10.2 分治算法 10.2.1 分治算法的运行时间 10.2.2 最近点问题 10.2.3 选择问题 10.2.4 一些算术问题的理论改进 10.3 动态规划 10.3.1 用一个表代替递归 10.3.2 矩阵乘法的顺序...