JAVA - 四柱汉诺塔最优移动次序展示

深藏阁楼爱情的钟 2022-03-25 01:50 142阅读 0赞

本文是初学JAVA的自己做的一个小程序，关于面向对象的思想掌握的还不是很好，还没完全从c++过渡过来，尽情各位看官大佬批评指正。（中间汉诺塔的英文单词写错了//尴尬?）

各个类的功能和函数注释的很详细了就不详解了。如果有想要学习算法【获得移动的最少步数】就只看方向类就可以。

各类源代码下载链接：[https://download.csdn.net/download/qq\_40285036/10841684][https_download.csdn.net_download_qq_40285036_10841684]

运行演示：  
![在这里插入图片描述][20190628090805113.gif]  
**主类**

/*
     * 主函数
     * 
     * 包含了各个类之间的逻辑控制
     */
    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
    }

[https_download.csdn.net_download_qq_40285036_10841684]: https://download.csdn.net/download/qq_40285036/10841684
[20190628090805113.gif]: /images/20220325/f7c423b5b1c94092b7bff19b2437cd8d.png