更改汉诺塔移动规则后递归求解

更改汉诺塔移动规则后递归求解

原问题描述
有三根杆左中右( left,mid , right ),在其中一杆( from )自下而上、由大到小按顺序放置num个圆盘。游戏的目标:把该杆的圆盘( from )全部移到另一杆 (to) 上,并仍保持原有顺序叠好。
操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上。
原问题解答点击这里(没有接触过汉诺塔问题的同学建议先看看原题求解)
约束移动规则
现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有N层的时候,打印最优移动过程和最优移动总步数。
举例
当圆盘有两个时,从 left 杆移到 right 杆,最上层的记为1,最下层的记为2,则打印:
Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.
递归方法
大致思想就是要移动N个圆盘,先移动上边N-1个圆盘,再移动剩下的那一个,整个过程交给递归。
递归头(结束递归):
首先,如果只剩最上层的圆盘需要移动,则有如下处理:
1.如果希望从“左”移到“中”,打印“Move 1 from left to mid”
2.如果希望从“中”移到“左”,打印“Move 1 from mid to left”
3.如果希望从“中”移到“右”,打印“Move 1 from mid to right”
4.如果希望从“右”移到“中”,打印“Move 1 from right to mid”
5.如果希望从“左”移到“右”,打印“Move 1 from left to mid”和“Move 1 from mid to right”
6.如果希望从“右”移到“左”,打印“Move 1 from right to mid”和“Move 1 from mid to left”
以上过程就是递归的终止条件,也就是只剩上层圆盘时的打印过程。

递归体:
接下来,我们分析剩下多个圆盘的情况。
如果剩下N个圆盘,从最上到最下依次为1~N,则有如下判断:

1.如果剩下的N个圆盘都在“左”, 希望全部移到“中”, 则有三个步骤。
1)将1~N-1个圆盘先全部从“左”移到“右”,明显交给递归过程。
2)将第N个圆盘从“左”移到“中”。
3)再将1~N-1个圆盘全部从“右”移到“中”,明显交给递归过程。

2.如果把剩下的N个圆盘从“中”移到“左”,从“中”移到“右”,从“右”移到“中”,
过程与情况1同理,一样是分解为三步,不再详述。

3.如果剩下的N个圆盘都在“左”,希望全部移到“右”,则有五个步骤。
1)将1~N-1个圆盘先全部从“左”移到“右”,明显交给递归过程。
2)将第N个圆盘从“左”移到“中”。
3)将1~N-1个圆盘全部从“右”移到“左”,明显交给递归过程。
4)将第N个圆盘从“中”移到“右”。
5)最后将1~N-1个圆盘全部从“左”移到“右”,明显交给递归过程。

4.如果剩下的N个圆盘都在“右”, 希望全部移到“左”, 过程与情况3同理,一样是.分解为五步,在此不再详述。

总结:假设有N个圆盘,什么时候结束递归?当只剩一个圆盘时(最上面那一个),根据它的起始杆和目标杆去移动,编码时总结移动规律,使代码更简便。递归方法分几类?两类,第一类,只要起始杆或者目标杆有一个是mid(中间杆),那么移动分为三步;第二类,其余情况移动分为五步。

代码展示

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();
System.out.print("终止位置: ");
String to = cs.next();
int n = Pro(num,"left","mid","right",from,to);
System.out.println("It will move "+n+" steps.");

}
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) { //递归头
if(from.equals(mid)||to.equals(mid)) {
System.out.println("move "+ num +" from "+ from +" to "+ to);
return 1;
}
else {
System.out.println("move "+ num +" from "+ from +" to "+mid);
System.out.println("move "+ num +" from "+ mid +" to "+to);
return 2;
}
}
//递归体
if(from.equals(mid)||to.equals(mid)) {
String another = (from.equals(left)||to.equals(left))?right:left;
int part1 = process(num-1,left,mid,right,from,another);
int part2 = 1;
System.out.println("move "+ num +" from "+ from +" to "+ mid);
int part3 = process(num-1,left,mid,right,another,to);
return part1+part2+part3; //共三步
}
else {
int part1 = process(num-1,left,mid,right,from,to);
int part2 = 1;
System.out.println("move "+ num +" from "+ from +" to "+ mid);
int part3 = process(num-1,left,mid,right,to,from);
int part4 = 1;
System.out.println("move "+ num +" from "+ mid +" to "+to);
int part5 = process(num-1,left,mid,right,from,to);
return part1+part2+part3+part4+part5; //共五步
}
}
}

对next和nextLine存在问题的点击这里

结果展示
在这里插入图片描述
个人经验总结,如有问题,欢迎指正讨论
( 思想源自左程云老师的程序员代码面试指南 )

作者:千辉

相关推荐

Python入门程序 函数应用(判断素数、递归求n的阶乘、x的n次方、最大最小值、插入排序法)

Python入门程序 函数应用(判断素数、递归求n的阶乘、x的n次方、最大最小值、插入排序法)

Python 树的遍历递归和循环

Java实现 LeetCode 662 二叉树最大宽度(递归)

1-2

leetcode_101.对称二叉树(递归思路)