汉诺塔_汉诺塔递归 - CSDN
汉诺塔 订阅
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 展开全文
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
信息
发明人
爱德华·卢卡斯
中文名称
汉诺塔
外文名称
Tower of Hanoi
又    称
河内塔
汉诺塔由来及传说
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。移动图片不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片,移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时,假如每秒钟一次,共需多长时间呢?一个平年365天有31536000 秒,闰年366天有31622400秒,平均每年31557600秒,计算一下:18446744073709551615秒计算的python程序:请输入片的个数:64需要移动 18446744073709551615 次这表明移完这些金片需要5845.42亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。真的过了5845.42亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。和汉诺塔故事相似的,还有另外一个印度传说 [1]  :舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么,他对国王说:“陛下,请您在这张棋盘的第1个小格里赏给我一粒麦子,在第2个小格里给2粒,第3个小格给4粒,以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒,都赏给您的仆人吧!”国王觉得这个要求太容易满足了,就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时,国王才发现:就是把全印度甚至全世界的麦粒全拿来,也满足不了那位宰相的要求。那么,宰相要求得到的麦粒到底有多少呢?总数为1+2+2^2 + … +2^63=2^64-1等于移完汉诺塔所需的步骤数。我们已经知道这个数字有多么大了。人们估计,全世界两千年也难以生产这么多麦子!
收起全文
  • 汉诺塔问题

    千次阅读 2019-03-23 21:59:24
    1205:汉诺塔问题 【题目描述】 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上,...

    1205:汉诺塔问题

    【题目描述】

    约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面。

    这是一个著名的问题,几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:18,446,744,073,709,551,615

    这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔,但很难用计算机解决64层的汉诺塔。

    假定圆盘从小到大编号为1, 2, ...

    【输入】

    输入为一个整数(小于20)后面跟三个单字符字符串。

    整数为盘子的数目,后三个字符表示三个杆子的编号。

    【输出】

    输出每一步移动盘子的记录。一次移动一行。

    每次移动的记录为例如 a->3->b 的形式,即把编号为3的盘子从a杆移至b杆。

    【输入样例】

    2 a b c

    【输出样例】

    a->1->c
    a->2->b
    c->1->b
    

    分析:

    将所有盘子从柱子A移动到柱子B上

    (1)当N=1 时,只有一个盘子,只需要移动一次:A—>1—>B;
    (2)当N=2时,则需要移动三次:
            A—>1—> C

            A —>2—>B

            C —>1—>B
    (3)如果N=3,则具体移动步骤为:

           A—>1—> B,    A —>2—>C,    B —>1—>C.       (3.1)

           A—>3—>B.                                                         (3.2)

           C—>1—>A,    C —>2—>B,    A —>1—>B.         (3.3)

    会发现当n>=2时是有规律的,可以抽象出将n-1个盘当做一个整体,首先要(借助b)将n-1个盘从柱子a移动到柱子c,然后将第n个盘子从a移动到柱子b,最后将n-1个盘子(借助a)从柱子c移动到柱子b上就大功告成了。

    例如当n==2时,将第一个盘子移动到c,然后将第2(n==2)个盘子从柱子a移动到柱子b,最后将第1个盘子从柱子c移动到柱子b。n==2就可以抽象为将2个盘子借助c从a移动到柱子b上

    当n==3时,可以将3.1看做将1、2盘子借助b从a移动到柱子c,然后将第3(n==3)个盘子从a移动到柱子b,最后将1、2盘子借助a从柱子c移动到柱子b

    同样n==4时,可以将前三个盘子借助b从a移动到柱子c,然后将第4个盘子从a移动到柱子b,最后将前三个盘子借助a从柱子c移动到柱子b。。。。

    C++代码:

    #include<bits/stdc++.h>
    using namespace std;
    void hanoi(int n, char a, char b, char c){
    	if(n==1){
    		cout <<a<<"->"<<n<<"->"<<b;
    		return;
    	}else if(n==2){
    		cout <<a<<"->"<<n-1<<"->"<<c<<endl;
    		cout <<a<<"->"<<n<<"->"<<b<<endl;
    		cout <<c<<"->"<<n-1<<"->"<<b<<endl;
    		return;
    	}else{
    		hanoi(n-1,a,c,b);   //将n-1个盘子借助b从柱子a移到柱子c上
    		cout <<a<<"->"<<n<<"->"<<b<<endl;
    		hanoi(n-1,c,b,a);   //将n-1个盘子借助a从柱子c移到柱子b上
    	}
    }
    int main(){
    	int n;
    	char a='a',b='b',c='c';
    	cin>>n;
    	cin >>a>>b>>c;
    	hanoi(n,a,b,c);
    	
    	return 0;
    } 

     

    展开全文
  • 图解汉诺塔问题(递归求解)

    万次阅读 多人点赞 2018-05-26 18:59:14
    汉诺塔汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小...

    汉诺塔:汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。                        --引用维基百科

    单看这个问题描述有点让人抓瞎,这是当然,无论多么简单的问题描述,在没有建立具体地模型之前都是让人不知所云的,仅仅用生活中的语言去描述一些数学或算法问题往往会让听者产生理解偏差,这也和每个的理解能力和思维方式有很大关系,这就显示出数学的强大了,数学让问题不再模糊,参数和公式组成的模型让问题不再有理解偏差和误区,只可惜数学没学好,看来以后还得回来把高数、概率论这些给补回来。

    说了一些题外话,下面来对汉诺塔问题进行解释和建立模型


        这是示意图,a是起始柱,c是目标柱,b起到中转作用

        在进行转移操作时,都必须确保大盘在小盘下面,且每次只能移动一个圆盘,最终c柱上有所有的盘子且也是从上到下按从小到大的顺序。

        很多时候看到这些蛋疼和矫情操作就觉得数学家真是思维清奇、智慧如海,嗯还有吃饱了撑的,某兄台邪魅地一笑,道:直接把c和a交换位置不就行了,我想这位兄台以后或成大器或被人打死。

        问题看起来并不复杂,当a柱子上只有一个盘子时只要把那个盘子直接移到c就行了,

        有两个盘子的话把1号盘先移到b柱,在把2号盘移到c柱,最后把b柱上的1号盘移到c柱就行了,

        但现在我们要移动的是64个盘子,要是我们自己手动操作,那画面会很美,闲着无聊的人可以试试,推荐去网上找找汉诺塔的小游戏,这也可以帮你加深对这个问题的理解。

    下面我用图来描述64个盘子的转移流程

      

        这里我们先把上方的63个盘子看成整体,这下就等于只有两个盘子,自然很容易了,我们只要完成两个盘子的转移就行了,好了现在我们先不管第64个盘子,假设a柱只有63个盘子,与之前一样的解决方式,前62个盘子先完成移动目标。

        嗯,就这样一步步向前找到可以直接移动的盘子,62,61,60,......,2,1,最终,最上方的盘子是可以直接移动到c柱的,那就好办了,我们的2号盘也能完成向c柱的转移,这时c柱上时已经转移成功的2个盘,于是3号盘也可以了,一直到第64号盘。

        下面是我用C#实现的代码:

    using System;
    using System.Collections.Generic;
    
    namespace 汉诺塔问题_递归解决
    {
       
        class Program
        {       
            static void Main(string[] args)
            {
                HanNuo(64, 'a', 'b', 'c');
    
                Console.ReadKey();
            }
    
            /// <summary>
            /// 汉诺塔问题解决方法
            /// </summary>
            /// <param name="n">汉诺塔的层数</param>
            /// <param name="a">承载最初圆盘的柱子</param>
            /// <param name="b">起到中转作用的柱子</param>
            /// <param name="c">移动到的目标柱子</param>
            static void HanNuo(int n, char a, char b, char c)
            {
                if (n == 1)   //这也是递归的终止条件
                {
                    Console.WriteLine("将盘子[{0}]从 {1} -----> {2}", n, a, c); //控制台输出每次操作盘子的动向
                }
                else
                {
                    HanNuo(n - 1, a, c, b);      //将a柱子上的从上到下n-1个盘移到b柱子上
                    Console.WriteLine("将盘子[{0}]从 {1} -----> {2}", n, a, c);
                    HanNuo(n - 1, b, a, c);      //将b柱子上的n-1个盘子移到c柱子上
                }
            }
        }
    }

           代码很简洁,可能对于递归不是很理解的同学觉得有些吃力,下面我来具体解释下递归的流程。

           当n=64时,前63个要想办法成功移动到b柱上,64号是Boss,他不管上面的63个小弟用什么办法,我可以先等着,前面63个小弟可以利用我的c柱,于是64号在等着上面63号完成移到b柱,现在63是临时老大,他也想去c柱,于是他命令前62号移到b柱,他等着,62号也采取之前两个的做法,于是这个命令一直往前传,没办法,上面被压着自己也没法动啊。

            终于到了1号,他是现在唯一能动的,于是1号移动到了b柱,好了,2号可以到c柱,2第一个到目的地,心里十分激动,我都到c柱,舒服。不过当他看到a柱上的3号时,猛然一惊,我还有个上司,好吧得完成任务啊,于是让1号移到c柱,3号可以到b柱了,之后1号和2号在想办法到b柱,于是1,2,3号在b柱,4号一看很满意,但我得到b柱啊,嗯,1,2,3号你们按照刚才的办法到c柱,空出b柱给我。唉,接着折腾,后面的5号一直到63号都是这么折腾的,终于前63号移动到b柱,64号直接跑到了c柱,他觉得这些小弟办事效率真不行,不过他还是招呼小弟到c柱。

         于是剩下在b柱的63个小弟还要再干一遍他们在a柱上干的事,这里来看,1号操作的频率是最高的,而64号只要移动一次就行了,要是在现实中让人这么去干,估计早就被逼疯了。

          如果真要解释代码的每一步执行过程,那会很乱,两层递归,最后自己也会被绕的晕头转向,这个时候只要理解递归最终的解决的问题是什么就行了,中间的事交给程序,递归可以很绕也可以很直接,我们按照最直接的理解就行了。

      最后关于递归算法,这中解决问题的方法也只有计算机才喜欢,我们虽然看着代码很简单,但真要深入理解也是很费脑细胞的,不过递归确实有中数学上的简洁美和逻辑美。

    展开全文
  • 汉诺塔 终于弄明白了

    万次阅读 2012-11-24 16:53:54
    汉诺塔 ( 又称河内塔 ) 问题是源于印度一个古老传说的益智玩具 。 古代有一个梵塔 , 塔内 个座 A 、 B 、 C , A 座上有 64 个盘子 , 盘子大小不等 , 大的在下 , 小的在上 。 有一个和尚想把 个盘子从 A 座...
    /*
    汉诺塔 ( 又称河内塔 ) 问题是源于印度一个古老传说的益智玩具 。 古代有一个梵塔 , 塔内
    个座 A 、 B 、 C , A 座上有 64 个盘子 , 盘子大小不等 , 大的在下 , 小的在上 。 有一个和尚想把
    个盘子从 A 座移到 B 座 , 但每次只能允许移动一个盘子 , 并且在移动过程中 , 3 个座上的盘
    终保持大盘在下,小盘在上。在移动过程中可以利用 B 座,下面左图给出了移动方法的提示
    编制递归函数输出盘子数为 4 时 ( 程序调试后 , 试试 15 个 、 20 个 , 直至 64 个 , 看看会如何
    动的方案。
    */
    /*
    * 程序的版权和版本声明部分
    * Copyright (c)2012, 烟台大学计算机学院学生
    * All rightsreserved.
    * 文件名称: x.cpp
    * 作者:徐本锡
    * 完成日期: 2012年 11 月24  日
    * 版本号: v1.0
    * 输入描述:无
    
    * 问题描述:无
    
    * 程序输出:步骤
    
    */
    //我的代码:
    
    #include <iostream>
    using namespace std;
    const int discCount=3;//定义个数
    void move(int n, char A, char B,char C);//声明函数
    int main()
    { 
    	move(discCount,'A','B','C');
    	return 0;
    }
    void move(int n, char A, char B,char C)//自定义函数
    {
    	if(n==0)//盘子为0的时候返回
    	{
    		return;
    	}
    	else
    	{
    		move(n-1,A,C,B);//先从A到B
    		cout<<A<<"-->"<<C<<endl;//再从A到C
    		move(n-1,B,A,C);//最后从B到C
    		return;
    	}
    }

    展开全文
  • 汉诺塔最清晰的理解

    万次阅读 多人点赞 2018-10-01 20:16:18
    汉诺塔最清晰的理解——从函数调用角度 阅读本文,你将会理解: 汉诺塔规律 汉诺塔算法函数递归调用次序 清晰明了的认识(不是靠死背,能够在头脑中想象,能够独立写出算法) 汉诺塔: 法国数学家爱德华·...

                                                   汉诺塔最清晰的理解——从函数调用角度

    • 阅读本文,你将会理解:
    1. 汉诺塔规律
    2. 汉诺塔算法函数递归调用次序
    3. 清晰明了的认识(不是靠死背,能够在头脑中想象,能够独立写出算法)

    • 汉诺塔:
    1. 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。(如图,看得一脸懵逼,不慌,大佬带你飞,往下看)

                      

                                                                          

     

     

     2.汉诺塔的编程解决算法:递归实现。什么是递归?

    • 程序调用自身的编程技巧称为递归( recursion),例如:

    void fun()

    {

            fun();

    }

    • 递归在计算机中是怎么运行的,次序是怎样的?,如:

    int main(void)

    {

              fun();

    }

    不好意思,如果你这么写的话,程序要炸,你会发现内存被耗尽,电脑死机,别去尝试!

    fucking why?

    首先,我们要知道,计算机是怎么调用函数的

    • 第一步:当前计算机环境入栈,保存计算机的状态,比如运行到哪儿,保存入参,局部变量等,这是用栈保存的,是耗内存的。
    • 第二步:调用函数。
    • 第三步:返回,将第一步过程中入栈的计算机环境出栈,继续往下运行。

    那么,递归,函数自己调用自己,将会发生什么?

    永远循环在第一步和第二步,不断的耗尽内存,直到崩溃。

    所以说,老司机告诫递归函数要有返回的条件,就是不要一直循环下去。

    什么是返回的条件?就是导演喊‘咔’,不要往下演了,如下:计算n+(n-1)+...+2+1

    int fun(int n) 

      

        if(n>0)

        {        

       

                      return n+fun(n-1);

        }

        else

        {

                     return 0;

        }

    int main(void)

    {

              int sum = 0;

              sum = fun(10);

              printf("sum = : %d",sum);

    }

    用小拇指算一下,是不是等于55.

    函数调用过程:

    fun函数是可以看成这样(只是变变形式而已):

    int fun(int n) 

      

        if(n>0)

        {         

                      n = n+fun(n-1);

                      return n;

        }

        else

        {

                     return 0;

        }

    可想而知函数执行过程中:

    开始:入参n=10调用fun(10-1),即fun(9),把9当做入参,n=9,调用fun(9-1),n=8,依次下去,直到n=0,

    这时候

    • n=0,return 0
    • return后回到1+fun(0),fun(0) 返回0,则执行1+0,返回1+0=1,return 1
    • return后回到2+fun(1),fun(1) 返回1,则执行2+1,返回2+1=1,return 3
    • .
    • .
    • .
    • return 后回到10+fun(9),fun(9)返回9+8+...+2+1+0,则执行45+10=55,return 55,即是结果:

    妙吧?

    如果不太清楚,请仔细重复一二。

     

    3.汉诺塔编程算法

    先不解释,看看代码,一下子是想不出来的,我们可以从代码的运行过程中找到解决的思路,这是一种方法之一,简称:逆向工程。

    (快速浏览一下代码,在往下看下面的解释)

    #include<stdio.h>
    #include<stdlib.h>
    static int count = 0;
    void move(char getone, char putone) {
        
        count ++;
        printf("%c-->%c\n", getone, putone);
    }
     
    void hanoit(int n, char a, char b, char c) {
        if(n == 1)
        {
            move(a, c);
        } 
        else
        {
            hanoit(n - 1, a, c, b);
            printf("count :%d\n",count);
            move(a, c);
            hanoit(n - 1, b, a, c);
        }
     
    }
     
    int main() {
        int m;
        
        scanf("%d", &m);
        hanoit(m, 'A', 'B', 'C');
        printf("count :%d",count);
     
        system("pause");
        return 0;
    }

                                                                         

     

    上图中,有三根棒,左中右,分别命名为'A','B','C',移动‘A’棒的圆片到‘B’棒上,代码执行为:move('A','B')

    依次类推:如吧'C'棒移动到‘A’棒,为move('C',‘A’)。

    先从简单的开始,假设有三个圆片,最初从小到大放在A棒,移动之后,要从小到大依次放在C棒,圆片根据小到大命名:1,2,3

    第一步,将1从A棒移动到C棒

    第二步,将2从A棒移动到B棒

    第三步,将1从C棒移动到B棒

    第四步,将3从A棒移动到C棒

    第五步,将1从B棒移动到A棒

    第六步,将2从B棒移动到C棒

    第七步,将1从A棒移动到C棒

    此时,圆盘1,2,3按从小到大依次排列依次在C棒上,移动的过程中没有违背规则:不管在哪根棒上,小片必须在大片上面

    如有不清楚,请重复一二。

    如果清晰明白了上面的移动次序,结合递归,我们来破解一下汉诺塔程序:

     

    void hanoit(int n, char a, char b, char c) {
        if(n == 1)
        {
            move(a, c);
        } 
        else
        {
            hanoit(n - 1, a, c, b);
            printf("count :%d\n",count);
            move(a, c);
            hanoit(n - 1, b, a, c);
        }
     
    }

    观察:

    第一眼:发现函数自己调用自己,使用递归,第二眼发现n 取值为1时有返回,程序不会炸,第三眼发现是递减调用:hanoit(n - 1, a, c, b);

    假设执行:hanoit(10, 'A', 'B', 'C'),一共有10个圆盘。

    那么递归调用次序(从计算机调用角度,因为调用过程参数顺序发生变化,索性使用r1,r2,r3代表,注意入参为n-1):

    hanoit(9, 'A', 'B', 'C')

             -->hanoit(8, r1, r2, r3)

                        --->hanoit(7, r1, r2, r3) 

                                .............依次一下去

                              move(a,c)

                              hanoit(7, r1, r2, r3)

                              move(a,c)

                 hanoit(8, r1, r2, r3)

    move(a,c)

    hanoit(9, b, a, c)

    .....

    简单检验:假设n =3

    执行:hanoit(3, 'A', 'B', 'C')

    调用次序(r1, r2, r3为实际使用的第一个,第二个,第三个参数,注意入参为n-1)

    开始:

    1.hanoit(2, r1, r2, r3)    

               2.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第一次move

               3.move(r1, r3);-----------------------------------------------------------------------------------执行第二次move

               4.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第三次move

    5.move(a, c);----------------------------------------------------------------------------------------------执行第四次move

    6.hanoit(2, r1, r2, r3)

               7.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第五次move

               8.move(r1, r3);-----------------------------------------------------------------------------------执行第六次move

               9.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第七次move

    结束(一共执行7次move ,也就是2^n-1,即n = 3,2^3-1 = 7次)

    在程序中执行如下(图):

    码源:https://download.csdn.net/download/yangming2466/10699026

     

    为什么是2^n-1 次move?

    我们知道唯一的返回条件的n==1,n==1 执行move,即:

               1.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第一次move,返回

               2.move(r1, r3);-----------------------------------------------------------------------------------执行第二次move

               3.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第三次move,返回

    那么n=3 的时候可以这么拆分

    2

         1  (执行一次)

         1  (执行一次)

         1  (执行一次)

    1 (执行一次)

    2

          1 (执行一次)

          1 (执行一次)

          1 (执行一次)

    把一的个数数起来,就是执行move的次数,我们知道2^n<十进制> -1= 1111...(n个1)...111 <二进制>

    我们知道  {1111...(n个1)...111 <二进制>} = {1111...(n-1个1)...111 <二进制>} + 1 + {1111...(n-1个1)...111 <二进制>}

    例如 1111<二进制> = 15,111<二进制> = 7,15 = 7 + 1 + 7,即:1111<二进制> = 111<二进制> + 1 + 111<二进制>

    可能有人问了:what are you doing ?

    注意看:

    hanoit(2, r1, r2, r3):

              1.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第一次move,返回

               2.move(r1, r3);-----------------------------------------------------------------------------------执行第二次move

               3.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第三次move,返回

    n = 2,执行次数是3,等于11<二进制>,岂不是可以这样拆分

    111拆分

    start:

    11

         1

         1

         1

    -----------------------------------------------

    1

    ----------------------------------------------- 

    11

          1

          1

          1

    end

    这是和递归调用的深度数是何其的相似!1的个数 = 111<二进制> = 2^n-1,得出了这个结论,下面我们来说说递推的移动过程:

    我们来详细把三个圆盘的移动推导过程过一下,特别是入参:

    函数

    void hanoit(int n, char a, char b, char c) {
        if(n == 1)
        {
            move(a, c);
        } 
        else
        {
            hanoit(n - 1, a, c, b);
            printf("count :%d\n",count);
            move(a, c);
            hanoit(n - 1, b, a, c);
        }
     
    }

    开始:

    (r1, r2, r3为当前函数实际使用的第一个,第二个,第三个参数)

     hanoit(3, 'A', 'B', 'C')---------------r1= 'A',r2='B',r3='C'

    1.hanoit(2, r1, r2, r3)---------------r1= 'A',r2='C',r3='B'

               2.hanoit(1, r1, r2, r3)------r1= 'A',r2='B',r3='C'--------------执行第一次move(r1,r3),即move("A', 'C')

               3.move(r1, r3);-----------------------------------------------------执行第二次move(r1,r3),即move('A', 'B')

               4.hanoit(1, r1, r2, r3)------r1= 'C',r2='A',r3='B'--------------执行第三次move(r1,r3),即move('C','B')

    5.move(a, c);----------------------------------------------------------------执行第四次move ( r1,r3 ),  即move('A','C')

    6.hanoit(2, r1, r2, r3)

               7.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第五次move

               8.move(r1, r3);-----------------------------------------------------------------------------------执行第六次move

               9.hanoit(1, r1, r2, r3)---------------------------------------------------------------------------执行第七次move

    结束(一共执行7次move ,也就是2^n-1,即n = 3,2^3-1 = 7次)

    实践是检验真理的唯一标准:

    码源:https://download.csdn.net/download/yangming2466/10699026

    此时,圆盘1,2,3按从小到大依次排列依次在C棒上,移动的过程中没有违背规则:不管在哪根棒上,小片必须在大片上面。

    我们再从逻辑宏观来分析:为什么能?

    推广到三阶的时候,我们将小环和中环视为一个整体,变成了执行二阶汉诺塔
    那么四阶前三个环视为整体,五阶前四个环视为整体…

     

     

     

                                       

    展开全文
  • C++ - 汉诺塔

    万次阅读 多人点赞 2019-03-14 10:18:06
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net /* * Created by Chimomo */ #include &lt;iostream&...l...
  • 汉诺塔问题——递归(时隔9个月,终于懂了)

    万次阅读 多人点赞 2020-02-08 12:04:29
    记得我第一次做汉诺塔这道题时,是2017年11月。当时,我坐在山大青岛校区图书馆3楼,不知怎么地,看到了这个题。 然后,就思考了一整天,233 当然,悲剧就是,我当时花了一天的时间还是没有真正理解这道题递归的...
  • 搞定汉诺塔
  • 汉诺塔问题(Hanoi)

    千次阅读 2018-08-28 16:03:45
    一、汉诺塔问题  有三根杆子A,B,C。A杆上有N个(N&gt;1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆: 每次只能移动一个圆盘; 大盘不能叠在小盘上面。 提示:可将圆盘临时置于B杆...
  • 汉诺塔递归调用(C语言实现)

    万次阅读 多人点赞 2020-07-30 23:41:24
    1.递归算法 递归算法:是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 递归过程一般通过函数或子过程来实现。...
  • 用递归算法的来解决汉诺塔问题

    万次阅读 多人点赞 2018-01-23 23:48:05
    汉诺塔 汉诺塔是一个发源于印度的益智游戏,也叫河内塔。相传它源于印度神话中的大梵天创造的三个金刚柱,一根柱子上叠着上下从小到大64个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序移动到另一根柱子...
  • 汉诺塔问题(C++)

    千次阅读 多人点赞 2018-08-19 18:50:51
    汉诺塔问题 题目描述 n个圆盘从下面开始按大小顺序摆放在A柱子上。并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘,求最少的移动步骤。 输入输出格式 输入格式:...
  • 用栈实现汉诺塔

    万次阅读 2016-11-16 09:32:56
    汉诺(Hanoi)塔问题 又称为河内塔问题。有位僧人整天把三根柱子上的金盘倒来倒去,原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。...由于汉诺塔的规则与栈的规则类似(先入后出
  • 递归经典案例汉诺塔 python实现

    万次阅读 多人点赞 2018-07-16 10:42:51
     学到递归的时候有个汉诺塔的练习,汉诺塔应该是学习计算机递归算法的经典入门案例了,所以本人觉得可以写篇博客来表达一下自己的见解。这markdown编辑器还不怎么会用,可能写的有点格式有点丑啦,各位看官多多见谅...
  • 汉诺塔问题求解(递归)

    万次阅读 2019-12-22 14:12:35
    汉诺塔问题的描述如下:有A、B和C 3跟柱子,在A上从下往上按照从小到大的顺序放着64个圆盘,以B为中介,把盘子全部移动到C上。移动过程中,要求任意盘子的下面要么没有盘子,要么只能有比它大的盘子。本实例将演示...
  • 汉诺塔图文详解

    2020-05-14 09:45:36
    汉诺塔汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序...
  • 四柱汉诺塔

    千次阅读 2016-04-21 20:15:19
    四柱汉诺塔变体汉诺塔 问题描述:在经典汉诺塔的基础上加一个条件,即,如果再加一根柱子(即现在有四根柱子a,b,c,d),计算将n个盘从第一根柱子(a)全部移到最后一根柱子(d)上所需的最少步数,当然,也不能够出现大...
  • 汉诺塔 汉诺塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔...
  • N柱汉诺塔问题_转载

    2018-01-25 12:48:09
    汉诺塔算法一直是算法设计科目的最具代表性的研究问题,本文关注于如何设计多柱汉诺塔最优算法的探究。最简单的汉诺塔是三个柱子(A、B、C),因此多柱汉诺塔的柱子个数M≥3。下面从三柱汉诺塔说起,慢慢深入我们要...
  • python关于汉诺塔代码的理解

    千次阅读 2018-11-16 09:36:30
    python关于汉诺塔代码的理解 递归函数经典 本人小白一枚,今天接触到递归函数,顺便也接触到了汉诺塔这个经典例题,在网上搜了一遍教程和代码,自己琢磨后也是第一次写这个文章。写自己的感想、感悟和思路。希望各路...
  • 汉诺塔代码执行过程

    2019-10-09 13:55:14
    汉诺塔规则 a、b、c三座塔,将n个从小到大(自上而下)的圆盘从a移动到c,移动期间小圆盘必须在大圆盘上面,且每次移动一个,问移动步骤。 汉诺塔解决办法 请见图 3. 汉诺塔执行代码 #include<stdio.h>...
1 2 3 4 5 ... 20
收藏数 19,804
精华内容 7,921
关键字:

汉诺塔