博客

递归方法解决汉诺塔问题（举例说明）

问题描述


有三根杆左中右（ left，mid , right )，在其中一杆( from )自下而上、由大到小按顺序放置num个金盘。游戏的目标：把该杆的金盘( from )全部移到另一杆 (to) 上，并仍保持原有顺序叠好。

操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上。

如图：将左边杆子上num个圆盘移到右边杆子上。

由上到下为1， 2 ，3， … ，num-1， num个盘子





举例


from为left, to为mid，num为3. （即从左边移动三个盘子到中间）

移动方法：

move 1 from left to mid

move 2 from left to right

move 1 from mid to right

move 3 from left to mid

move 1 from right to left

move 2 from right to mid

move 1 from left to mid


递归方法


递归头（递归的最底层）：当num剩一个时直接将这一个移到目标to杆子上，然后返回。

递归体：有from（起始杆）和to（终止杆），设另一个杆子为another，将num-1个圆盘从from移到another，再将剩余一个最大的圆盘num移到to，最后将num-1个圆盘移到to…


输入以及输出


输入移动盘子数量num，以及起始杆from和目标杆to；

输出移动方法和移动次数。


参考代码

import java.util.Scanner;
public class HanNuoTa {
 public static void main(String[] args) {
  Scanner cs = new Scanner(System.in);
  System.out.print("盘子个数： "); 
  int num =cs.nextInt();           //输入盘子个数
  System.out.print("起始位置： ");
  String from = cs.next();         //输入起始杆，from，mid 或 right
  System.out.print("终止位置： ");
  String to = cs.next();           //输入目标杆，from，mid 或 right
  System.out.println(Pro(num,"left","mid","right",from,to));
  
 }
  static int Pro(int num, String left, String mid, String right, String from, String to) {
  if(num<1) return 0;
  else return process(num,left,mid,right,from,to);
  }
  static int process(int num, String left, String mid, String right, String from, String to) {
   if(num==1) {
    System.out.println("move "+ num +" from "+ from +" to "+ to);
    return 1;  //返回移动次数
   }
   //下面为递归体，先要找到除from和to的另一个杆子
   //我分为两步去找，如果from和to有一个是mid杆子，则另一个杆子不是left就是right
   //否则，另一个杆子就是mid
   //然后开始移动
   if(from.equals(mid)||to.equals(mid)) {
    String another = (from.equals(left)||to.equals(left))?right:left;
    //找到另一个杆子another
    int part1 = process(num-1,left,mid,right,from,another);
    //将num-1个圆盘从from移到another
    int part2 = 1;
    System.out.println("move "+ num +" from "+ from +" to "+ mid);
    //将剩余一个最大的圆盘num移到to
    int part3 = process(num-1,left,mid,right,another,to);
    //最后将num-1个圆盘从another移到to
    return part1+part2+part3;  //返回移动次数
   }
   else { 
    //此时另一个圆盘就是mid
    int part1 = process(num-1,left,mid,right,from,mid);
    int part2 = 1;
    System.out.println("move "+ num +" from "+ from +" to "+ to);
    int part3 = process(num-1,left,mid,right,mid,to);
    return part1+part2+part3;
   }
  }
}

运行





思考


现修改游戏规则:现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。（

点击这里查看

）

个人学习经验总结，如有问题，欢迎指正。