`

动态规划之矩阵链乘法的Java实现

阅读更多

      下面的代码是对《算法导论》(第二版)第十五章第二节内容的实现。这个算法的时间复杂度是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(")");
		}
	}
}
0
0
分享到:
评论

相关推荐

    矩阵链相乘算法

    用C++实现的矩阵链相乘算法,并包含大量的注释,对理解程序很有帮助

    MatrixMultiplication:链矩阵乘法动态规划算法的Java实现

    矩阵乘法 链矩阵乘法的动态规划算法的实现

    以行逻辑链接的三元组为结构,实现稀疏矩阵的压缩存储,对压缩后的矩阵进行转置,两矩阵相加相乘 java

    以行逻辑链接的三元组为结构,实现稀疏矩阵的压缩存储,对压缩后的矩阵进行转置,两矩阵相加相乘。判断所给矩阵是否为稀疏矩阵,java实现

    JAVA上百实例源码以及开源项目源代码

    像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java编写的显示器显示模式检测程序 2个目标文件 内容...

    JAVA上百实例源码以及开源项目

    像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java编写的显示器显示模式检测程序 2个目标文件 内容...

    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配置...

    Matrix-Chain-Multiplication:计算与'n'个矩阵相乘所需的最小标量乘法数,并确定必须相乘的顺序

    矩阵链乘法 计算与'n'个矩阵相乘所需的最小标量乘法数...实现递归,动态编程和算法的简化版本,以解决矩阵链乘法。 比较所有三种算法的运行时间,以了解这些方法之间的区别。 注意:最佳Paranthesization的代码将更新

    leetcode数组下标大于间距-algorithm_java:实现数据结构和算法

    3.矩阵链乘法 4.最优二叉查找树 greedy:贪心算法 leetcode: LeetCode上的题目 methodofprogramming: 编程之美上的例子以及习题 第一章:字符 AlternateStr: 输入三个字符串s1、s2和s3,判断第三个字符串s3是否由前两...

    数据结构与算法分析Java语言描述(第二版)

    算法设计技巧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语言描述(第2版)]

    算法设计技巧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 动态规划...

    Matrix-Chain-Multiplication

    矩阵链乘法 该程序找到了最有效的乘法矩阵的方法。 该程序实现的复杂度为O(n ^ 3),并用O(n)括住最终输出 输入规范:第一行包含n,下一行包含a0,...,an,以空格分隔。 假定所有数字都是正数且适合int且n最多为...

    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 实例1 开发第一个Java...

    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...

    数据结构与算法分析 Java语言描述第2版

    算法设计技巧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范例开发大全(全书源程序)

    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 配置环境...

    数据结构与算法分析_Java语言描述(第2版)

    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 ...

    java范例开发大全(pdf&源码)

    第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...

    数据结构与算法分析-Java语言描述(第2版)_2_2

    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 矩阵乘法的顺序...

Global site tag (gtag.js) - Google Analytics