“漢諾塔”算法


作者：xcbeyond
瘋狂源自夢想，技術(shù)成就輝煌！微信公眾號：《程序猿技術(shù)大咖》號主，專注后端開發(fā)多年，擁有豐富的研發(fā)經(jīng)驗，樂于技術(shù)輸出、分享，現(xiàn)階段從事微服務(wù)架構(gòu)項目的研發(fā)工作，涉及架構(gòu)設(shè)計、技術(shù)選型、業(yè)務(wù)研發(fā)等工作。對于Java、微服務(wù)、數(shù)據(jù)庫、Docker有深入了解，并有大量的調(diào)優(yōu)經(jīng)驗。 






   


問題描述：

      

           “漢諾塔”問題有時大家有把它習(xí)慣的叫做“和尚搬塔”，它來自有古老的印度：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。
問題分析：     

             

            對于這個問題肯定是搬一輩子都搬不完的，以下分析其過程，看到底搬得完不？

             假如只有1個盤，則需搬動1次；

              假如只有2個盤，則需搬動3次；

              假如只有3個盤，則需搬動8次；

              假如只有4個盤，則需搬動15次；

              ……

              不難歸納得到：當有n個盤時，需搬移2的n次方減1.

因此，當有64個盤（n=64）時,需要移動2的64次方減1次，這個數(shù)字是大的嚇人吧，再轉(zhuǎn)化一下就知道要多少年了，所以是一輩子也無法搬完的。

然而，我又為何要研究其算法?。窟@個問題我還真不知道，但歸咎我們還是可以思考一下其移動的過程，是如何移動的??！
算法研究（實現(xiàn)）：

           

         先將這個問題構(gòu)建一個簡單的數(shù)學(xué)模型，以方便研究。假設(shè)三根柱子分別編號為A,B,C,盤的個數(shù)為n,A柱子上從下到上按由大到小疊放著n個的圓盤，現(xiàn)在把所有盤子一個一個移動到柱子C上，并且每次移動同一根柱子上都不能出現(xiàn)大盤子在小盤子上方，請問至少需要多少次移動？

    肯定的是說把上面n-1個盤子移動到柱子B上，然后把最大的一塊放在C上，實現(xiàn)第一輪的移動，最后把B上的所有盤子移動到C上，以此移動最終可以完成其要求。也就是個遞歸問題，由此得到類似階乘算法的遞歸出表達式： 　　h(1) = 1 　　h(n) = 2*h(n-1)+1      (n>1)                    知道“斐波那契”數(shù)列的人，就比較容易推出這個表達式了。

其遞歸算法如下：(覺得這個算法是比較完美的，所以就用它了)

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

#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

望諸位共同繼續(xù)探討“漢諾塔”問題，以求得到更完美的理解與算法。