7

重複の可能性:
これはどのように機能しますか? ハノイ ソリューションの奇妙な塔

Google をサーフィンしているときに、スタックをデータ構造としても使用しないハノイの塔に対するこの興味深いソリューションを見つけました。

誰かが私を簡単に説明できますか、それは実際に何をしているのですか?

この解決策は本当に受け入れられますか?

コード

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int n, x;
   printf("How many disks?\n");
   scanf("%d", &n);
   printf("\n");
   for (x=1; x < (1 << n); x++)
      printf("move from tower %i to tower %i.\n",
         (x&x-1)%3, ((x|x-1)+1)%3);
return 0;
}

更新: ここでハードコードされた番号 3 は何をしているのですか?

4

2 に答える 2

11

PSEUDOCODEで見やすいかもしれません：

GET NUMBER OF DISKS AS n
WHILE x BETWEEN 1 INCLUSIVE AND 1 LEFT-SHIFTED BY n BITS
    SUBTRACT 1 FROM n, DIVIDE BY 3 AND TAKE THE REMAINDER AS A
    OR x WITH x-1, ADD 1 TO THAT, DIVIDE BY 3 AND TAKE THE REMAINDER AS B
    PRINT "MOVE FROM TOWER " A " TO TOWER " B
    ADD 1 TO x

1 LEFT SHIFTED BY n BITS は基本的に 2 の n 乗、4 ディスクの場合は 16 です。

このシーケンスを手動で実行すると、ディスクの移動の進行が表示されます。http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

于 2010-05-20T02:44:59.433 に答える
6

これは、ハノイの塔のバイナリ ソリューションの 1 つです。ウィキペディアには、このアルゴリズムの詳細な説明があります。 「バイナリ ソリューション」の段落を参照してください。

于 2010-05-20T02:42:36.600 に答える