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

汉诺塔(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(n1)+1n11n=1

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

由递归式可知:

image

又因当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)=2n1+2n2+...+21+20=2n1

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

汉诺塔与二进制

公式

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)=2n1+2n2+...+21+20=2n1

这就像是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} 10000212=11112=1510

每个盘子的移动次数,观察下图:

image

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

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

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

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

image

汉诺塔与满二叉树

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

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

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

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 2n1,所以汉诺塔移动次数为 2 n − 1 2^n-1 2n1

  • 满二叉树第n层的节点数为 2 n − 1 2^{n-1} 2n1,所以n阶汉诺塔第i个盘子被移动的次数为 2 ( n − i + 1 ) − 1 = 2 n − i 2^{(n-i+1)-1}=2^{n-i} 2(ni+1)1=2ni

  • 满二叉树叶子节点数为 2 n − 1 2^{n-1} 2n1,所以汉诺塔第一个盘子被移动的次数为 2 n − 1 2^{n-1} 2n1

  • 满二叉树是二进制的一种表现形式,所以汉诺塔也是二进制的一种表现形式,其中汉诺塔的移动过程就是二进制的累加过程。

最后附上三者的关系图

image

总结

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

image

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

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

Java实现负载均衡算法--轮询和加权轮询

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

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/8067.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数据挖掘(2.3)--数据预处理

目录 三、数据集成和转换 1.数据集成 2.数据冗余性 2.1 皮尔森相关系数 2.2卡方检验 3.数据转换 四、数据的规约和变换 1.数据归约 2数据离散化 三、数据集成和转换 1.数据集成 数据集成是将不同来源的数据整合并一致地存储起来的过程。 不同来源的数据可能有不同…

【ESP32+freeRTOS学习笔记之“ESP32环境下使用freeRTOS的特性分析(2-多核环境中的任务)”】

目录1、ESP32的双核对称多处理SMP概念2、涉及任务task的特殊性2.1 创建任务的特殊函数2.2 xTaskCreatePinnedToCore()函数的解释3、任务的删除4、总结1、ESP32的双核对称多处理SMP概念 最初的FreeRTOS(以下简称Vanilla FreeRTOS)…

线性表——顺序表

文章目录一:线性表二:顺序表1:概念与结构1:静态顺序表2:动态顺序表2:动态顺序表的代码实现1:结构2:接口实现1:初始化2:释放内存3:检查容量4&#…

Linux下最小化安装CentOS-7.6(保姆级)

文章目录安装包开始安装一、 新建一个虚拟机二、配置安装CentOS7.6二、开始安装CentOS三、配置CentOS并下载基本信息安装包 链接:https://pan.baidu.com/s/1DodB-kDy1yiNQ7B5IxwYyg 提取码:p19i 开始安装 一、 新建一个虚拟机 1、 打开VMWare&#x…

刷题笔记【5】| 快速刷完67道剑指offer(Java版)

本文已收录于专栏🌻《刷题笔记》文章目录前言🎨 1、合并两个有序链表题目描述思路一(递归)思路二(双指针)🎨 2、树的子结构题目描述思路一(递归)🎨 3、二叉树…

Redis分布式锁系列

1.压力测试出的内存泄漏及解决(可跳过) 使用jmeter对查询产品分类列表接口进行压力测试,出现了堆外内存溢出异常。 我们设置的虚拟机堆内存100m,并不是堆外内存100m 产生堆外内存溢出:OutOfDirectMemoryError 原因是…

某大厂面试题:说一说Java、Spring、Dubbo三者SPI机制的原理和区别

大家好,我是三友~~ 今天来跟大家聊一聊Java、Spring、Dubbo三者SPI机制的原理和区别。 其实我之前写过一篇类似的文章,但是这篇文章主要是剖析dubbo的SPI机制的源码,中间只是简单地介绍了一下Java、Spring的SPI机制,并没有进行深…

SQL——数据查询DQL

基本语句、时间查询(当天、本周,本月,上一个月,近半年的数据)。 目录 1 查询语句基本结构 2 where 子句 3 条件关系运算符 4 条件逻辑运算符 5 like 子句 6 计算列 7 as 字段取别名 8 distinct 清除重复行 9 …

