JAVA - 四柱汉诺塔最优移动次序展示
本文是初学JAVA的自己做的一个小程序，关于面向对象的思想掌握的还不是很好，还没完全从c++过渡过来，尽情各位看官大佬批评指正。（中间汉诺塔的英文单词写错了//尴尬????）
各个类的功能和函数注释的很详细了就不详解了。
各类源代码下载链接：https://download.****.net/download/qq_40285036/10841684
运行截图：
主类
/*
* 主函数
*
* 包含了各个类之间的逻辑控制
*/
package Hanio;
import java.awt.Color;
import java.awt.Font;
import java.util.*;
import javax.swing.*;
import Hanio.Pillars;
import Hanio.Direction;
import Hanio.Direction.Step;
import Hanio.MyPillar;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.FocusEvent;
import java.awt.event.FocusListener;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.awt.event.WindowEvent;
import java.awt.event.WindowListener;
import java.awt.print.Book;
public class MainHanio extends JFrame {
public static int PlateN = 20;
// 主窗口的大小
public static int MainFrameWidth = 1800;
public static int MainFrameHeight = 900;
// 柱子的大小
public static int PillarWidth = 2;
public static int PillarHeight = 500;
// 柱子的位置
public static int PillarLocationAX = 200;
public static int PillarLocationAY = 200;
public static int PillarLocationBX = 600;
public static int PillarLocationBY = 200;
public static int PillarLocationCX = 1000;
public static int PillarLocationCY = 200;
public static int PillarLocationDX = 1400;
public static int PillarLocationDY = 200;
// 盘子的大小
public static int PlateHeight = 10;
// 主窗口
public static JFrame mainframe;
// 四个柱子
public static MyPillar pillarA;
public static MyPillar pillarB;
public static MyPillar pillarC;
public static MyPillar pillarD;
// 保存当前所有的盘子
public static Plate[] allPlate;
// 最有移动次序
public static List<Step> mySteps;
// 当前移动到了第几步
public static int pstep = 0;
// 为了方便逻辑控制 设置的一些全局变量
public static int FromX,FromY,EndX,EndY;
public static Plate CurrentPlate;
// 字体的格式，出现的所有字体都使用的这个格式
public static Font allFont = new Font("宋体",Font.BOLD,20);
// 文本框
public static JTextField plateTextField;
// 更新按钮和下一步按钮
public static JButton updataButton;
public static JButton nextStepButton;
// windows 窗口动作的监听类
static class windowsEvent implements WindowListener
{
@Override
public void windowActivated(WindowEvent arg0) {
// TODO Auto-generated method stub
}
@Override
public void windowClosed(WindowEvent arg0) {
// TODO Auto-generated method stub
}
@Override
public void windowClosing(WindowEvent arg0) {
// TODO Auto-generated method stub
System.out.println("this is be closed");
mainframe.dispose();
System.gc();
}
@Override
public void windowDeactivated(WindowEvent arg0) {
// TODO Auto-generated method stub
}
@Override
public void windowDeiconified(WindowEvent arg0) {
// TODO Auto-generated method stub
}
@Override
public void windowIconified(WindowEvent arg0) {
// TODO Auto-generated method stub
}
@Override
public void windowOpened(WindowEvent arg0) {
// TODO Auto-generated method stub
}
}
// 盘子移动，更新窗口的线程类
static class MyThread extends Thread
{
public void run()
{
int fx = FromX, fy = FromY;
int ex = EndX, ey = EndY;
Plate cur = CurrentPlate;
while(fx != ex || fy != ey)
{
int tx = (ex - fx);if(tx != 0) tx /= Math.abs(ex - fx);
int ty = (ey - fy);if(ty != 0) ty /= Math.abs(ey - fy);
fx += tx;fy += ty;
cur.setLocation(fx, fy);
mainframe.repaint();
try
{
//Thread.sleep(1);
}
catch(Exception e)
{
System.out.println("Thread Exception!");
}
}
}
}
// 键盘监听类
static class MyKey implements KeyListener
{
@Override
public void keyPressed(KeyEvent e) {
// TODO Auto-generated method stub
if(pstep == mySteps.size())
{
System.out.println("移动完成!!");
return;
}
movePlate(mySteps.get(pstep).begin, mySteps.get(pstep).end);
pstep++;
}
@Override
public void keyReleased(KeyEvent e) {
// TODO Auto-generated method stub
}
@Override
public void keyTyped(KeyEvent e) {
// TODO Auto-generated method stub
}
}
// 制作主窗口
public static void createFrame(int w,int h)
{
JPanel panel = new JPanel();
panel.setBackground(Color.DARK_GRAY);
mainframe = new JFrame();
mainframe.addKeyListener(new MyKey());
mainframe.setSize(w, h);
mainframe.setTitle("Hanio");
mainframe.setBackground(Color.DARK_GRAY);
mainframe.getLayeredPane().add(panel, Integer.MIN_VALUE);
mainframe.setVisible(true);
}
// 制作盘子
public static void createPlate(int n)
{
allPlate = new Plate[n];
for(int i = 1;i <= n;i++)
{
int w = 20 * (n - i) + 10;
int h = 10;
int x = PillarLocationAX - w / 2;
int y = PillarLocationAY + PillarHeight - i * 10;
allPlate[i - 1] = new Plate(w, h, x, y);
pillarA.addPlate(allPlate[i - 1]);
mainframe.getLayeredPane().add(allPlate[i - 1], new Integer(2));
}
}
// 制作柱子
public static void createPillars()
{
pillarA = new MyPillar(PillarWidth,PillarHeight);
pillarA.setLocation(PillarLocationAX, PillarLocationAY);
pillarB = new MyPillar(PillarWidth,PillarHeight);
pillarB.setLocation(PillarLocationBX, PillarLocationBY);
pillarC = new MyPillar(PillarWidth,PillarHeight);
pillarC.setLocation(PillarLocationCX, PillarLocationCY);
pillarD = new MyPillar(PillarWidth,PillarHeight);
pillarD.setLocation(PillarLocationDX, PillarLocationDY);
pillarA.setVisible(true);
pillarB.setVisible(true);
pillarC.setVisible(true);
pillarD.setVisible(true);
mainframe.getLayeredPane().add(pillarA, new Integer(3));
mainframe.getLayeredPane().add(pillarB, new Integer(3));
mainframe.getLayeredPane().add(pillarC, new Integer(3));
mainframe.getLayeredPane().add(pillarD, new Integer(3));
}
// 移动方向和当前柱子的映射
public static MyPillar choosePillar(Pillars A)
{
switch(A)
{
case A:return pillarA;
case B:return pillarB;
case C:return pillarC;
case D:return pillarD;
}
return pillarA;
}
// 利用多线程更新盘子
public static void movePlate(Pillars A,Pillars B)
{
MyPillar from = choosePillar(A), to = choosePillar(B);
Plate plate = from.getTop();
int ex = to.getLocation().x - plate.getWidth() / 2;
int ey = to.getLocation().y + to.getHeight() - 10 * (to.getPlateCouner() + 1);
System.out.println(pillarB.getPlateCouner());
System.out.println(pillarC.getPlateCouner());
FromX = plate.getLocation().x;
FromY = plate.getLocation().y;
EndX = ex;
EndY = ey;
CurrentPlate = plate;
to.addPlate(plate);
from.removePlate();
new MyThread().start();
}
// 制作标签
public static void createLabel(int x,int y,int w,int h, String text)
{
JLabel plateCounter = new JLabel();
plateCounter.setSize(w,h);
plateCounter.setFocusable(false);
plateCounter.setLocation(x,y);
plateCounter.setText(text);
plateCounter.setVisible(true);
plateCounter.setFont(allFont);
plateCounter.addFocusListener(new FocusListener(){
@Override
public void focusLost(FocusEvent e) {
//失去焦点执行的代码
System.out.println("TextField 失去焦点");
}
@Override
public void focusGained(FocusEvent e) {
//获得焦点执行的代码
}
});
mainframe.getLayeredPane().add(plateCounter, Integer.MIN_VALUE);
mainframe.repaint();
}
// 制作输入框
public static void createTextBox(int x,int y,int w,int h)
{
plateTextField = new JTextField();
plateTextField.setFont(allFont);
plateTextField.setText("20");
plateTextField.setLocation(x,y);
plateTextField.setSize(w,h);
plateTextField.setVisible(true);
mainframe.getLayeredPane().add(plateTextField, Integer.MIN_VALUE);
}
// 制作按钮
public static void createUpdataButton(int x,int y,int w,int h,String text)
{
updataButton = new JButton();
updataButton.setText(text);
updataButton.setFocusPainted(false);
updataButton.setFocusable(false);
updataButton.setSize(w,h);
updataButton.setLocation(x,y);
updataButton.setFont(allFont);
updataButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e)
{
if(plateTextField.getText().isEmpty())
{
plateTextField.setText("不能为空!");
return;
}
String str = plateTextField.getText();
for(int i = 0;i < str.length();i++)
{
if(str.charAt(i) < '0' || str.charAt(i) > '9')
{
plateTextField.setText("数字不合法");
return;
}
}
resetFrame();
//plateTextField.setEditable(false);
//plateTextField.setEditable(true);
}
});
updataButton.setVisible(true);
mainframe.getLayeredPane().add(updataButton, Integer.MIN_VALUE);
}
// 制作按钮
public static void createNextStepButton(int x,int y,int w,int h,String text) {
nextStepButton = new JButton();
nextStepButton.setLocation(x,y);
nextStepButton.setSize(w,h);
nextStepButton.setText(text);
//nextStepButton.addActionListener(new ActionListener() {
// public void actionPerformed(ActionEvent e)
// {
// if(pstep == mySteps.size())
// {
// System.out.println("移动完成!!");
// return;
// }
// movePlate(mySteps.get(pstep).begin, mySteps.get(pstep).end);
// pstep++;
// }
//});
nextStepButton.setFont(allFont);
nextStepButton.setFocusable(true);
nextStepButton.addKeyListener(new MyKey());
nextStepButton.setVisible(true);
mainframe.getLayeredPane().add(nextStepButton, Integer.MIN_VALUE);
}
// 释放当前资源
public static void disposeAll()
{
mySteps.clear();
for(int i = 0;i < PlateN;i++)
mainframe.getLayeredPane().remove(allPlate[i]);
mainframe.getLayeredPane().remove(pillarA);
mainframe.getLayeredPane().remove(pillarB);
mainframe.getLayeredPane().remove(pillarC);
mainframe.getLayeredPane().remove(pillarD);
mainframe.repaint();
}
// 重置窗口
public static void resetFrame()
{
disposeAll();
pstep = 0;
PlateN = Integer.parseInt(plateTextField.getText());
Direction dir = new Direction(PlateN);
dir.getOptmalMove();
dir.getMoveSteps4(PlateN, Pillars.A, Pillars.B, Pillars.C, Pillars.D);
mySteps = dir.getSteps();
createPillars();
createPlate(PlateN);
}
public static void main(String[] args)
{
//得到最有移动次序
Direction dir = new Direction(PlateN);
dir.getOptmalMove();
dir.getMoveSteps4(PlateN, Pillars.A, Pillars.B, Pillars.C, Pillars.D);
mySteps = dir.getSteps();
//初始化前台
createFrame(MainFrameWidth, MainFrameHeight);
createPillars();
createPlate(PlateN);
createLabel(0,720,180,30,"请输入盘子数量:");
createTextBox(180, 720, 70, 30);
createUpdataButton(250,720,100, 30, "重置");
createNextStepButton(350,720,100,30,"下一步");
// 增加windows的监听事件
mainframe.addWindowListener(new windowsEvent());
mainframe.repaint();
}
}
方向类
/*方向移动判断类
* 四柱汉诺塔的移动采用的是最少移动次数
* 大概思路是先用动态规划的思想求出最优值
* 在递归寻找最优解也就是最优移动次序
*
* 下面的程序还包含了三柱汉诺塔的移动
*/
package Hanio;
import Hanio.Pillars;
import java.awt.Point;
import java.util.*;
public class Direction {
// 记录移动的方向 从begin柱子到end柱子
public static class Step{
public Pillars begin;
public Pillars end;
public Step(Pillars a,Pillars b)
{
begin = a;end = b;
}
}
// 有n个盘子
public static int n;
// dp vis 动态规划所用
public static int[] dp;
public static int[] vis;
// 记录最优移动次序
public static List<Step> Steps = new ArrayList<Step>();
// 初始化 tmpn 是盘子的个数
public Direction(int tmpn)
{
n = tmpn;
dp = new int[n + 2];
vis = new int[n + 2];
}
// 动态规划求解最优值
public static void getOptmalMove()
{
dp[1] = 1;
dp[2] = 3;
for(int i = 3;i <= n;i++)
{
dp[i] = 0x3f3f3f3f;
for(int k = 1;k < i;k++)
{
// 最优子结构
int tmp = (int) (2 * dp[k] + Math.pow(2, i - k) - 1);
if (tmp < dp[i])
{
dp[i] = tmp;
vis[i] = k;
}
}
System.out.println(dp[i]);
}
}
// 移动一个盘子， 保存移动方向
public static void moveOneStep(Pillars A,Pillars B)
{
Steps.add(new Step(A, B));
}
// 得到三柱汉诺塔的移动方向
public static void getMoveSteps3(int k, Pillars A,Pillars B,Pillars C)
{
if(k == 1)
{
moveOneStep(A, C);
return;
}
getMoveSteps3(k - 1,A, C, B);
moveOneStep(A, C);
getMoveSteps3(k - 1,B, A, C);
}
// 得到四柱汉诺塔的移动方向
public static void getMoveSteps4(int k,Pillars A,Pillars B,Pillars C,Pillars D)
{
if(k == 1) {
moveOneStep(A, D);
return;
}
if(k == 2)
{
moveOneStep(A, B);
moveOneStep(A, D);
moveOneStep(B, D);
return;
}
getMoveSteps4(vis[k], A, C, D, B);
getMoveSteps3(k - vis[k], A, C, D);
getMoveSteps4(vis[k], B, A, C, D);
}
// 返回移动次序
public static List<Step> getSteps()
{
return Steps;
}
// 测试函数
public void printSteps()
{
for(Step step : Steps)
{
System.out.println(step.begin + "->" + step.end);
}
}
}
盘子类
/*
* 盘子类
* 记录每个盘子的状态
* 例如：在哪个柱子，盘子的颜色，大小
*/
package Hanio;
import java.awt.Color;
import java.awt.Graphics;
import java.util.Random;
import javax.swing.*;
public class Plate extends JPanel{
// 为了产生随机颜色
public static Color[] color = {Color.black,Color.BLUE, Color.decode("#800080"),Color.GREEN,Color.pink
,Color.MAGENTA,Color.RED,Color.CYAN,Color.decode("#4B0082"),Color.ORANGE};
public void mySetSize(int w,int h)
{
this.setSize(w, h);
this.setVisible(true);
}
public void mySetLocation(int x,int y)
{
this.setLocation(x, y);
}
public void myPaint() {
}
public Plate() {
}
// 初始化
public Plate(int w,int h,int x,int y)
{
Random rand = new Random();
// 生成随机颜色
this.setBackground(color[rand.nextInt(10)]);
this.setLocation(x, y);
this.setSize(w, h);
this.setVisible(true);
}
}
柱子类
/*
* 柱子类
* 主要是记录当前柱子上的盘子
*/
package Hanio;
import Hanio.Pillars;
import Hanio.Plate;
import java.awt.Color;
import java.util.*;
import javax.swing.*;
public class MyPillar extends JPanel {
// 记录当前柱子上的盘子
public List<Plate> pillars = new ArrayList<Plate>();;
public MyPillar() {}
public MyPillar(int w, int h) {
this.setSize(w, h);
this.setBackground(Color.BLUE);
this.setVisible(true);
}
// 增加一个盘子
public void addPlate(Plate plate)
{
pillars.add(plate);
}
public void removePlate()
{
if(pillars.size() == 0)
{
System.out.println("No Plate!");
return;
}
pillars.remove(pillars.size() - 1);
}
// 得到柱子上的最上面的一个盘子
public Plate getTop()
{
return pillars.get(pillars.size() - 1);
}
// 得到柱子上盘子的个数
public int getPlateCouner()
{
return pillars.size();
}
}
柱子的枚举
package Hanio;
// 四个柱子的枚举 ，方便传参
public enum Pillars {
A,B,C,D
}