软件编程
位置：首页>> 软件编程>> java编程>> Java使用递归法解决汉诺塔问题的代码示例

Java使用递归法解决汉诺塔问题的代码示例

作者：goldensun　　发布时间：2023-09-05 20:31:28　

标签：Java,递归

汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有n个盘子，盘子大小不等，大的在下，小的在上（如图）。

Java使用递归法解决汉诺塔问题的代码示例

有一个和尚想把这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
0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com