汉诺塔与二进制、满二叉树的千丝万缕

迷南。 2023-10-08 23:49 5阅读 0赞

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

### 汉诺塔递归算法 ###

3阶汉诺塔移动步骤：

![image][]

#### 汉诺塔解法思路 ####

一个规模为n的问题，可以拆成互相独立且与原问题形式相同的子问题的问题，可以采用**递归**方式解决子问题，然后将各个子问题的解合并得到原问题的解（分而治之思想）。

**理解过程**

如图，3阶的一共需要七步，

因为盘子3是最大的，所以所有盘子都可放在它上面，所以我们可以忽略盘子3，既是把“前三步”看做一个整体，完成2阶移动即可，移动目标是从A移动到B（伪C）；

接着执行第四步，从A移到C，此时最大的盘就完成移动了，因为是最大，所以所有盘子都可以移到C，可以忽略盘子3，此时，后续的操作可以将3阶看成2阶来处理了；

“前三步”将盘子1和2，从A移到B了，托盘A和托盘B是相对来说的，此时的托盘B可以看做是托盘A，所以“后三步”2阶移动和普通的2阶移动步骤一样，移动目标是B（伪A）到C。

从上面分析可以知道，**所有的移动都是从“A”移动到“C”**，只是**第一大步**和**最后一大步**是要交换位置，分别是C交换成B、B交换从A（看代码不太懂时，回来看这里）

当n=1时，只需托盘A直接移到托盘C（这是递归问题的出口）； 当n>1时，需要借助另一托盘来移动，将n个圆盘由A移到C上可以分解为以下几个步骤： (1) 将A上的n-1个圆盘，借助C，**从A移到B**上; (2) 把A上第n个圆盘，直接**从A移到C**上; (3) 将B上的n-1个圆盘，借助A，**从B移到C**上。

递归方式实现的汉诺塔（Java版）：

public class Hanoi {
        
        // 阶数
        private static int n = 4;
        //验证汉诺塔移动次数
        private static int sum=0;
        public static void main(String[] args) {
        
            System.out.println(String.format("%s层汉诺塔的移动顺序：", n));
            move(n, 'A','B','C');
            System.out.println("汉诺塔移动次数："+sum);
        }
    
        /**
         * (n-1) A -> B
         *   n   A -> C
         * (n-1) B -> C
         * 
         * 结束条件为：当n=1 时， A -> C
         */
        public static void move(int n,char A, char B, char C) {
        
            if(n==1) {
        
                System.out.println(A + " -> " + C);
                sum++;
            }
            else {
        
                move(n-1, A, C, B);//每次都是输出A->C，所以要看到A->B，就需要将B和C交换
    
                if(n==Hanoi.n)
                    System.out.println("前面完成(n-1)层：从A移动到B");
                System.out.println(A + " -> " + C);
                sum++;
                if(n==Hanoi.n)
                    System.out.println("完成第(n)层：从A移动到C");
    
                move(n-1, B, A, C);//每次都是输出A->C，所以要看到B->C，就需要将A和B交换
                if(n==Hanoi.n)
                    System.out.println("前面完成(n-1)层：从B移动到C");
            }
        }
    
    }

执行结果：

> 3层汉诺塔的移动顺序：
> 
> A -> C
> 
> A -> B
> 
> C -> B
> 
> 前面完成(n-1)层：从A移动到B
> 
> A -> C
> 
> 完成第(n)层：从A移动到C
> 
> B -> A
> 
> B -> C
> 
> A -> C
> 
> 前面完成(n-1)层：从B移动到C
> 
> 汉诺塔移动次数：7

先完成(n-1)层：从A移动到B，

再完成第(n)层：从A移动到C，

最后完成(n-1)层：从B移动到C。

#### 通过数学推导汉诺塔移动次数 ####

递归算法可以通过递归式的方式去推导证明，现在通过递归式推导汉诺塔移动次数。

假定n是盘子的数量，T(n)是移动n个圆盘的移动次数。

当n=1时，T(1)=1

当n=2时，T(2)=2T(1)+1

当n=3时，T(3)=2T(2)+1

得**汉诺塔递归式**：

