- 浏览: 38003 次
- 性别:
- 来自: 北京
最新评论
-
xglv2013:
liaokangli 写道linkedhashmap 可以实现 ...
双端链表实现LRUCache -
liaokangli:
linkedhashmap 可以实现
双端链表实现LRUCache -
kesun_shy:
收藏。。过两天就试一下。
Spring MVC实现的RESTful webservice服务器并用Python调用API -
qindongliang1922:
不错
Spring MVC实现的RESTful webservice服务器并用Python调用API -
xglv2013:
<div class="quote_title ...
Java实现的矩阵链乘法动态规划算法Swing动态演示器
矩阵链乘法问题,是动态规划的一个经典问题。目的是使一个相乘的矩阵序列所用的乘法次数最少。这里用Java Swing实现了矩阵链乘法的动态演示。用到两个二维数组,m和s。其中m[i][j]的值表示第i个矩阵和第j个矩阵之间的最优的加括号的方案。s[i][j]的值表示第i个矩阵和第j个矩阵最外层的两部分在何处断开。关于矩阵、矩阵相容性和矩阵链乘法算法的详细介绍请查阅《算法导论》第15章《动态规划》,在此不做赘述。
算法运行之前:
算法运行中(其中绿色方块表示已经计算出的值,黄色方块表示正在计算的值,蓝色方块表示当前计算的值所依靠的值):
算法运行结束:
代码:
main方法中的矩阵行列数组p决定矩阵个数
算法运行之前:
算法运行中(其中绿色方块表示已经计算出的值,黄色方块表示正在计算的值,蓝色方块表示当前计算的值所依靠的值):
算法运行结束:
代码:
import java.awt.Color; import java.awt.Container; import java.awt.EventQueue; import java.awt.Font; import java.awt.Frame; import java.awt.Graphics; import java.awt.Polygon; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.JButton; import javax.swing.JComboBox; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JOptionPane; import javax.swing.JPanel; import javax.swing.SwingUtilities; import javax.swing.WindowConstants; public class MatrixChainGUI extends JFrame { int n;//矩阵个数 int di;//正方形斜对角线长 int XMStart;//m值菱形数组最左边的x坐标 int YStart;//菱形数组最左边的y坐标 int xSStart;//s值菱形数组最左边的x坐标 int rstStrXStart;//最优加括号矩阵链起始横坐标 Polygon[][] polygonArrayM;//m值菱形数组 Polygon[][] polygonArrayS;//s值菱形数组 int[] p; JPanel charPanel; JComboBox change; JButton calculate = new JButton("开始/暂停"); Container pane; DrawPolygon d;//画表格 DrawCalculateRst dr;//计算并向屏幕写结果的任务 Thread algThread;//计算向屏幕写结果的线程 PauseOrResume pOR;//暂停、恢复的任务 Thread pORThread;//暂停、恢复的线程 SynObj so = new SynObj();//用以同步 int interval;//计算速度 boolean awake = false;//暂停、恢复计算线程初始化为睡眠状态 Font fontLetter = new Font("letter", 0, 18);//字母字体 Font fontNumber = new Font("number", 0, 10);//角标字体 Font fontBracket = new Font("number", 0, 17);//括号字体 public MatrixChainGUI(int[] p, int di) { super(); n = p.length - 1; if(n <= 2) { JOptionPane.showMessageDialog(MatrixChainGUI.this, "矩阵数目最少为3", "", JOptionPane.ERROR_MESSAGE); System.exit(0); } this.p = p; this.di = di; XMStart = di/2;//m值菱形数组最左边的x坐标 YStart = di * (n+2)/2;//菱形数组最左边的y坐标 xSStart = XMStart + n*di;//s值菱形数组最左边的x坐标 rstStrXStart = XMStart;//最优加括号矩阵链起始横坐标 polygonArrayM = new Polygon[n+1][n+1];//m值菱形数组 polygonArrayS = new Polygon[n+1][n+1];//s值菱形数组 pane = this.getContentPane(); d = new DrawPolygon(); d.setIgnoreRepaint(true); charPanel = new JPanel(); String str[] = { "1", "2", "3" }; change = new JComboBox(str); charPanel.add(new JLabel("速度:")); charPanel.add(change); charPanel.add(calculate); pane.add("South", charPanel); pane.add("Center", d); calculate.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent arg0) { if(so.status.equals("0")) { pOR = new PauseOrResume(); pORThread = new Thread(pOR); pORThread.start();//启动暂停或恢复计算的线程 if(change.getSelectedItem().toString().equals("1")) { interval = 1000; } else if(change.getSelectedItem().toString().equals("2")) { interval = 600; } else { interval = 200; } dr = new DrawCalculateRst(); pane.add(dr); algThread = new Thread(dr); algThread.start();//启动开始计算的线程 } //若正在运行,则进入暂停状态;若已经暂停,则恢复 else if(so.status.equals("2") || so.status.equals("1")) { awake = true; } } }); } public class DrawPolygon extends JPanel { public void paintComponent(Graphics g) { super.paintComponents(g); //绘制m值表格 int outCount = 1; int q = 0;//纵坐标偏移单位 while(outCount < n + 1) { int inCount = 1; int p = 0;//横坐标偏移单位 int j = outCount, i = 1; while(inCount < n + 2 - outCount) { int X[] = {XMStart+di*p+di/2*q,XMStart+di/2+di*p+di/2*q,XMStart+di+di*p+di/2*q,XMStart+di/2+di*p+di/2*q}; int Y[] = {YStart-di/2*q,YStart+di/2-di/2*q,YStart-di/2*q,YStart-di/2-di/2*q}; polygonArrayM[i][j] = new Polygon(X,Y,4); g.drawPolygon(polygonArrayM[i][j]); p++; i++; j++; inCount++; } q++; outCount++; } g.drawString("m", XMStart + di * n/2, YStart - di * (n + 1)/2); //绘制m值编号 for(int i = 1; i <= n; i++) { int xl = polygonArrayM[1][i].xpoints[0]; int yl = polygonArrayM[1][i].ypoints[0]; int xr = polygonArrayM[i][n].xpoints[0]; int yr = polygonArrayM[i][n].ypoints[0]; setColorAndDrawStr(g, Color.BLACK, i, xl, yl, 0, -9*di/25); setColorAndDrawStr(g, Color.BLACK, i, xr, yr, 4*di/5, -9*di/25); } //绘制i,j字母 int xj = polygonArrayM[1][n/2].xpoints[0]; int yj = polygonArrayM[1][n/2].ypoints[0]; int xi = polygonArrayM[n/2 + 1][n].xpoints[0]; int yi = polygonArrayM[n/2 + 1][n].ypoints[0]; setColorAndDrawStr(g, Color.BLACK, "j", xj, yj, 0, -di); setColorAndDrawStr(g, Color.BLACK, "i", xi, yi, di, -di); //绘制s值表格 int outCount1 = 2; int q1 = 1;//纵坐标偏移单位 while(outCount1 < n + 1) { int inCount = 1; int p = 1;//横坐标偏移单位 int j = outCount1, i = 1; while(inCount < n + 2 - outCount1) { int X[] = {xSStart+di*p+di/2*q1,xSStart+di/2+di*p+di/2*q1,xSStart+di+di*p+di/2*q1,xSStart+di/2+di*p+di/2*q1}; int Y[] = {YStart-di/2*q1,YStart+di/2-di/2*q1,YStart-di/2*q1,YStart-di/2-di/2*q1}; polygonArrayS[i][j] = new Polygon(X,Y,4); g.drawPolygon(polygonArrayS[i][j]); p++; i++; j++; inCount++; } q1++; outCount1++; } g.drawString("s", xSStart + di * (n + 2)/2, YStart - di * (n + 1)/2); //绘制s值编号 for(int i = 2; i <= n; i++) { int xl = polygonArrayS[1][i].xpoints[0]; int yl = polygonArrayS[1][i].ypoints[0]; setColorAndDrawStr(g, Color.BLACK, i, xl, yl, 0, -9*di/25); } for(int i = 1; i <= n - 1; i++) { int xr = polygonArrayS[i][n].xpoints[0]; int yr = polygonArrayS[i][n].ypoints[0]; setColorAndDrawStr(g, Color.BLACK, i, xr, yr, 4*di/5, -9*di/25); } int matrixXStart = XMStart; for(int i = 1; i <= n; i++) { g.setFont(fontLetter); g.drawString("A", matrixXStart, YStart + di); matrixXStart = matrixXStart + 12; g.setFont(fontNumber); g.drawString(String.valueOf(i), matrixXStart, YStart + di); matrixXStart = matrixXStart + 10; g.setFont(fontLetter); g.drawString(": " + p[i - 1] + "*" + p[i] + " ", matrixXStart, YStart + di); matrixXStart = matrixXStart + di * 3/2; } } } public class SynObj { String status = "0"; } public class DrawCalculateRst extends JPanel implements Runnable { public void run() { synchronized(so) { so.status = "2"; } matrixChainMul(d.getGraphics()); } } public class PauseOrResume implements Runnable { public void run() { while(true) { while(!awake) { try { Thread.sleep(50); } catch (InterruptedException e) { e.printStackTrace(); } } if(so.status.equals("1")) { if(change.getSelectedItem().toString().equals("1")) { interval = 1000; } else if(change.getSelectedItem().toString().equals("2")) { interval = 600; } else { interval = 200; } synchronized(so) { so.status = "2"; so.notifyAll(); } } else if(so.status.equals("2")) { so.status = "1"; } awake = false; } } } //矩阵链乘法最优算序寻找算法 public void matrixChainMul(Graphics g) { long[][] m = new long[n + 1][n + 1]; int[][] s = new int[n][n + 1]; for(int i = 1; i <= n; i++) { m[i][i] = 0; int x = polygonArrayM[i][i].xpoints[0]; int y = polygonArrayM[i][i].ypoints[0]; setColorAndFill(g, Color.GREEN, polygonArrayM[i][i]); setColorAndDrawStr(g, Color.BLACK, m[i][i], x, y, 10, 5); sleepAndPossiblePause(interval); } for(int l = 2; l <= n; l++) { for(int i = 1; i <= n - l + 1; i++) { int j = i + l - 1; m[i][j] = Integer.MAX_VALUE; int x = polygonArrayM[i][j].xpoints[0]; int y = polygonArrayM[i][j].ypoints[0]; int xs = polygonArrayS[i][j].xpoints[0]; int ys = polygonArrayS[i][j].ypoints[0]; setColorAndFill(g, Color.YELLOW, polygonArrayM[i][j]); setColorAndFill(g, Color.YELLOW, polygonArrayS[i][j]); sleepAndPossiblePause(interval); for(int k = i; k <= j - 1; k++) { int x1 = polygonArrayM[i][k].xpoints[0]; int y1 = polygonArrayM[i][k].ypoints[0]; int x2 = polygonArrayM[k+1][j].xpoints[0]; int y2 = polygonArrayM[k+1][j].ypoints[0]; setColorAndFill(g, Color.BLUE, polygonArrayM[i][k]); setColorAndDrawStr(g, Color.BLACK, m[i][k], x1, y1, 10, 5); setColorAndFill(g, Color.BLUE, polygonArrayM[k+1][j]); setColorAndDrawStr(g, Color.BLACK, m[k+1][j], x2, y2, 10, 5); long q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(q < m[i][j]) { m[i][j] = q; s[i][j] = k; } sleepAndPossiblePause(interval); setColorAndFill(g, Color.GREEN, polygonArrayM[i][k]); setColorAndDrawStr(g, Color.BLACK, m[i][k], x1, y1, 10, 5); setColorAndFill(g, Color.GREEN, polygonArrayM[k+1][j]); setColorAndDrawStr(g, Color.BLACK, m[k+1][j], x2, y2, 10, 5); } setColorAndFill(g, Color.GREEN, polygonArrayM[i][j]); setColorAndDrawStr(g, Color.BLACK, m[i][j], x, y, 10, 5); setColorAndFill(g, Color.GREEN, polygonArrayS[i][j]); setColorAndDrawStr(g, Color.BLACK, s[i][j], xs, ys, 10, 5); sleepAndPossiblePause(interval); } } g.drawString("最优的加括号的序列: ", rstStrXStart, YStart + di * 2); rstStrXStart = rstStrXStart + 120; printRstSequence(s, 1, n, g); } //打印加括号顺序 public void printRstSequence(int[][] s, int i, int j, Graphics g) { if(i == j) { g.setFont(fontLetter); g.drawString("A", rstStrXStart, YStart + di * 2); rstStrXStart = rstStrXStart + di/4; g.setFont(fontNumber); g.drawString(String.valueOf(i), rstStrXStart, YStart + di * 2); rstStrXStart = rstStrXStart + di/4; System.out.print("A" + i + " "); } else { g.setFont(fontBracket); g.drawString("(", rstStrXStart, YStart + di * 2); rstStrXStart = rstStrXStart + di/4; System.out.print("("); printRstSequence(s, i, s[i][j], g); printRstSequence(s, s[i][j] + 1, j, g); g.setFont(fontBracket); g.drawString(")", rstStrXStart, YStart + di * 2); rstStrXStart = rstStrXStart + di/4; System.out.print(")"); } } //睡眠并可能暂停 private void sleepAndPossiblePause(int interval) { try { Thread.sleep(interval); synchronized(so) { while(so.status.equals("1")) { so.wait(); } } } catch (InterruptedException e) { e.printStackTrace(); } } private void setColorAndFill(Graphics g, Color c, Polygon p) { g.setColor(c); g.fillPolygon(p); g.setColor(Color.BLACK); g.drawPolygon(p); } private void setColorAndDrawStr(Graphics g, Color c, Object value, int x, int y, int xDeviation, int yDeviation) { g.setColor(c); g.drawString(String.valueOf(value), x + xDeviation, y + yDeviation); } private static class FrameShower implements Runnable { private final Frame frame; FrameShower(Frame frame) { this.frame = frame; } public void run() { frame.setVisible(true); } } public static void main(String[] args) { SwingUtilities.invokeLater(new Runnable() { public void run() { //矩阵行列数组 int[] p = {27, 33, 20, 18, 15, 18, 25}; int di = 50; int n = p.length - 1; MatrixChainGUI c = new MatrixChainGUI(p, di); c.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE); c.pack(); c.setSize(di * (2 * n + 2), di * (n+2)/2 + 200); c.setResizable(false); c.setTitle("矩阵链乘法的动态规划算法"); EventQueue.invokeLater(new FrameShower(c)); } }); } }
main方法中的矩阵行列数组p决定矩阵个数
发表评论
-
社区内互不相邻的房间内财物之和的最大值
2016-07-06 19:43 2242一个很有意思的问题,一个社区,所有的房子构成一棵二叉树,每个房 ... -
隐马尔可夫模型之:维特比算法
2016-06-25 18:47 2301接上一篇博客的内容,给出利用已知的隐马尔可夫模 ... -
隐马尔可夫模型之:前向算法
2016-06-23 20:53 2512隐马尔可夫模型(hidden markov model 简称h ... -
双端链表实现LRUCache
2015-04-12 23:07 1986Memcached的实现核心就是一个LRU算法,它使用双端链表 ... -
字符串全排列 java实现
2014-08-26 15:03 1244package permStr; public clas ... -
Java实现判断入栈序列是否可以以某个序列出栈
2013-05-17 00:48 1748输入第一个序列inSequence,是车厢入栈顺序 输入第二个 ... -
《算法导论》习题A.1-2解答
2013-05-14 14:31 1486根据调和级数等式证明本习题
相关推荐
Java 实现银行家算法(Swing 界面) 银行家算法是操作系统中非常重要的一种资源分配算法,用于避免死锁和饥饿的出现。下面我们将通过 Java 语言来实现银行家算法,并使用 Swing 库来设计一个友好的图形用户界面。 ...
Java Swing 是Java GUI(图形用户界面)库,用于构建桌面应用程序。在Swing中,多选下拉框通常由JComboBox类实现,但默认的JComboBox只支持单选。为了实现多选功能,我们需要扩展JComboBox或者使用第三方库,如JList...
java Swing多Jpanel仿安卓苹果桌面动态切换滑动效果
Java Swing实现的生命游戏Java Swing实现的生命游戏Java Swing实现的生命游戏 Java Swing实现的生命游戏Java Swing实现的生命游戏Java Swing实现的生命游戏 Java Swing实现的生命游戏Java Swing实现的生命游戏Java ...
在设计Swing应用时,提前规划界面结构,使用适当的容器和布局管理器,以及合理的继承关系,可以提高代码的可读性和维护性。 总之,Java Swing组件全演示旨在通过实际项目引导学习者深入理解Swing组件的使用和界面...
基于Java Swing实现答题系统的技术要点 本文将详细介绍基于Java Swing实现答题系统的技术要点,涵盖了GUI设计、事件处理、swing组件使用、Java图形化编程等多个方面的知识点。 一、GUI设计 在本文中,我们使用了...
DJNativeSwing.jar是纯Swing实现,而DJNativeSwing-SWT.jar则利用了Eclipse的SWT库来增强功能,提供更好的渲染效果。 接下来,我们将探讨如何在Java项目中集成这些库。首先,将这两个JAR文件添加到项目的类路径中。...
4. **GUI.java**:图形化界面的实现,可能使用了Java Swing或JavaFX库,显示当前系统状态,如资源分配情况、进程状态等,并提供交互功能,如启动算法、模拟进程请求等。 5. **Util.java**:辅助工具类,可能包含一些...
Java Swing 组件全演示源代码-Java Swing components entire demo source code
在Java Swing中实现PDF阅读器是一项技术挑战,涉及到对PDF文件格式的理解、IO操作、Swing组件的使用以及可能的第三方库集成。 PDF(Portable Document Format)是一种广泛使用的文件格式,用于存储文档,包括文本...
Java编程实现swing圆形按钮实例代码主要介绍了Java编程实现swing圆形按钮实例代码,涉及两个简单的Java实现按钮的代码,其中一个具有侦测点击事件的简单功能,具有一定借鉴价值,需要的朋友可以参考。 Swing是一个...
Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打...
JTable实现下拉动态加载数据,滑动动态加载数据,纯原生态java。
在“Java Swing教程”中,我们会详细讲解如何使用这些组件、布局管理器、事件处理和外观定制,通过实例代码演示如何一步步构建出美观且功能丰富的应用程序。无论是初学者还是有一定经验的开发者,都能从中学习到如何...
在Java编程语言中,实现GIF动画效果实际上是对一系列静态图像进行定时切换,模拟出动态效果。本示例主要展示了如何在Java环境下显示动态图片,特别是GIF格式的动画。以下将详细介绍实现这一功能的关键步骤和相关知识...
Java作为一种跨平台的编程语言,提供了丰富的库和API,如Java AWT(Abstract Window Toolkit)和Swing,用于创建图形用户界面,因此使用Java实现这样的算法对于学习和理解图形绘制非常有帮助。 在实际应用中,...
"基于Java swing组件实现简易计算器" 本文主要介绍了基于Java swing组件实现简易计算器的知识点,以下是相关知识点的总结: 1. JFrame组件:JFrame是Java swing组件中的一种顶层容器,用于创建一个窗口框架。通过...
java贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇...
本项目"JavaSwing实现简单计算器"就是利用这些组件来创建一个功能基础的计算器应用,可以处理基本的数学运算,包括加、减、乘、除,同时也支持负数、小数以及括号的使用。下面我们将详细探讨实现这样一个计算器所需...
Java Swing 是Java编程语言中用于构建桌面应用程序用户界面的一个库,它是Java Foundation Classes (JFC) 的一部分。Swing 提供了一系列组件,如按钮、文本框、菜单等,用于创建功能丰富的图形用户界面(GUI)。在...