汉诺塔的图解递归算法

一.起源:

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

二.抽象为数学问题:

  如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数

解:(1)n == 1

第1次  1号盘  A---->C       sum = 1 次

(2)  n == 2

第1次  1号盘  A---->B

第2次  2号盘  A---->C

第3次  1号盘  B---->C        sum = 3 次

  (3)n == 3

  第1次  1号盘  A---->C

  第2次  2号盘  A---->B

  第3次  1号盘  C---->B

  第4次  3号盘  A---->C

  第5次  1号盘  B---->A

  第6次  2号盘  B---->C

  第7次  1号盘  A---->C        sum = 7 次

不难发现规律:1个圆盘的次数 2的1次方减1

       2个圆盘的次数 2的2次方减1

3个圆盘的次数 2的3次方减1

。  。   。    。   。

n个圆盘的次数 2的n次方减1

故:移动次数为:2^n - 1

三.调用方法的栈机制:(特点:先进后出)

从主线程开始调用方法(函数)进行不停的压栈和出栈操作,函数的调用就是将函数压如栈中,函数的结束就是函数出栈的过程,这样就保证了方法调用的顺序流,即当函数出现多层嵌套时,需要从外到内一层层把函数压入栈中,最后栈顶的函数先执行结束(最内层的函数先执行结束)后出栈,再倒数第二层的函数执行结束出栈,到最后,第一个进栈的函数调用结束后从栈中弹出回到主线程,并且结束。

四.算法分析(递归算法):

我们在利用计算机求汉诺塔问题时,必不可少的一步是对整个实现求解进行算法分析。到目前为止,求解汉诺塔问题最简单的算法还是同过递归来求,至于是什么是递归,递归实现的机制是什么,我们说的简单点就是自己是一个方法或者说是函数,但是在自己这个函数里有调用自己这个函数的语句,而这个调用怎么才能调用结束呢?,这里还必须有一个结束点,或者具体的说是在调用到某一次后函数能返回一个确定的值,接着倒数第二个就能返回一个确定的值,一直到第一次调用的这个函数能返回一个确定的值。

实现这个算法可以简单分为三个步骤:

    (1)     把n-1个盘子由A 移到 B;

    (2)     把第n个盘子由 A移到 C;

    (3)     把n-1个盘子由B 移到 C;

从这里入手,在加上上面数学问题解法的分析,我们不难发现,移到的步数必定为奇数步:

    (1)中间的一步是把最大的一个盘子由A移到C上去;

    (2)中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,

    (3)中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;

五,java源代码:

package demo;
/**
 * 目的:实现汉诺塔问题求解
 * 作者:Dmego  时间:2016-10-15
 */
import java.util.Scanner;

public class TowersOfHanoi {
    static int m =0;//标记移动次数
    //实现移动的函数
    public static void move(int disks,char N,char M)
    {
        System.out.println("第" + (++m) +" 次移动 : " +" 把 "+ disks+" 号圆盘从 " + N +" ->移到->  " + M);
    }
    //递归实现汉诺塔的函数
    public static void hanoi(int n,char A,char B,char C)
    {
        if(n == 1)//圆盘只有一个时,只需将其从A塔移到C塔
            TowersOfHanoi.move(1, A, C);//将编b号为1的圆盘从A移到C
        else
        {//否则
            hanoi(n - 1, A, C, B);//递归,把A塔上编号1~n-1的圆盘移到B上,以C为辅助塔
            TowersOfHanoi.move(n, A, C);//把A塔上编号为n的圆盘移到C上
            hanoi(n - 1, B, A, C);//递归,把B塔上编号1~n-1的圆盘移到C上,以A为辅助塔
        }
    }
    public static void main(String[] args) {
        Scanner imput = new Scanner(System.in);
        char A = ‘A‘;
        char B = ‘B‘;
        char C = ‘C‘;
        System.out.println("******************************************************************************************");
        System.out.println("这是汉诺塔问题(把A塔上编号从小号到大号的圆盘从A塔通过B辅助塔移动到C塔上去");
        System.out.println("******************************************************************************************");
        System.out.print("请输入圆盘的个数:");
        int disks = imput.nextInt();
        TowersOfHanoi.hanoi(disks, A, B, C);
        System.out.println(">>移动了" + m + "次,把A上的圆盘都移动到了C上");
        imput.close();
    }

}

六.图解程序运行流程:

  (1)函数hanoi(int n,char A,char B,char C)的功能是把编号为n的圆盘借助B从A移动到 C上。

  (2)函数move(int n ,char N ,char M)的功能是把1编号为n的圆盘从N 移到M上

七.程序运行截图:

时间: 10-14

汉诺塔的图解递归算法的相关文章

汉诺塔问题非递归算法集锦