T ( n ) = \{ 2 T ( n − 1 ) + 1 n ≥ 1 1 n = 1 T(n)= \\begin\{cases\} 2T(n-1)+1\\quad n≥1 \\\\ \\quad 1 \\quad n=1 \\end\{cases\} T(n)=\{ 2T(n−1)\+1n≥11n=1

由递归式求n阶汉诺塔移动次数：

由递归式可知：

![image][image 1]

又因当n=1时，T(1)=1，得：

T ( n ) = 2 n − 1 + 2 n − 2 + . . . + 2 1 + 2 0 = 2 n − 1 T(n)=2^\{n-1\}+2^\{n-2\}+...+2^1+2^0=2^n-1 T(n)=2n−1\+2n−2\+...\+21\+20=2n−1

解得n阶汉诺塔移动次数为： 2 n − 1 2^n-1 2n−1次。

### 汉诺塔与二进制 ###

公式

T ( n ) = 2 n − 1 + 2 n − 2 + . . . + 2 1 + 2 0 = 2 n − 1 T(n)=2^\{n-1\}+2^\{n-2\}+...+2^1+2^0=2^n-1 T(n)=2n−1\+2n−2\+...\+21\+20=2n−1

这就像是n位二进制的和，最终得到n位二进制的最大值（全1）  
所以有，**n阶汉诺塔移动次数等于n位二进制得最大值**，如：4阶汉诺塔移动次数为 1000 0 2 − 1 2 = 111 1 2 = 1 5 10 10000\_2-1\_2=1111\_2=15\_\{10\} 100002−12=11112=1510

每个盘子的移动次数，观察下图：

![image][image 2]

如图可知，每个盘子移动总次数刚好相反，

所以，n阶汉诺塔的第i个盘子总的移动次数为：

2 ( n − i + 1 ) − 1 = 2 n − i 2^\{(n-i+1)-1\}=2^\{n-i\} 2(n−i\+1)−1=2n−i

3阶汉诺塔图解与二进制关系

![image][image 3]

### 汉诺塔与满二叉树 ###

递归算法会有相对应的递归树，而汉诺塔的递归树刚好是满二叉树，即所有分支结点都有两个叶子结点。

调整汉诺塔对算法代码的输出信息后：

public class Hanoi {
        
        // 阶数
        private static int n = 3;
        public static void main(String[] args) {
        
            System.out.println(String.format("%s层汉诺塔的移动顺序：", n));
            int sum = moveTree(n, 'A','B','C');
            System.out.println("汉诺塔移动次数："+sum);
        }
    
        /**
         * 汉诺塔与满二叉树
         * (n-1) A -> B
         *   n   A -> C
         * (n-1) B -> C
         * 
         * 结束条件为：当n=1 时， A -> C
         */
        public static int moveTree(int n,char A, char B, char C) {
        
            if(n==1)
                System.out.println(String.format("第 %s 层(叶子节点)：%s -> %s",n, A, C));
            else {
        
                moveTree(n-1, A, C, B);//每次都是输出A->C，所以要看到A->B，就需要将B和C交换
    
                if(n==Hanoi.n)
                    System.out.println(String.format("第 %s 层(根节点)：%s -> %s", n, A, C));
                else
                    System.out.println(String.format("第 %s 层(分支结点)：%s -> %s", n, A, C));
    
                moveTree(n-1, B, A, C);//每次都是输出A->C，所以要看到B->C，就需要将A和B交换
            }
            //汉诺塔的移动次数为: 2^n-1
            return (int) Math.pow(2, n)-1;
        }
    
    }

> 3层汉诺塔的移动顺序：
> 
> 第 1 层(叶子节点)：A -> C
> 
> 第 2 层(分支结点)：A -> B
> 
> 第 1 层(叶子节点)：C -> B
> 
> 第 3 层(根节点)：A -> C
> 
> 第 1 层(叶子节点)：B -> A
> 
> 第 2 层(分支结点)：B -> C
> 
> 第 1 层(叶子节点)：A -> C
> 
> 汉诺塔移动次数：7

3阶汉诺塔对应的满二叉树：

![image][image 4]

3阶汉诺塔的移动步骤为满二叉树的**中序遍历**：AC、AB、CB、AC、BA、BC、AC

从输出结果可以看到，汉诺塔**盘子编号**对应满二叉树**自底向上**计算的**层号**，如：1号盘子的移动对应是叶子节点，最底层盘子对应根节点。

为了更好理解，可以写成这样：

public static int moveTree(int n,char A, char B, char C) {
        
            if(n==1)
                System.out.println(String.format("第 %s 层(叶子节点)：%s -> %s",Hanoi.n-n+1, A, C));
            else {
        
                moveTree(n-1, A, C, B);//每次都是输出A->C，所以要看到A->B，就需要将B和C交换
    
                if(n==Hanoi.n)
                    System.out.println(String.format("第 %s 层(根节点)：%s -> %s", Hanoi.n-n+1, A, C));
                else
                    System.out.println(String.format("第 %s 层(根节点)：%s -> %s", Hanoi.n-n+1, A, C));
    
                moveTree(n-1, B, A, C);//每次都是输出A->C，所以要看到B->C，就需要将A和B交换
            }
            //汉诺塔的移动次数为: 2^n-1
            return (int) Math.pow(2, n)-1;
        }

汉诺塔递归实现与二叉树中序遍历的递归实现，在代码实现上很类似

public static void inorder(TreeNode root) {
        
        if (root == null)
            return;
        inorder(root.left);
        System.out.print(root.val);
        inorder(root.right);
    }

汉诺塔的移动步骤可以用满二叉树的中序遍历来表示，反过来，我们可以通过满二叉树的特性推导出汉诺塔的一些特性：

*  满二叉树总的结点数为 2 n − 1 2^n-1 2n−1，所以汉诺塔移动次数为 2 n − 1 2^n-1 2n−1；
 *  满二叉树第n层的节点数为 2 n − 1 2^\{n-1\} 2n−1，所以n阶汉诺塔第i个盘子被移动的次数为 2 ( n − i + 1 ) − 1 = 2 n − i 2^\{(n-i+1)-1\}=2^\{n-i\} 2(n−i\+1)−1=2n−i；
 *  满二叉树叶子节点数为 2 n − 1 2^\{n-1\} 2n−1,所以汉诺塔第一个盘子被移动的次数为 2 n − 1 2^\{n-1\} 2n−1；
 *  满二叉树是二进制的一种表现形式，所以汉诺塔也是二进制的一种表现形式，其中汉诺塔的移动过程就是二进制的累加过程。

最后附上三者的关系图

![image][image 5]

### 总结 ###

如果这些结论都是自己推导发现的话，你会发现充满惊喜。其推导过程非常有意思，好像冥冥之中万物都和二进制相关。文章想表达的不仅仅是得出汉诺塔有哪些特性，更重要的是希望能在学习中，发现学习本身的乐趣，从而滋养内在的好奇心、探索精神，不断地自我推进，让学习越来越有趣越有动力。

![image][image 6]

[自己编写平滑加权轮询算法，实现反向代理集群服务的平滑分配][Link 1]

[Java实现平滑加权轮询算法--降权和提权][Java_--]

[Java实现负载均衡算法--轮询和加权轮询][Java_-- 1]

[Java全栈学习路线、学习资源和面试题一条龙][Java]

更多优质文章，请关注WXgzh： Java全栈布道师

原创不易，觉得写得还不错的，三联支持↓

[image]: https://img-blog.csdnimg.cn/img_convert/81209a0d8af958f92f6c7121e18194b1.png
[image 1]: https://img-blog.csdnimg.cn/img_convert/c5f4fc91c68a428a1159e9f0cac8188f.png
[image 2]: https://img-blog.csdnimg.cn/img_convert/fa6b64854eed133aa6d051cc39933ede.png
[image 3]: https://img-blog.csdnimg.cn/img_convert/42413deff9833283c6158cc69140714e.png
[image 4]: https://img-blog.csdnimg.cn/img_convert/7489ae56d2608f7abc6f8826b79d95de.png
[image 5]: https://img-blog.csdnimg.cn/img_convert/ec46150d7fb2f37646e3ef186ad99b93.png
[image 6]: https://img-blog.csdnimg.cn/img_convert/f144c9204a505c460a45f3d6843cb239.gif
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI5NDM5NDM1NA==&mid=2247485469&idx=1&sn=d81920b2ce30a1d675c95aa881627bd6&chksm=ec62c880db154196d1f37129cb9dc30f107814fa2da2f130f08a207da814fd25eba54ac3c18a&scene=21#wechat_redirect
[Java_--]: http://mp.weixin.qq.com/s?__biz=MzI5NDM5NDM1NA==&mid=2247485441&idx=1&sn=db09c8d233c743b3a4bdf7f4d2766b81&chksm=ec62c89cdb15418acf590bbe316a3e9cc9420959eac0d57858a5afb825cc45d8c20bafd2e765&scene=21#wechat_redirect
[Java_-- 1]: http://mp.weixin.qq.com/s?__biz=MzI5NDM5NDM1NA==&mid=2247485432&idx=1&sn=81347615fdec6a4e7e2bb2ae74d85f1b&chksm=ec62c765db154e7348c1b34ebeed1e0ec006c68cfbeda17f1321d4e318b155258982d093b898&scene=21#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=MzI5NDM5NDM1NA==&mid=2247485015&idx=1&sn=862bc2b379726b89cdb396ec0d325cc0&chksm=ec62c6cadb154fdc533111a253d72001534ab92de317cbde5c1c9f575548500bc734c3028484&scene=21#wechat_redirect