linux mysql

安装 下载包 wget https://cdn.mysql.com/archives/mysql-8.0/mysql-8.0.31-1.el8.x86_64.rpm-bundle.tar解压 tar -zxvf mysql-8.0.31-1.el8.x86_64.rpm-bundle.tar -C /usr/local/mysql安装openssl-devel插件 yum install openssl-devel安装rpm包 使用rpm -ivh安装图中r…

【Unity项目实战】从零手戳一个背包系统

首先我们下载我们的人物和背景资源,因为主要是背包系统,所以人物的移动和场景的搭建这里我们就不多讲了,我这里直接提供基础项目源码给大家去使用就行 基础项目下载地址: 链接: https://pan.baidu.com/s/1o7_RW_QQ1rrAbDzT69ApRw 提取码: 8s95 顺带说一下,这里用到了uni…

AttributeError: module transformers has no attribute LLaMATokenizer解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

AES加密

来源:链接: b站up主可厉害的土豆 (据评论区说图片中有计算错误,但是过程是对的。只是了解过程问题不大,专门研究这一块的话自己可以看视频算一下) 准备 首先,明文是固定长度 16字节 128位。 密钥长度可以…

TCP协议一

TCP数据报格式 TCP通信时序 下图是一次TCP通讯的时序图。TCP连接建立断开。包含大家熟知的三次握手和四次握手。 在这个例子中,首先客户端主动发起连接、发送请求,然后服务器端响应请求,然后客户端主动关闭连接。两条竖线表示通讯的两端&…

houjie-cpp面向对象

houjie 面向对象 面向对象(上) const 在一个函数后面放const,这个只能修饰成员函数,告诉编译器这个成员函数不会改数据 const还是属于函数签名的一部分。 引用计数:涉及到共享的东东,然后当某个修改的时候&…

Mysql的学习与巩固:一条SQL查询语句是如何执行的?

前提 我们经常说,看一个事儿千万不要直接陷入细节里,你应该先鸟瞰其全貌,这样能够帮助你从高维度理解问题。同样,对于MySQL的学习也是这样。平时我们使用数据库,看到的通常都是一个整体。比如,你有个最简单…

【Paper】2019_Resilient Consensus Through Asynchronous Event-based Communication

Wang Y, Ishii H. Resilient consensus through asynchronous event-based communication[C]//2019 American Control Conference (ACC). IEEE, 2019: 1842-1847. 文章目录I. INTRODUCTIONII. EVENT-BASED RESILIENT CONSENSUS PROBLEMA. Preliminaries on graphsB. Event-base…

基于Java+ SpringBoot+Vue 的网上图书商城管理系统(毕业设计,附源码,教程)

您好,我是程序员徐师兄,今天为大家带来的是 基于Java SpringBootVue 的网上图书商城管理系统(毕业设计,附源码,教程)。 😁 1.Java 毕业设计专栏,毕业季咱们不慌忙,几百款…

电脑桌面图标间距突然变大怎么恢复

1. WindowsR打开 > 输入regedit 按住WindowsR打开运行,输入regedit并点击确定。 2. 双击Control Panel 双击展开HKEY_CURRENT_USER,双击展开Control Panel,双击展开Desktop。 3. 更改间距 点击打开WindowMetrics, 双击打开…

两年外包生涯,给我后面入职字节跳动奠定了基础.....

我是一位软件测试工程师。从大学毕业后,我进入了一家外包公司,在那里工作了两年时间。虽然我在公司中得到了不少锻炼和经验,但是我一直渴望能够进入一家更加专业的公司,接触更高端、更有挑战性的项目。 于是,我开始主…

Keil 4 安装教程及简单使用【嵌入式系统】

Keil 4 安装教程及简单使用【嵌入式系统】前言推荐说明Keil 4 for Arm安装教程1.安装MDK2.激活mdkkeil 4 for arm 的简单使用1建立新工程2在工程下创建新文件3.设置工程属性4.中文注释5.编辑代码6.build7.debug8. 调试窗口简介keil 4 for C51安装教程1.前期准备2.开始keil4 for…