“汉诺塔”算法


作者:xcbeyond
疯狂源自梦想,技术成就辉煌!微信公众号:《程序猿技术大咖》号主,专注后端开发多年,拥有丰富的研发经验,乐于技术输出、分享,现阶段从事微服务架构项目的研发工作,涉及架构设计、技术选型、业务研发等工作。对于Java、微服务、数据库、Docker有深入了解,并有大量的调优经验。 






   


问题描述:

      

           “汉诺塔”问题有时大家有把它习惯的叫做“和尚搬塔”,它来自有古老的印度:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。
问题分析:     

             

            对于这个问题肯定是搬一辈子都搬不完的,以下分析其过程,看到底搬得完不?

             假如只有1个盘,则需搬动1次;

              假如只有2个盘,则需搬动3次;

              假如只有3个盘,则需搬动8次;

              假如只有4个盘,则需搬动15次;

              ……

              不难归纳得到:当有n个盘时,需搬移2的n次方减1.

因此,当有64个盘(n=64)时,需要移动2的64次方减1次,这个数字是大的吓人吧,再转化一下就知道要多少年了,所以是一辈子也无法搬完的。

然而,我又为何要研究其算法啊?这个问题我还真不知道,但归咎我们还是可以思考一下其移动的过程,是如何移动的啊!
算法研究(实现):

           

         先将这个问题构建一个简单的数学模型,以方便研究。假设三根柱子分别编号为A,B,C,盘的个数为n,A柱子上从下到上按由大到小叠放着n个的圆盘,现在把所有盘子一个一个移动到柱子C上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动?

    肯定的是说把上面n-1个盘子移动到柱子B上,然后把最大的一块放在C上,实现第一轮的移动,最后把B上的所有盘子移动到C上,以此移动最终可以完成其要求。也就是个递归问题,由此得到类似阶乘算法的递归出表达式:   h(1) = 1   h(n) = 2*h(n-1)+1      (n>1)                    知道“斐波那契”数列的人,就比较容易推出这个表达式了。

其递归算法如下:(觉得这个算法是比较完美的,所以就用它了)

————————————————————————————————————-

#include”stdio.h”

void hanoi(int n,char one,char two,char three);
void move(char x,char y);

void main()
{
        int m;
  printf(“————-hanoi—————-\n”);
        printf(“input the number of plates:”);
        scanf(“%d”,&m);
        printf(“The step to move %d plates:\n”,m);
        hanoi(m,’A',’C',’B');
}
//汉诺塔
void hanoi(int n,char one,char two,char three)
{
        if (n==1)
        {
           move(one,three);

        }
        else
        {
            hanoi(n-1,one,three,two);
            move(one,three);
            hanoi(n-1,two,one,three);
        }
}
//每次移动的顺序
void move(char x,char y)
{
        printf(“%c–>%c\n”,x,y);
}

本算法是输出的移动盘的顺序!

     如果是6个盘,最终要全部从A移到C,即移动的顺序为:ABACBCABCACBAB

望诸位共同继续探讨“汉诺塔”问题,以求得到更完美的理解与算法。