基于Java中Stack类实现的Hanoi塔问题解决算法

基于Java中Stack类实现的Hanoi塔问题解决算法

• 算法伪代码
• 算法Java代码

算法伪代码

/*
 * @作者 : Mou Chaoli 
 * @算法简介 : 基于递归的思想的Hanoi塔问题解决器.算法中用整数表示圆盘的大小.
 *            数字越大那么圆盘的大小越大.
 * 
 */

伪代码

Algorithm :  solveHanoi(A,C,n)                   // 将A柱上的n个盘子按要求移到C柱上
     if n = 1 then moveHanoi(A,C)               // 将A柱上的1个盘子移到C柱上
     else solveHanoi(A,B,n-1)       
          moveHanoi(A,C)
          solveHanoi(B,C,n-1)

伪代码的说明

      I. A,B,C采用Stack类实现
      II. HanoiTowerSolver : Hanoi塔问题的解决类
      III. solveHanoi : HanoiTowerSolver的方法,用于解决Hanoi塔问题
      IV. moveHanoi : 移动操作

算法Java代码

public class HanoiTowerSolver
{	
	static int moveTimes = 0;
	Stack A = new Stack();
	Stack B = new Stack();
	Stack C = new Stack();
	
	public HanoiTowerSolver(int numOfPlates)
	{
		System.out.println("|Hanoi Tower|----> Generating A B C...");
		int tempNumOfPlates = numOfPlates;
		for(int i=0 ; i<numOfPlates ; i++)
		{
			A.push(tempNumOfPlates);
			tempNumOfPlates--;
		}
		System.out.println("|Hanoi Tower|----> Generating A B C Done.");
		System.out.println("|Hanoi Tower|----> Display A B C :");
		System.out.println("A: "+A);
		System.out.println("B: "+B);
		System.out.println("C: "+C);
	}
	
	
	public void solveHanoi(Stack origPillar,Stack finaPillar,Stack tempPillar,int n)
	{
		
		  if(n == 1)
	      {
	         moveHanoi(origPillar,finaPillar);
	         return;
	      }
	      else
          {
	    	 solveHanoi(origPillar,tempPillar,finaPillar,n-1);
	         moveHanoi(origPillar,finaPillar);
	         solveHanoi(tempPillar,finaPillar,origPillar,n-1);
	      }
	}
	
	public static void moveHanoi(Stack origPillar,Stack finaPillar)
	{
		//origPillar  remove *
		//finaPillar  add *	
		finaPillar.push(origPillar.pop());
        moveTimes++;
	}
	
	
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		System.out.println("|Hanoi Tower|----> Please enter the number of plates: ");
		int n = scanner.nextInt();
		HanoiTowerSolver Hanoi = new HanoiTowerSolver(n);
		
		Hanoi.solveHanoi(Hanoi.A,Hanoi.C,Hanoi.B,n);
		
		//检验结果
		//若算法成功,最终输入的C应该是从大到小排序的数列即其中的元素是与原始的A一致的.
		System.out.println("|Hanoi Tower|----> The final pillar C is: "+Hanoi.C);
		System.out.println("|Hanoi Tower|----> The total number of moves is: "+moveTimes);
	}

}

算法测试

|Hanoi Tower|----> Please enter the number of plates: 
6
|Hanoi Tower|----> Generating A B C...
|Hanoi Tower|----> Generating A B C Done.
|Hanoi Tower|----> Display A B C :
A: [6, 5, 4, 3, 2, 1]
B: []
C: []
|Hanoi Tower|----> The final pillar C is: [6, 5, 4, 3, 2, 1]
|Hanoi Tower|----> The total number of moves is: 63

本文地址：https://blog.csdn.net/Matlab16/article/details/109902300