Java使用递归法解决汉诺塔问题的代码示例
程序员文章站
2024-03-11 15:21:55
汉诺(hanoi)塔问题:古代有一个梵塔,塔内有三个座a、b、c,a座上有n个盘子,盘子大小不等,大的在下,小的在上(如图)。
有一个和尚想把这n个盘子从a座移到b座...
汉诺(hanoi)塔问题:古代有一个梵塔,塔内有三个座a、b、c,a座上有n个盘子,盘子大小不等,大的在下,小的在上(如图)。
有一个和尚想把这n个盘子从a座移到b座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用b座,要求打印移动的步骤。如果只有一个盘子,则不需要利用b座,直接将盘子从a移动到c。
- 如果有2个盘子,可以先将盘子1上的盘子2移动到b;将盘子1移动到c;将盘子2移动到c。这说明了:可以借助b将2个盘子从a移动到c,当然,也可以借助c将2个盘子从a移动到b。
- 如果有3个盘子,那么根据2个盘子的结论,可以借助c将盘子1上的两个盘子从a移动到b;将盘子1从a移动到c,a变成空座;借助a座,将b上的两个盘子移动到c。这说明:可以借助一个空座,将3个盘子从一个座移动到另一个。
- 如果有4个盘子,那么首先借助空座c,将盘子1上的三个盘子从a移动到b;将盘子1移动到c,a变成空座;借助空座a,将b座上的三个盘子移动到c。
java代码如下:
public class hanoi { public static void main(string[] args) { int disk = 3; //盘子 move(disk, 'a', 'b', 'c'); } /* * 根据题意,从上向下编号 => 1 ~ n */ /** * * @param topn 源塔顶的盘子编号 * @param from 从哪个塔移动 * @param inter 中介,过渡的塔 * @param to 目的塔 */ private static void move(int topn, char from, char inter, char to) { if (topn == 1) { system.out.println("disk 1 from " + from + " to " + to); } else { move(topn - 1, from, to, inter); system.out.println("disk " + topn + " from " + from + " to " + to); move(topn - 1, inter, from, to); } } }
out
disk 1 from a to c disk 2 from a to b disk 1 from c to b disk 3 from a to c disk 1 from b to a disk 2 from b to c disk 1 from a to c