Tháp lặp của Hà Nội này hoạt động như thế nào? C

Question

thể trùng lặp:
How does this work? Weird Towers of Hanoi Solution

Trong khi lướt Google, tôi tìm thấy giải pháp thú vị này đến Tháp Hà Nội mà thậm chí không sử dụng ngăn xếp như cấu trúc dữ liệu.

Ai đó có thể giải thích ngắn gọn về tôi, nó thực sự đang làm gì?

Giải pháp này có thực sự chấp nhận được không?

Mã

#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; 
} 

Cập nhật: các mã hóa cứng số 3 làm ở đây là gì?

Answer 1

Có thể dễ dàng nhìn thấy trong mã giả:

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 dịch đi n BITS là về cơ bản 2 với sức mạnh của n, 16 trong trường hợp của 4 đĩa.

If you walk through this sequence manually, you should see the progression of movement of the disks. http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

Answer 2

Đây là một trong những giải pháp nhị phân cho Tháp Hà Nội, có giải thích chi tiết về thuật toán này trên Wikipedia - đọc the "Binary solution" paragraph.