Java函数实现递归算法求解汉诺塔问题
汉诺塔问题是经典的递归问题，它起源于印度的传说，后被法国数学家爱德华·卢卡斯（Edouard Lucas）研究。在游戏中，有三根柱子（A、B、C），其中A柱上有n个大小不等的盘子，盘子从下到上按从大到小顺序摆放。现在要求把A柱上的所有盘子移动到C柱上，移动过程中可以借助B柱，但是要求移动的时候小的盘子不能放在大的盘子上，问题是如何实现这个过程。以下为Java函数实现递归算法求解汉诺塔问题的方法。
1. 首先定义hanoi函数，函数输入参数为盘子数量n，柱子A、B、C的序列号分别为1、2、3，其中A是起始柱，C是目标柱，B是中间柱。
public static void hanoi(int n, int A, int B, int C) {
}
2. 其次判断递归结束条件，当只有一个盘子时，只需将其从A柱移到C柱即可。
if (n == 1) {
System.out.println("Move disk " + n + " from " + A + " to " + C);
}
3. 当有多个盘子时，递归调用hanoi函数。首先将上面的n-1个盘子从A柱移到B柱上，然后将第n个盘子从A柱移到C柱上，最后将B柱上的上面的n-1个盘子移到C柱上即可。
else {
hanoi(n-1, A, C, B);
System.out.println("Move disk " + n + " from " + A + " to " + C);
hanoi(n-1, B, A, C);
}
4. 在主函数中调用hanoi函数，传入盘子数量n和柱子序列号1、2、3。
public static void main(String[] args) {
int n = 3;
hanoi(n, 1, 2, 3);
}
完整代码如下：
public class Hanoi {
public static void hanoi(int n, int A, int B, int C) {
if (n == 1) {
System.out.println("Move disk " + n + " from " + A + " to " + C);
}
else {
hanoi(n-1, A, C, B);
System.out.println("Move disk " + n + " from " + A + " to " + C);
hanoi(n-1, B, A, C);
}
}
public static void main(String[] args) {
int n = 3;
hanoi(n, 1, 2, 3);
}
}