汉诺塔问题

汉诺塔问题

  最近面试题遇到过汉诺塔的问题,当时竟然懵逼了,不会了!!大学研究的问题竟然都忘光了,于是抓紧捡起来。然而在网上看了看博客,发现非递归算法还真挺多。下面总结了一下。

一、递归算法

  1、递归算法优缺点:递归算法算是最易于理解也是最容易实现的,但是对内存的消耗也是巨大的,因为递归需要系统堆栈来保存调用函数地址、形参、局部变量、返回值等数据,也就是回调N次,就要保存N个之前提到的数据。但是递归算法结构简洁,清晰。基于这个原因,我先介绍一下递归算法。

  2、递归算法思路:

    1)将N-1个盘子从A柱移动到B柱或者将N-1个盘子从B柱移动到A柱。

    2)将第N个盘子移动到C柱。

代码:

 1 /**
 2      * 
 3      * @param n 需要移动的盘子数
 4      * @param a a柱    这里的abc柱,并不是实际问题中的ABC三个柱子,是动态分析过程中的柱子
 5      * @param b    b柱
 6      * @param c    c柱
 7      */
 8     static void move(int n, char a, char b, char c) {
 9         if (n == 1)
10             System.out.println(a + "-->" + c); // 当只有1个盘子的时候直接将盘子从a柱移动到c柱
11         else {
12             move(n - 1, a, c, b); // 将当前a柱的n-1个盘子,通过c移动到b
13             System.out.println(a + "-->" + c);//将a柱子上的最大的盘子移动到c柱
14             move(n - 1, b, a, c); // n-1个移动过来之后b柱成为a柱,这里就变成了n-1个盘子从b移动到c柱。
15         }
16     }

  二、非递归算法

  这里使用了便利二叉树的思路

1)算法推论描述:

    这里用4个盘子举例

    进行整合:

2)算法规律:

   根据上面的二叉树的图,可以看到如下规率:

    A.盘子数(N)=二叉树的高度(H)

    B.第n层序号能被2的(n-1)次方整除,但不能被2的n次方整除(n从下至上增加)

    C.每一层的节点数=2的(N-n)次方

    D.无论有多少个盘子,每一层的步骤都是相同的,例如:所有的最上面一层都是A->C,第二层也是一样的。

    E.每一层都是以A未开始,以C为结束

    F.奇数层规律是A->C,C->B,B->A,依次循环

    G.偶数层规律是A->B,B->C,C->A,依次循环

  根据上面的特点进行进一步总结得到:

    A.第M部层数确定(可以判断循环规律):如果M能被2的(n-1)次方整除,但不能被2的n次方整除,那么,M步处于n层

    B.第M步在J层的序号确定:K=M除以2的(n-1)次方

3)算法代码:

static void hanoi(int m) {
        int c = 1;// 总步骤数
        int n = 1;// 步骤数
        c <<= m;
        for (; n < c; n++) {
            shuchu(m, n);
        }
    }

    private static void shuchu(int m, int n) {
        for (int i = n, y = i % 2, c = m;; i = i / 2, y = i % 2, c--) {
            if (y != 0) {
                switch ((c % 2) * 3 + (i / 2) % 3) {
                case 0:
                    System.out.println("第"+n+"步"+ ":A-B"+"   当前移动的盘子是:"+(m-c+1));
                    break;
                case 1:
                    System.out.println("第"+n+"步"+ ":B-C"+"   当前移动的盘子是:"+(m-c+1));
                    break;
                case 2:
                    System.out.println("第"+n+"步"+ ":C-A"+"   当前移动的盘子是:"+(m-c+1));
                    break;
                case 3:
                    System.out.println("第"+n+"步"+ ":A-C"+"   当前移动的盘子是:"+(m-c+1));
                    break;
                case 4:
                    System.out.println("第"+n+"步"+ ":C-B"+"   当前移动的盘子是:"+(m-c+1));
                    break;
                case 5:
                    System.out.println("第"+n+"步"+ ":B-A"+"   当前移动的盘子是:"+(m-c+1));
                }
                break;
            }
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

objective-C中的Class(类类型),Selector(选择器SEL),函数指针(IMP)

今天在园子里看到了一篇牛文“Objective-C 2.0 with Cocoa Foundation--- 5,Class类型,选择器Selector以及函数...

2335
来自专栏数据结构与算法

3145 汉诺塔游戏

3145 汉诺塔游戏  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 白银 Silver  查看运行结果 题目描述 Description...

3657
来自专栏陈满iOS

iOS开发·NSString字符串的各种基本操作,数值转换及衍生操作

但有时候,仅仅停留在这些基本操作还不能直接满足一些需求,这时候可以利用这些基本操作进行一些字符串的衍生操作。

2522
来自专栏青玉伏案

Objective-C中的内存管理

        在编程语言中是少不了对内存的管理的,内存对于计算机来说是宝贵的资源,所以对使用不到的资源进行回收是很有必要的。OC中使用引用计数和垃圾回收来管理...

1859
来自专栏前端那些事

递归函数-汉诺塔经典递归

前言 最近在读《JavaScript语言精粹》,对递归函数有了进一步的认识,希望总结下来: 递归是一种强大的编程技术,他把一个问题分解为一组相似的子问题,每一问...

2877
来自专栏C语言及其他语言

【每日一题】问题 1109: Hanoi双塔问题

关注我们 题目描述 给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分...

34310
来自专栏進无尽的文章

编码篇 - NSInvocation的简单使用

在认识 NSInvocation 之前,iOS开发中我们一般会使用以下两种方式去调用一个方法

1362
来自专栏数据魔术师

基础算法 | 递归的世界你不懂.......

转眼间又到了深夜,终于能好好吃一把鸡了。 ………… 等等,TM11点就停电了。玩鸡毛!!! 哦……那么,就只能……学习了…… 今天学啥呢? 对,没错 今天要教给...

4316
来自专栏Scott_Mr 个人专栏

利用Runtime实现简单的字典转模型

1103
来自专栏Python小屋

基于非递归算法的汉诺塔游戏之Python实现

本文代码涉及到汉诺塔问题的非递归算法,可能不是很好理解,我在代码中加了大量注释,希望能够有所帮助,如果实在难以理解的话,请搜索这个算法并结合下面的代码进行阅读和...

6465

扫码关注云+社区

领取腾讯云代金券