您现在的位置: 华盟网 >> 编程 >> C语言 >> 正文

C++汉诺塔算法

2015/3/17 作者:admin 来源: 网络收集
导读 汉诺塔是递归的一个非常典型的问题。    汉诺塔问题的描述是:有三根柱子(A、B、C),A柱子上有n个圆盘(由下到上逐个减小),现在要将A柱子上的n个圆盘移到C…
汉诺塔是递归的一个非常典型的问题。

    汉诺塔问题的描述是:有三根柱子(A、B、C),A柱子上有n个圆盘(由下到上逐个减小),现在要将A柱子上的n个圆盘移到C柱子上,可以借助B柱子,要求小圆盘上不能放大圆盘,并且每次只能移动一个圆盘。

    首先让我们分析一下汉诺塔问题,汉诺塔可以用递归解决,要完成递归算法我们需要找到两个要素①、递归出口;②、组成大问题的小块循环。

    1、递归出口

    显然汉诺塔的递归出口是当n=1时,我们只需要将A柱子上的圆盘直接拿到C柱子上就可以了。

    2、大问题的小块循环

    这里我们不妨用当n=2时来推断出其小块的规律。

    当n=2时(即A柱子上有两个圆盘要移动到C柱子上),我们需要做的是:

    ①:A----1---->B(将1号圆盘从A柱子移动到B柱子)

    ②:A----2---->C

    ③:B----1---->C

    由此我们可以推断出汉诺塔的规律,即有n个圆盘时:

    ①:A----n-1---->B(将n-1号圆盘由A柱子移动到B柱子上)

    ②:A----n---->C(将n号圆盘由A柱子移动到C柱子上)

    ③:B----n-1---->C(将n-1号圆盘由B柱子移动到C柱子上)

    得到两个递归条件之后我们可以写出递归算法的程序了,在这里笔者用C语言实现。

    #include<stdio.h>

    //递归函数

    void hanoi(int n,char x,char y,char z) {

    if(n==1) {//递归出口

    printf("将编号为%d的盘子从%c柱子物体移动到%c柱子上\n",n,x,z);

    }else{//小块循环

    hanoi(n-1,x,z,y);

    printf("将编号为%d的盘子从%c柱子物体移动到%c柱子上\n",n,x,z);

    hanoi(n-1,y,x,z);//调用自身递归,进行下一步

    }

    }

    int main(void) {

    char A = 'A';//第一根柱子

    char B = 'B';//第二根柱子

    char C = 'C';//第三根柱子

    int n;//需要移动圆盘的数量

    scanf("%d",&n);

    hanoi(n,A,B,C);

    }

    笔者认为汉诺塔问题比较抽象,我们要从分析递归问题的角度去解决汉诺塔问题,这样有利于我们快速掌握。还有一个扩展和大家分享一下(移动n个盘子的最少移动次数是:2^n - 1,大家不妨可以试一下)。

                  微信群名称:华盟黑白之道二群   华盟-黑白之道⑦QQ群: 9430885

  • 上一篇编程:

  • 下一篇编程:
  • 网友评论
      验证码
     

    关注

    分享

    0

    讨论

    2

    猜你喜欢

    论坛最新贴