Как это работает? Странное Решение для Ханойских башен
Я был потерян в Интернете, когда я обнаружил это необычное, повторяющееся решение к Ханойским башням:
for (int x = 1; x < (1 << nDisks); x++)
{
FromPole = (x & x-1) % 3;
ToPole = ((x | x-1) + 1) % 3;
moveDisk(FromPole, ToPole);
}
Это сообщение также имеет подобный код Delphi в одном из ответов.
Однако ни за что в жизни я, может казаться, не нахожу хорошее объяснение того, почему это работает.
Кто-либо может помочь мне понять это?
2 ответа
Рекурсивное решение для башен Ханоя работает так, что если вы хотите переместить N дисков из точки A в точку C, вы сначала переместите N-1 из точки A в точку B, затем переместите нижнюю точку в точку C, а затем снова переместите N-1 диски из точки B в точку C. В сущности,
hanoi(from, to, spare, N):
hanoi(from, spare, to, N-1)
moveDisk(from, to)
hanoi(spare, to, from, N-1)
Ясно Ханой(_, _, _, 1) делает один ход, и ханой (_, _, _, k) принимает столько ходов, сколько 2 * ханой (_, _, _, k-1) + 1. Итак, длина раствора растет в последовательности 1, 3, 7, 15,... Это та же последовательность, что и (1 < < k) - 1, которая объясняет длину цикла в приведенном алгоритме.
Если вы посмотрите на сами решения, для N = 1 вы получите
FROM TO
; hanoi(0, 2, 1, 1)
0 2 movedisk
Для N = 2 вы получите
FROM TO
; hanoi(0, 2, 1, 2)
; hanoi(0, 1, 2, 1)
0 1 ; movedisk
0 2 ; movedisk
; hanoi(1, 2, 0, 1)
1 2 ; movedisk
и для N = 3 вы получите
FROM TO
; hanoi(0, 2, 1, 3)
; hanoi(0, 1, 2, 2)
; hanoi(0, 2, 1, 1)
0 2 ; movedisk
0 1 ; movedisk
; hanoi(2, 1, 0, 1)
2 1 ; movedisk
0 2 ; movedisk ***
; hanoi(1, 2, 0, 2)
; hanoi(1, 0, 2, 1)
1 0 ; movedisk
1 2 ; movedisk
; hanoi(0, 2, 1, 1)
0 2 ; movedisk
Из-за рекурсивного характера решения столбцы FROM и TO следуют рекурсивной логике: если взять среднюю запись в столбцах, части выше и ниже являются копиями друг друга, но с перестановкой чисел. Это очевидное следствие самого алгоритма, который не выполняет никаких арифметических действий в отношении пиковых чисел, а только переставляет их. В случае N = 4 средняя строка имеет значение x = 4 (помечена тремя звездами выше).
Теперь выражение (X & (X-1)) отключает наименьший установленный бит X, поэтому оно отображает, например, числа из формы 1 в 7 следующим образом:
1 -> 0
2 -> 0
3 -> 2
4 -> 0 (***)
5 -> 4 % 3 = 1
6 -> 4 % 3 = 1
7 -> 6 % 3 = 0
Хитрость заключается в том, что, поскольку средняя строка всегда имеет точную степень два и, таким образом, имеет ровно один бит, часть после средней строки равняется предшествующей ей части при добавлении среднего значения строки (4 в данном случае) к строкам (т.е. 4 = 0 + 4, 6 = 2 + 6). Выражение (X | (X-1)) + 1 устанавливает наименьший нулевой бит, который имеет единицы справа, и очищает эти единицы, так что он имеет такие же свойства, как ожидалось:
1 -> 2
2 -> 4 % 3 = 1
3 -> 4 % 3 = 1
4 -> 8 (***) % 3 = 2
5 -> 6 % 3 = 0
6 -> 8 % 3 = 2
7 -> 8 % 3 = 2
Что касается того, почему эти последовательности на самом деле производят правильные числа точек, давайте рассмотрим столбец FROM. Рекурсивное решение начинается с ханоя (0, 2, 1, N), поэтому в средней строке (2 * * (N-1)) должен быть movedisk (0, 2). Теперь по правилу рекурсии, в (2 * * (N-2)) необходимо иметь movedisk (0, 1) и в (2 * * (N-1)) + 2 * * (N-2) movedisk (1, 2). Это создает шаблон "0,0,1" для колышков из, который виден с различными перестановками в таблице выше (проверьте строки 2, 4 и 6 для 0,0,1 и строки 1, 2, 3 для 0,0,2 и строки 5, 6, 7 для 1,1,0, все перестановочные версии того же шаблона).
Теперь из всех функций, которые имеют это свойство, что они создают копии себя вокруг степеней двух, но со смещениями, авторы выбрали те, которые производят по модулю 3 правильных перестановок. Это не очень трудная задача, потому что есть только 6 возможных перестановок трех целых чисел 0.. 2 и перестановки прогрессируют в логическом порядке в алгоритме. (X | (X-1)) + 1 не обязательно глубоко связан с ханойской проблемой или ее не нужно быть; достаточно иметь свойство копирования и произвести правильные перестановки в правильном порядке.
Это не прямой ответ на вопрос, но это было слишком долго, чтобы добавлять комментарии.
Я всегда делал это, анализируя размер диска, который нужно переместить следующим. Если вы посмотрите на перемещенные диски, то увидите следующее:
1 disk : 1
2 disks : 1 2 1
3 disks : 1 2 1 3 1 2 1
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Нечетные размеры всегда перемещаются в направлении, противоположном четному, в том порядке, если привязки (0, 1, 2, повторение) или (2, 1, 0, повторение) ).
Если вы посмотрите на шаблон, кольцо для перемещения - это самый высокий набор битов xor количества ходов и количества ходов +1.