递归方法解决汉诺塔问题(举例说明)

递归方法解决汉诺塔问题(举例说明)

问题描述
有三根杆左中右( 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层的时候,打印最优移动过程和最优移动总步数。(点击这里查看)

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

作者:千辉

相关推荐

ubuntu 禁止外部ping和允许ping方法

在这里插入图片描述

jdk1.8之后的String.intern()方法内存分析

Python pandas 的DataFrame对象在使用to_csv()方法时,如何实现数据追加写入文本的功能?

Python object类中的特殊方法代码讲解