汉诺塔问题研究——分治法

前言

相信学过《数据结构与算法》这门课程的同学都有听过汉诺塔问题,但是可能在大学的时候没有钻研过,或者在学的时候就没有弄懂,导致没有很好的理解汉诺塔的经典解法,下面让我来给大家来分析一下。

背景

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三个金刚石塔,在一个塔上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在最后一个塔上。并且规定,在小圆盘上不能放大圆盘,在三个塔之间一次只能移动一个圆盘。

分析

对圆盘编号1~n,数字大的圆盘比数字小的圆盘体积大。并且引入起始塔,中转塔,目标塔的概念,在算法运行的时候,这3个塔的身份可能会互相变换。
  1.如果现在在塔A上面只有1个圆盘,那么直接把圆盘移动到塔C即可;
  2.如果现在在塔A上面有2个圆盘,那么先把圆盘1从塔A移动到塔B,再把圆盘2从塔A移动到塔C,最后把圆盘1从塔B移动到塔C;
  3..……
  4.如果塔A有n个圆盘,那么需要先把圆盘n之前的(圆盘n-1~ 圆盘1)从塔A先移动到塔B,再把圆盘n从塔A移动到塔C,最后把放在塔B的(圆盘n-1~圆盘1)从塔B移动到塔C。

可以看出,上面的解法是很典型的分治法算法思想。
  因为汉诺塔要求一次只能移动一个圆盘,并且小圆盘上面不能放大圆盘,所以需要把同一个塔最底下的大圆盘上面的圆盘搬走。要想移动圆盘n,那么先要移动其上的(圆盘n-1~ 圆盘1)到中转塔,要想移动(圆盘n-1~ 圆盘1)中的圆盘n-1,那么先要移动其上的(圆盘n-2~ 圆盘1)到中转塔,依次类推……直到只有一个圆盘1,那么直接移动即可。同时,因为我们的目的是把所有的圆盘移动到目标塔,所以在移动完圆盘n到目标塔之后,需要把之前放在中转塔上的(圆盘n-1~圆盘1)移动到目标塔。
  可能大家会说了,道理都懂,但是代码该如何写呢?其实这也是算法学习中比较占时间的部分,用计算机编程语言把算法表示(写)出来。下面给大家附上经典的实现,分析为何要这样写,并介绍一种我自己平时理解递归所用的思考方法。

Java版算法实现

一般来说,分治法总是结合递归去实现,以下示例代码就用了递归结构。
  在写递归结构的时候,可以从语义层面去出发。思考过程如上面分析所示:我们需要写一个函数,它的作用是把圆盘n~圆盘1由一个起始塔移动到目标塔,由于要求要先移动圆盘n上面的圆盘后才能移动圆盘n,所以需要一个中转塔。经过这样的思考过程之后,我们就可以确定函数的签名了,即void hanoi(int n, String sourceTower, String tempTower, String targetTower)
  根据算法,函数体里面就可这样写(语义层面):
  如果当前为盘子1,那么直接移动到目标塔 move(n, sourceTower, targetTower)
  否则先将圆盘n-1~圆盘1移动到中转塔hanoi(n - 1, sourceTower, targetTower, tempTower),移动完之后把圆盘n先移动到目标塔move(n, sourceTower, targetTower),再把中转塔上的圆盘n-1~圆盘1移动到目标塔hanoi(n - 1, tempTower, sourceTower, targetTower)

public class Hanoi {
    public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
        if (n == 1) {
            //如果只有一个盘子1,那么直接将其从sourceTower移动到targetTower
            move(n, sourceTower, targetTower);
        } else {
            //将(盘子n-1~盘子1)由sourceTower经过targetTower移动到tempTower
            hanoi(n - 1, sourceTower, targetTower, tempTower);
            //移动盘子n由sourceTower移动到targetTower
            move(n, sourceTower, targetTower);
            //把之前移动到tempTower的(盘子n-1~盘子1),由tempTower经过sourceTower移动到targetTower
            hanoi(n - 1, tempTower, sourceTower, targetTower);
        }
    }

    //盘子n的从sourceTower->targetTower的移动
    private static void move(int n, String sourceTower, String targetTower) {
        System.out.println("第" + n + "号盘子 move:" + sourceTower + "--->" + targetTower);
    }

    public static void main(String[] args) {
        System.out.println("移动汉诺塔的步骤:");
        hanoi(3, "a", "b", "c");
    }
}

运行结果:

移动汉诺塔的步骤:
第1号盘子 move:a--->c
第2号盘子 move:a--->b
第1号盘子 move:c--->b
第3号盘子 move:a--->c
第1号盘子 move:b--->a
第2号盘子 move:b--->c
第1号盘子 move:a--->c

可以发现,对于一次调用hanoi(n, sourceTower, tempTower, targetTower),中转塔是给圆盘n-1~圆盘1用的。从语义上理解,hanoi(n, sourceTower, tempTower, targetTower)最终的调用效果是圆盘n~圆盘1从起始塔全部移动到了目标塔,并按要求(在小圆盘上不能放大圆盘)所有圆盘都放在目标塔上了。

可能有些同学还是不能理解为什么满足了在小圆盘上不能放大圆盘的的这个要求,很简单,因为我们每次想移动圆盘n的时候,都已经把圆盘n上面的圆盘拿走了,移动完圆盘n之后,再把其他圆盘移动到圆盘n所在的塔上,所以当然是满足了在小圆盘上不能放大圆盘的的这个要求。如果还是不能明白的话,可以从2个圆盘的情况和3个圆盘的情况去模拟看看。

附上一个算法调用的分析图:


3阶汉诺塔分析.png

总结

平时在用分治法解决问题的时候,先根据分治法的原则把问题逐步拆分。而分治法往往需要和递归结合起来去写代码,阅读或者设计递归结构的时候可以从语义的层面出发去进行。
  与分治法一样,回溯法也可以跟递归结合去实现。但是两者还是有些许区别的。
  分治法使用递归解决问题,问题一般是有解的。如汉诺塔,链表反转。
  回溯法使用递归试探问题的解法,可能会无解。如迷宫问题,深度遍历。

结语

其实钻研算法的确挺烧脑的,而且需要投入比较多的时间。很多人觉得有这时间还不如去看看别的框架更好。其实吧,如果想在计算机领域成为大牛,算法知识是必不可少的。本人很喜欢看动漫《一拳超人》,里面有一句台词“兴趣使然”。确实,我觉得算法是最能体现计算机科学之魅力的东西,所以研究算法就不会觉得无聊,因为“兴趣使然”。
  ——写于2018中秋佳节。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,743评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,296评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,285评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,485评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,581评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,821评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,960评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,719评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,186评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,516评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,650评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,936评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,757评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,991评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,370评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,527评论 2 349

推荐阅读更多精彩内容

  • 递归算法 开放分类:数学术语术语科学自然科学计算机术语 递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递...
    LuckTime阅读 220评论 0 0
  • 前置文章:递归算法:www.greatytc.com/p/703069f3ba3f . 汉诺塔问题是来源于印度传...
    郎小凯阅读 754评论 0 1
  • 原文链接(转载请注明出处)汉诺塔的图解递归算法 起源 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大...
    Dmego阅读 1,532评论 0 0
  • 我 坐在窗前 仰望星空 他们 一闪一闪的 好像 在向我倾诉着 我 静静的聆听 他们的诉说
    恋城时凉阅读 334评论 0 1
  • 所谓"聊得来"的深层含义其实是:读懂你的内心,听懂你的说话,与你的见识同步,配得上你的好,并能互相给予慰藉、理解和...
    孙靖洆阅读 139评论 0 0