孤步 / c / 汉诺塔问题递归算法分析

分享

   

汉诺塔问题递归算法分析

2012-07-27  孤步


汉诺塔问题递归算法分析:

递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展,逐步迫近循环终止条件。

递归函数也是如此,它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时,它便不在调用自身。


递归算法的特点

  递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。

  递归算法解决问题的特点:

  (1) 递归就是在过程或函数里调用自身。

  (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

  (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

  (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

递归算法要求

  递归算法所体现的重复一般有三个要求:

  一是每次调用在规模上都有所缩小(通常是减半)

  二是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)

三是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。

  一个庙里有三个柱子,第一个有64个盘子,从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。

  1、此时老和尚(后面我们叫他第一个和尚)觉得很难,所以他想:要是有一个人能把前63个盘子先移动到第二个柱子上,我再把最后一个盘子直接移动到第三个柱子,再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上,我的任务就完成了,简单。所以他找了比他年轻的和尚(后面我们叫他第二个和尚),命令:

          你丫把前63个盘子移动到第二柱子上

          然后我自己把第64个盘子移动到第三个柱子上后

          你把前63个盘子移动到第三柱子上

      2
、第二个和尚接了任务,也觉得很难,所以他也和第一个和尚一样想:要是有一个人能把前62个盘子先移动到第三个柱子上,我再把最后一个盘子直接移动到第二个柱子,再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上,我的任务就完成了,简单。所以他也找了比他年轻的和尚(后面我们叫他第三和尚),命令:

          你把前62个盘子移动到第三柱子上

          然后我自己把第63个盘子移动到第二个柱子上后

          你把前62个盘子移动到第二柱子上

  3、第三个和尚接了任务,又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚,等等递推下去,直到把任务交给了第64个和尚为止(估计第64个和尚很郁闷,没机会也命令下别人,因为到他这里盘子已经只有一个了)。

  4、到此任务下交完成,到各司其职完成的时候了。完成回推了:

64个和尚移动第1个盘子,把它移开,然后第63个和尚移动他给自己分配的第2个盘子。
64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成,第63个和尚完成了第62个和尚交给他的任务的第一步。

从上面可以看出,只有第64个和尚的任务完成了,第63个和尚的任务才能完成,只有第2个和尚----64个和尚的任务完成后,第1个和尚的任务才能完成。这是一个典型的递归问题。


/************************************************************************/

/*

现在我们以有3个盘子来分析:

1个和尚命令:

2个和尚你先把第一柱子前2个盘子移动到第二柱子。(借助第三个柱子)

1个和尚我自己把第一柱子最后的盘子移动到第三柱子。

2个和尚你把前2个盘子从第二柱子移动到第三柱子。

   很显然,第二步很容易实现(哎,人总是自私地,把简单留给自己,困难的给别人)。

其中第一步,第2个和尚他有2个盘子,他就命令:

3个和尚你把第一柱子第1个盘子移动到第三柱子。(借助第二柱子)

2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。

3个和尚你把第1个盘子从第三柱子移动到第二柱子。

   同样,第二步很容易实现,但第3个和尚他只需要移动1个盘子,所以他也不用在下派任务了。

(注意:这就是停止递归的条件,也叫边界值)

第三步可以分解为,第2个和尚还是有2个盘子,命令:

3个和尚你把第二柱子上的第1个盘子移动到第一柱子。

2个和尚我把第2个盘子从第二柱子移动到第三柱子。

3个和尚你把第一柱子上的盘子移动到第三柱子。

 

  分析组合起来就是:13 12 32 借助第三个柱子移动到第二个柱子

  |13 自私人留给自己的活| 21 23 13 借助第一个柱子移动到第三个柱子|共需要七步。

 

       如果是4个盘子,则第一个和尚的命令中第1步和第3步各有3个盘子,

       所以各需要7步,共14步,再加上第1个和尚的1步,

       所以4个盘子总共需要移动 7+1+7=15步,

       同样,5个盘子需要15+1+15=31步,6个盘子需要31+1+31=64步……

       由此可以知道,移动n个盘子需要(2n次方)-1步。

     

  从上面整体综合分析可知把n个盘子从1座(相当第一柱子)移到3座(相当第三柱子):

  1)把1座上(n-1)个盘子借助3座移到2座。

  2)把1座上第n个盘子移动3座。

  3)把2座上(n-1)个盘子借助1座移动3座。

 

       下面用hanoin,a,b,c)表示把1n个盘子借助2座移动到3座。

      

         很明显:   

         (1)步上是 hanoi(n-1,1,3,2)

         (3)步上是 hanoi(n-1,2,1,3)

         C语言表示出来,就是:

 

把第 1 个盘子 A 搬到 C

把第 2 个盘子 A 搬到 B

把第 1 个盘子 C 搬到 B

把第 3 个盘子 A 搬到 C

把第 1 个盘子 B 搬到 A

把第 2 个盘子 B 搬到 C

把第 1 个盘子 A 搬到 C

                                                                     */

/************************************************************************/

#include <stdio.h>

#include <iostream>

using namespace std;

 

//入参int n:代表第n个盘子

int move(int n,char a, char b)

{

       printf("==>==>:    把第 %d 个盘子 %c 搬到 %c\n\n",n,a,b);

              return 0;

}

 

//入参int n:代表 共剩余n个盘子

int hanoi(int n,char a,char b,char c)

{

       cout<<"******************int hanoi(int n,char a,char b,char c) begin!!!"<<endl;

       if (n == 1)

       {

              cout<<"剩余盘子数 n="<<n<<",盘子在"<<a<<"座上,可以直接搬到"<<c<<""<<endl;

       }

       else

       {

              cout<<"剩余盘子数 n="<<n<<",盘子在"<<a<<"座上,需借助"<<b<<"座,搬到"<<c<<""<<endl;

       }

      

       if( n==1 )

       {

              cout<<endl<<"11111=>: ";

              move (1,a,c);

       }

       else

       {

              hanoi(n-1,a,c,b);//根据上面解说知道:移动n个盘子需要(2n次方)-1步,这里需要移动n-1个盘子需要(2n次方)-2步,也就是说这里的第一轮递归 要进行 n-1 层递归循环,才会结束调用,完成 将  n-1 个盘子从a座上借助c座,最终放到了b座上,

              move(n,a,c);//完成 将 最后一个盘子即第 n 个盘子从a座上放到了c座上,至此完成第一轮的调用,其结果是将最后一个盘子完成了任务,其余的盘子都还在b座上放着呢,下面一步是对剩余的n-1个盘子进行新一轮的递归调用

              hanoi(n-1,b,a,c);//开启新一轮的递归调用

       };

 

       if (n == 1)

       {

              cout<<"对应-----------剩余盘子数 n="<<n<<",盘子在"<<a<<"座上,可以直接搬到"<<c<<""<<endl;

       }

       else

       {

              cout<<"对应-----------剩余盘子数 n="<<n<<",盘子在"<<a<<"座上,需借助"<<b<<"座,搬到"<<c<<""<<endl;

       }

       cout<<"int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@"<<endl<<endl;

      

      return 0;

 }

int main()

{

       freopen("hanoi.in","r",stdin);

 

       freopen("hanoiOutPut.txt","w",stdout);

       int num;

       scanf("%d",&num);

       cout<<"开始"<<endl<<endl;

       hanoi(num,'A','B','C');

       cout<<endl<<endl<<"结束"<<endl<<endl;

       return 0;

}

 

 

开始

 

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=3,盘子在A座上,需借助B座,搬到C

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=2,盘子在A座上,需借助C座,搬到B

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1,盘子在A座上,可以直接搬到C

 

11111=>: ==>==>:  把第 1 个盘子 A 搬到 C

 

对应-----------剩余盘子数 n=1,盘子在A座上,可以直接搬到C

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

==>==>: 把第 2 个盘子 A 搬到 B

 

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1,盘子在C座上,可以直接搬到B

 

11111=>: ==>==>:  把第 1 个盘子 C 搬到 B

 

对应-----------剩余盘子数 n=1,盘子在C座上,可以直接搬到B

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

对应-----------剩余盘子数 n=2,盘子在A座上,需借助C座,搬到B

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

==>==>: 把第 3 个盘子 A 搬到 C

 

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=2,盘子在B座上,需借助A座,搬到C

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1,盘子在B座上,可以直接搬到A

 

11111=>: ==>==>:  把第 1 个盘子 B 搬到 A

 

对应-----------剩余盘子数 n=1,盘子在B座上,可以直接搬到A

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

==>==>: 把第 2 个盘子 B 搬到 C

 

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1,盘子在A座上,可以直接搬到C

 

11111=>: ==>==>:  把第 1 个盘子 A 搬到 C

 

对应-----------剩余盘子数 n=1,盘子在A座上,可以直接搬到C

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

对应-----------剩余盘子数 n=2,盘子在B座上,需借助A座,搬到C

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

对应-----------剩余盘子数 n=3,盘子在A座上,需借助B座,搬到C

int hanoi(int n,char a,char b,char c) end end  end end end end @@@!!!@@@

 

 

 

结束

 

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    来自: 孤步 > 《c》

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>