[PHP知识库]用递归的办法神奇的解决汉诺塔问题

汉诺塔问题

汉诺塔问题，这个名词我们可能不熟悉，但是观看上图我们很可能都曾经了解过甚至玩过，他的规则就是有3根柱子A，B，C。A柱子上由上至下依次由小至大排列的圆盘。把A柱子上的圆盘借B柱子全部移动到C柱子上，并且移动的过程始终是小的圆盘在上，大的在下。
我们用递归的方式来解这道题，先来定义一个函数

public void hanoi(int n, char A, char B, char C)

他表示的是把n个圆盘从A借助B成功的移动到C。
递归的条件，一个是终止条件，一个是递归调用自己。
首先是终止条件：当n等于1的时候，也就是A柱子上只有一个圆盘的时候，我们直接把A柱子上的圆盘移动到C柱子上即可。

if(n==1){
            System.out.println("从"+A+"移动到"+C);
            return;
        }

然后是递归调用自己
如果n不等于1，我们要分3步，
1、先把n-1个圆盘从A借助C成功的移动到B
2、然后再把第n个圆盘从A移动到C
3、最后再把n-1个圆盘从B借助A成功的移动到C

hanoi(n, ‘A’, ‘B’, ‘C’)表示的是把n个圆盘从A借助B成功的移动到C
所以hanoi(n-1, ‘A’, ‘C’, ‘B’)就表示的是把n-1个圆盘从A借助C成功的移动到B
hanoi(n-1, ‘B’, ‘A’, ‘C’)就表示的是把n-1个圆盘从B借助A成功的移动到C
所以上面3步如果用代码就可以这样来表示
1，hanoi(n-1, ‘A’, ‘C’, ‘B’)
2，System.out.println(“从” + A + “移动到” + C);
3，hanoi(n-1, ‘B’, ‘A’, ‘C’)
最终代码如下：

public static void hanoi(int n,char A,char B,char C){
        if(n==1){
            System.out.println("从"+A+"移动到"+C);
            return;
        }
        hanoi(n-1,A,C,B);
        System.out.println("从"+A+"移动到"+C);
        hanoi(n-1,B,A,C);
    }

然后实际测试：

测试结果：

你可以实操一下，一定是可以成功的。
一个自己可能玩很久都成功不了的游戏，只要了解递归，就能用计算机轻松完成，是不是很神奇！