巧若拙(欢迎转载,但请注明出处:http://blog.csdn.net/qiaoruozhuo) 汉诺塔问题介绍: 在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片,一次只移动一片,不管在哪根针上,小片必在大片上面.当所有的金片都从梵天穿好的那根针上移到另外一概针上时,世界就将在一声霹

汉诺塔的非递归算法

思路 模拟递归程序执行过程,借助一个堆栈,把递归转成非递归算法. 转化过程 1. 递归算法 1 void hanoi(int n, char from, char pass, char to) { 2 if (n == 0) 3 return; 4 5 hanoi(n - 1, from, to, pass); 6 move(n, from, to); 7 hanoi(n - 1, pass, from, to); 8 } 2. 处理首递归 本函数第2行是结束条件,第5行开始进入首递归.执行第5

汉诺塔解析(图解)

ps:一时学不会也没关系,过一个月再自己试试说不定就学会了 ps:图片可能加载有点慢 题目: 三个柱子,标号为1,2,3 现在告诉你柱子1上套有n个盘,问你如何把全部盘从柱子1移到柱子3 注意:盘子顺序必须时刻保持从上到下是从小到大的,一次只能移一个盘 基本思路: 现在有3个柱子,分别标号为1,2,3,然后会输入一个n,代表初始的时候有几个盘子 特殊说明:输出过程的时候,把 1 -> 3 这样的结果看作从柱子1移最上面那个盘子到柱子3 比如说当三个盘子时 3 1 -> 3 1 -> 2

【Python学习】Python解决汉诺塔问题

参考文章:http://www.cnblogs.com/dmego/p/5965835.html 一句话:学程序不是目的,理解就好:写代码也不是必然,省事最好:拿也好,查也好,解决问题就好! 信息时代不用信息就是罪过,直接抄不加理解与应用,就不是自己的,下次遇到还是不会,或许其中的某一个细节就能够用于各个问题的解决,共勉 学习一个东西总会遇到一些经典的问题,学习Python第二天尝试看一下汉诺塔问题,还是百度,看看解题思路,纯粹是重温初中课堂,越活越回去了 汉诺塔的图解递归算法 一.起源: 汉诺

汉诺塔hanoi

问题描述: 有一个梵塔,塔内有三个座A.B.C,A座上有诺干个盘子,盘子大小不等,大的在下,小的在上(如图). 把这些个盘子从A座移到C座,中间可以借用B座但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘 子始终保持大盘在下,小盘在上. 描述简化:把A柱上的n个盘子移动到C柱,其中可以借用B柱. #include <bits/stdc++.h> using namespace std; void move(int n, char f, char t) { static int cnt

算法学习(4)----汉诺塔递归算法和非递归算法

学习<算法设计与分析基础>,习题2.4 第5题要求为汉诺塔游戏设计一个非递归的算法. 思,不得其解.看书后答案提示: 你如果做不到,也不要沮丧:这个问题的非递归算法虽然不复杂,但却不容易发现.作为一种安慰,可以在因特网上寻找答案. 好吧,话都说得这么直接了,遂百度之,得到一个感觉很好的答案,略做修改,摘录于下: 原文地址:http://blog.sina.com.cn/s/blog_48e3f9cd01000474.html ##################################

汉诺塔问题的详解-附代码

一.由来: 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 汉诺塔问题源于递归算法,看起来很简单,想起来很麻烦,要深刻理解递归的真正含义,将第一个柱子上的所有圆盘全部拿到第三个盘子上,其实这些盘子可以抽象的分成两个部分,最底下的大盘子,和上面的小盘子.

汉诺塔的递归算法

汉诺塔是怎样通过递归算法实现的? 这个问题困扰了我一段时间,今天回过头来想想似乎明白了,因此在这里记录下自己想法. 首先贴上在Python上的代码: 1 # -*- coding: utf-8 -*- 2 3 def move(n,a,b,c): 4 if n == 1: 5 print(a+"-->"+c) 6 if n > 1: 7 move(n-1,a,c,b) 8 print(a+"-->"+c) 9 move(n-1,b,a,c) 10

C语言之算法初步(汉诺塔--递归算法)

个人觉得汉诺塔这个递归算法比电子老鼠的难了一些,不过一旦理解了也还是可以的,其实网上也有很多代码,可以直接参考.记得大一开始时就做过汉诺塔的习题,但是那时代码写得很长很长,也是不理解递归的结果.现在想起来汉诺塔的算法就3个步骤:第一,把a上的n-1个盘通过c移动到b.第二,把a上的最下面的盘移到c.第三,因为n-1个盘全在b上了,所以把b当做a重复以上步骤就好了.所以算法看起来就简单多了.不过,思考过程还是很痛苦的,难以理解.递归中会保存数据的好处在这里又得到体现,太神奇了. 汉诺塔代码如下: