分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter
package live.every.day.ProgrammingDesign.CodingInterviewGuide.StackAndQueue; /** * 用栈来求解汉诺塔问题 * * 【题目】 * 汉诺塔问题比较经典，这里修改一下游戏规则：限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必 * 须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。 * * 【要求】 * 用以下两种方法解决。 * 方法一：递归的方法； * 方法二：非递归的方法，用栈来模拟汉诺塔的三个塔。 * * 【难度】 * 困难 * * 【解答】 * 方法一：递归的方法。 * * 首先，如果只剩最上层的塔需要移动，则有如下处理： * １、如果希望从"左"移到"中"，打印"Move 1 from left to mid"。 * ２、如果希望从"中"移到"左"，打印"Move 1 from mid to left"。 * ３、如果希望从"中"移到"右"，打印"Move 1 from mid to right"。 * ４、如果希望从"右"移到"中"，打印"Move 1 from right to mid"。 * ５、如果希望从"左"移到"右"，打印"Move 1 from left to mid"和"Move 1 from mid to right"。 * ６、如果希望从"右"移到"左"，打印"Move 1 from right to mid"和"Move 1 from mid to left"。 * 以上过程就是递归的终止条件，也就是只剩上层塔时的打印过程。 * * 接下来，我们分析剩下多层塔的情况。 * 如果剩下N层塔，从最上到最下依次为1~N，则有如下判断： * １、如果剩下的N层塔都在"左"，希望全部移到"中"，则有三个步骤。 * １）将1~N-1层塔先全部从"左"移到"右"，明显交给递归过程。 * ２）将第N层塔从"左"移到"中"。 * ３）再将1~N-1层塔全部从"右"移到"中"，明显交给递归过程。 * ２、如果把剩下的N层塔从"中"移到"左"，从"中"移到"右"，从"右"移到"中"，过程与情况1同理，一样是分解为三步，在此不再详 * 述。 * ３、如果剩下的N层塔都在"左"，希望全部移到"右"，则有五个步骤。 * １）将1~N-1层塔先全部从"左"移到"右"，明显交给递归过程。 * ２）将第N层塔从"左"移到"中"。 * ３）将1~N-1层塔全部从"右"移到"左"，明显交给递归过程。 * ４）将第N层塔从"中"移到"右"。 * ５）最后将1~N-1层塔全部从"左"移到"右"，明显交给递归过程。 * ４、如果剩下的N层塔都在"右"，希望全部移到"左"，过程与情况3同理，一样是分解为五步，在此不再详述。 * * 以上递归过程经过逻辑化简之后的代码请参看如下代码中的hanoi1方法。 * * @author Created by LiveEveryDay */ public class HanoiByStack1 { public static int hanoi1(int num, String left, String mid, String right) { if (num < 1) { return 0; } return process(num, left, mid, right, left, right); } private 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.printf("Move 1 from %s to %s%n", from, to); return 1; } else { System.out.printf("Move 1 from %s to %s%n", from, mid); System.out.printf("Move 1 from %s to %s%n", mid, 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.printf("Move %d from %s to %s%n", num, from, to); 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.printf("Move %d from %s to %s%n", num, from, mid); int part3 = process(num - 1, left, mid, right, to, from); int part4 = 1; System.out.printf("Move %d from %s to %s%n", num, mid, to); int part5 = process(num - 1, left, mid, right, from, to); return part1 + part2 + part3 + part4 + part5; } } public static void main(String[] args) { int r = hanoi1(2, "left", "mid", "right"); System.out.printf("It will move %d steps.", r); } } // ------ Output ------ /* 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. */
