關于漢諾塔問題的最終解決

問題的提出:約19世紀末，在歐州的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個圓盤構(gòu)成的塔。目的是將最左邊桿上的盤全部移到右邊的桿上，條件是一次只能移動一個盤，且不允許大盤放在小盤的上面。
    *問題分析與算法設計
    這是一個的問題，幾乎所有的教材上都有這個問題。由于條件是一次只能移動一個盤，且不允許大盤放在小盤上面，所以64個盤的移動次數(shù)是：
     18，446，744，073，709，551，615
    這是一個天文數(shù)字，若每一微秒可能計算(并不輸出)一次移動，那么也需要幾乎一百萬年。我們僅能找出問題的解決方法并解決較小N值時的漢諾塔，但很難用計算機解決64層的漢諾塔。
    分析問題，找出移動盤子的正確算法。
    首先考慮a桿下面的盤子而非桿上最上面的盤子，于是任務變成了：
    *將上面的63個盤子移到b桿上；
    *將a桿上剩下的盤子移到c桿上；
    *將b桿上的全部盤子移到c桿上。
    將這個過程繼續(xù)下去，就是要先完成移動63個盤子、62個盤子、61個盤子....的工作。
    為了更清楚地描述算法，可以定義一個函數(shù)movedisc(n,a,b,c)。該函數(shù)的功能是：將N個盤子從A桿上借助C桿移動到B桿上。這樣移動N個盤子的工作就可以按照以下過程進行：
     1) movedisc(n-1,a,c,b);
     2) 將一個盤子從a移動到b上；
     3) movedisc(n-1,c,b,a)；
     重復以上過程，直到將全部的盤子移動到位時為止。
    *程序與程序注釋
    #include
    void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
    int i=0;
    void main()
    {
     unsigned n;
     printf("please enter the number of disc:");
     scanf("%d",&n); /*輸入N值*/
     printf("\tneedle:\ta\t b\t c\n");
     movedisc(n,'a','c','b'); /*從A上借助B將N個盤子移動到C上*/
     printf("\t Total: %d\n",i);
    }
    void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
    {
     if(n>0)
     {
     movedisc(n-1,fromneedle,usingneedle,toneedle);
     /*從fromneedle上借助toneedle將N-1個盤子移動到usingneedle上*/
     ++i;
     switch(fromneedle) /*將fromneedle 上的一個盤子移到toneedle上*/
     {
     case 'a': switch(toneedle)
     {
     case 'b': printf("\t[%d]:\t%2d.........>%2d\n",i,n,n);
     break;
     case 'c': printf("\t[%d]:\t%2d...............>%2d\n",i,n,n);
     break;
     }
     break;
     case 'b': switch(toneedle)
     {
     case 'a': printf("\t[%d]:\t%2d<...............>%2d\n",i,n,n);
     break;
     case 'c': printf("\t[%d]:\t %2d........>%2d\n",i,n,n);
     break;
     }
     break;
     case 'c': switch(toneedle)
     {
     case 'a': printf("\t[%d]:\t%2d<............%2d\n",i,n,n);
     break;
     case 'b': printf("\t[%d]:\t%2d<........%2d\n",i,n,n);
     break;
     }
     break;
     }
     movedisc(n-1,usingneedle,toneedle,fromneedle);
     /*從usingneedle上借助fromneedle將N-1個盤子移動到toneedle上*/
     }
    }