C趣味編程百例(31)漢諾塔

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