Как работает эта повторяющаяся Ханойская башня? С

Возможный дубликат:
Как Это работает? Странные решения Ханойских башен

Просматривая Google, я нашел это интересное решение для Tower Of Hanoi, которое даже не использует стек в качестве структуры данных.

Может ли кто-нибудь объяснить мне вкратце, что он на самом деле делает?

Это решение действительно приемлемо?

Код

#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?


c iteration towers-of-hanoi
person TCM    schedule 20.05.2010    source источник
comment
Он использует стандартные 3 стержня.   -  person Matthew Flaschen    schedule 20.05.2010
comment
Сообщает ли он о правильной последовательности ходов? Если да, то это работает, и нет никаких причин, по которым это не должно быть приемлемым. Тем не менее, вам нужно понять это, прежде чем предлагать это в качестве решения для вашего домашнего задания, иначе у вас будут проблемы, если вас попросят объяснить это, что вполне может быть, поскольку это так отличается от нормального.   -  person Jonathan Leffler    schedule 20.05.2010
comment
Это не моя домашняя работа. Я просто случайно нашел этот алгоритм и подумал спросить, как он на самом деле работает.   -  person TCM    schedule 20.05.2010
comment
Точный дубликат: stackoverflow.com/questions/2209860/   -  person ergosys    schedule 20.05.2010

Ответы (2)


arrow_upward
11
arrow_downward

Может быть проще увидеть в ПСЕВДОКОДЕ:

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 СДВИГ ВЛЕВО НА n БИТ в основном равен 2 в степени n, 16 в случае 4 дисков.

http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

person Robert Harvey    schedule 20.05.2010
comment
Спасибо, Харви, этот псевдокод действительно легко понять :). Отличный ответ! - person TCM; 20.05.2010
comment
Мм, МЕЖДУ 1 И n совсем не то же самое, что для (x=1; x ‹ (1 ‹‹ n); x++) - person David Gelhar; 20.05.2010
comment
Просто примечание: ссылка в конце битая. - person Ziezi; 04.09.2017

arrow_upward
6
arrow_downward

Это одно из бинарных решений Ханойской башни, подробное объяснение этого алгоритма есть в Википедии — читайте параграф "Двоичное решение".

person ZelluX    schedule 20.05.2010