アルゴリズムのハノイの塔
1382 ワード
ハノイのタワープログラマーはよく知っているはずですが、背景を簡単に紹介します.
伝说の创世纪の时、Benaresに1基のポロ教塔があって、3本のダイヤモンドの棒で支えて、神は第1本の柱の上で64个の金盘を置いて、金盘は上から下まで顺次小さくて大きいです.神は僧侶に最初の柱から金盤を3本目の柱に移すように命令し、移動する過程で、ずっと大皿を下に保つ.皿が全数運ばれると、塔は自壊し、世界の終わりになる.
この問題の簡単な解決策は次のとおりです.
抽象的な3本の柱はA,B,Cで、簡単な皿から類推されます.
ディスクが1つしかない場合は、そのディスクをA->Cから
伝说の创世纪の时、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->Cvoid 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なら、皆さんはコンピューターで走ってもいいですが、しばらくは走りきれないと思います.人が運んでくれれば、世界の終わりはありません....