开发者社区> 壮壮father> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

汉诺塔问题

简介: 汉诺塔问题   最近面试题遇到过汉诺塔的问题,当时竟然懵逼了,不会了!!大学研究的问题竟然都忘光了,于是抓紧捡起来。然而在网上看了看博客,发现非递归算法还真挺多。下面总结了一下。   一、递归算法   1、递归算法优缺点:递归算法算是最易于理解也是最容易实现的,但是对内存的消耗也是巨大的,因为递归需要系统堆栈来保存调用函数地址、形参、局部变量、返回值等数据,也就是回调N次,就要保存N个之前提到的数据。
+关注继续查看

汉诺塔问题

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

  一、递归算法

  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;
            }
        }
    }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
递归—汉诺塔
汉诺塔是经典递归问题:相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
35 0
汉诺塔问题(递归版)
汉诺塔问题(递归版)
42 0
经典递归 - 汉诺塔问题
经典递归 - 汉诺塔问题
30 0
递归-汉诺塔
问题描述 算法复杂度 2的n次方再减1 n为盘子的个数 算法实现 #include #include /** 汉诺塔问题 */ void hanoi(int n,char A, char B, char C){ ...
813 0
汉诺塔问题
老生常谈的一个问题,仅作代码记录呵呵 题目链接:http://ica.openjudge.cn/dg2/3/ 总时间限制: 1000ms  内存限制: 65536kB 描述 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。
948 0
汉诺塔
1 #include 2 #include 3 4 using namespace std; 5 6 void Hanoi(int n,char A,char B,char C); 7 8 void main() 9 { 10 Hanoi(5,'...
555 0
+关注
壮壮father
从14年开始从事安卓开发。喜欢接触新鲜事物,不断的挑战自己
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载