アルゴリズムのハノイの塔

1382 ワード

ハノイのタワープログラマーはよく知っているはずですが、背景を簡単に紹介します.
伝说の创世纪の时、Benaresに1基のポロ教塔があって、3本のダイヤモンドの棒で支えて、神は第1本の柱の上で64个の金盘を置いて、金盘は上から下まで顺次小さくて大きいです.神は僧侶に最初の柱から金盤を3本目の柱に移すように命令し、移動する過程で、ずっと大皿を下に保つ.皿が全数運ばれると、塔は自壊し、世界の終わりになる.
この問題の簡単な解決策は次のとおりです.
抽象的な3本の柱はA,B,Cで、簡単な皿から類推されます.
ディスクが1つしかない場合は、そのディスクをA->Cから
void hanoi(int n, char A, char B, char C)
{
    if(n==1)
       printf("move sheet %d,  from %c to %c",n,A,C);
}
皿が2つある場合:A->B,A->C,B->C
void hanoi(int n, char A, char B,char C)
{
    if(n==1)
        printf("move sheet %d,  from %c to %c",n,A,C);
    else(n==2)
    {
        printf("move sheet %d,  from %c to %c",n,A,B);
        printf("move sheet %d,  from %c to %c",n,A,C);
        printf("move sheet %d,  from %c to %c",n,B,C);
    }
}
2つ以上の皿の場合、一番下の皿を1と見なすことができ、上の皿はn-1であり、基本的な流れは上記の通りである.
void hanoi(int n, char A, char B,char C)
{
    if(n==1)
        printf("move sheet %d,  from %c to %c",n,A,C);
    else
    {
        //printf("move sheet %d,  from %c to %c",n,A,B);
        hanoi(n-1, A,  C, B);
        printf("move sheet %d,  from %c to %c",n,A,C);
        //printf("move sheet %d,  from %c to %c",n,B,C);
        hanoi(n-1, B,  A, C);
    }
}
もしn=64なら、皆さんはコンピューターで走ってもいいですが、しばらくは走りきれないと思います.人が運んでくれれば、世界の終わりはありません....