Java 实现汉诺塔 Hanoi 算法：递归、非递归和规律实现
187 浏览量
更新于2024-08-31
收藏 63KB PDF 举报
"java 汉诺塔Hanoi递归、非递归(仿系统递归)和非递归规律实现代码"
汉诺塔（Hanoi）算法是经典的递归算法，通过三个函数，分别对Hanoi进行递归、非递归和非递归规律实现。下面是对标题、描述、标签和部分内容的知识点详细解释：
一、汉诺塔（Hanoi）算法概述
汉诺塔（Hanoi）算法源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
二、递归实现
递归实现是指通过函数自己调用自己来解决问题。汉诺塔递归实现可以通过以下步骤来完成：
1.将问题分解成小问题，直到问题足够小，可以直接解决。
2.解决小问题，然后将结果组合起来，得到最终的解决方案。
在 Java 代码中，递归实现函数为 `play_recursive`，它将问题分解成小问题，直到问题足够小，可以直接解决。然后，将结果组合起来，得到最终的解决方案。
三、非递归实现（模仿递归思想）
非递归实现（模仿递归思想）是指通过循环来模仿递归思想。汉诺塔非递归实现可以通过以下步骤来完成：
1.使用栈来存储问题的状态。
2.使用循环来模仿递归思想，直到问题解决。
在 Java 代码中，非递归实现函数为 `play_non_recursive`，它使用栈来存储问题的状态，然后使用循环来模仿递归思想，直到问题解决。
四、非递归实现（根据Hanoi规律）
非递归实现（根据Hanoi规律）是指通过分析汉诺塔规律来解决问题。汉诺塔规律是指：
1.如果只有一个圆盘，那么直接移动到目标柱子上。
2.否则，将最大的圆盘移到中间柱子上，然后将剩余的圆盘移到目标柱子上。
在 Java 代码中，非递归实现函数为 `play_regular`，它通过分析汉诺塔规律来解决问题。
五、Java 代码分析
Java 代码中，主要包括三个函数：`play_recursive`、`play_non_recursive` 和 `play_regular`。这些函数分别对Hanoi进行递归、非递归和非递归规律实现。
六、总结
汉诺塔（Hanoi）算法是经典的递归算法，通过三个函数，分别对Hanoi进行递归、非递归和非递归规律实现。递归实现是指通过函数自己调用自己来解决问题，非递归实现是指通过循环来模仿递归思想或分析汉诺塔规律来解决问题。java 代码中，三个函数分别对Hanoi进行递归、非递归和非递归规律实现。
java 汉诺塔汉诺塔Hanoi递归、非递归递归、非递归(仿系统递归仿系统递归)和非递归规律和非递归规律 实实
现代码现代码
汉诺塔（Hanoi） 算法Java实现。通过三个函数，分别对Hanoi进行递归、非递归和非递归规律实现。
程序如下：
复制代码 代码如下:
View Code
/*
* Hanoi塔游戏 问题描述：
* 汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。
* 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照
* 大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小
* 顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在
* 三根柱子之间一次只能移动一个圆盘。
*
* fuction:实现 hanoi塔
* 1.递归实现
* 2.非递归实现
* author:iGeneral
* date:2013.04.26
*
* expe:
* 1.注意：塔的状态:当status=1时，表示可以直接将该Disk移动到目标塔
* 而不是用Disk的id来判断输出
* 2.System.out.println();
System.out.println((int)3.3%3);
没有(int)时，输出：0.299999
加上(int)后，输出：0
*/
package part03.chapter10;
import java.util.Scanner;
public class _2exercise {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入Hanoi碟子的数量：");
int diskNum = scanner.nextInt();
Hanoi hanoi = new Hanoi();
System.out.println("递归实现：");
hanoi.play_recursive(diskNum, 'A', 'B', 'C');
System.out.println("非递归实现(模仿递归思想)：");
hanoi.play_non_recursive(diskNum);
System.out.println("非递归实现(根据Hanoi规律)：");
hanoi.play_regular(diskNum);
}
}
class Hanoi {
// 递归实现
public void play_recursive(int num, char A, char B, char C) {
if (num == 1) {
System.out.println(A + " -> " + C);
return;
} else {
play_recursive(num - 1, A, C, B);
System.out.println(A + " -> " + C);
play_recursive(num - 1, B, A, C);
}
下载后可阅读完整内容，剩余3页未读，立即下载
2011-03-27 上传
2012-08-22 上传
2024-06-13 上传
2023-09-06 上传
2023-04-26 上传
2024-10-11 上传
2023-11-19 上传
2024-10-12 上传
