Башни Ханоя: Нахождение n-й конфигурации

Question

Я хочу найти n-ю конфигурацию в решении проблемы Ханойских башен, учитывая количество дисков и номер хода.

Следующий код находит n-й ход с использованием хвостовой рекурсии:

  public static String N_th_Move(int k_discs, int move){
        return HanoiRec(k_discs, move, "A", "B", "C");
    }

    private static String HanoiRec(int k_discs, int move, String rod_a, String rod_b, String rod_c) {
        int max_n_moves = (int) (Math.pow(2, k_discs) - 1); 
        int bound =(int) Math.pow(2, k_discs - 1);
        if(move > max_n_moves){
            return "Not valid";
        } else if(move == bound ){
            return rod_a + " -> " + rod_b;
        } else if(move < bound){
            return HanoiRec(k_discs-1, move , rod_a, rod_c, rod_b);
        } else {
            return HanoiRec(k_discs-1, move - bound, rod_c, rod_b, rod_a);
        }
    }

Как найти n-ю конфигурацию, используя тот же подход?

например:.

N_th_configuation(3, 4) #{rod_a: 0, rod_b: 1, rod_c: 2}

ДОБАВЛЕНО: двоичное дерево для 3 дисков (в соответствии с приведенным выше кодом):

                                (0  1  2)
                               /         \
                        (1 1 1)           (0 2 1)
                       /       \         /       \
                    (2 1 0)  (1 0 2)  (1 1 1)  (0 3 0)

Где первое число - это число дисков на rod_a, второе на rod_b и третье на rod_c. Нижний левый лист - это конфигурация после первого хода, а нижний правый - это конфигурация после последнего хода. Я не выясняю связь между всеми конфигурациями.

Answer 1

Каноническим решением для ToH является чередование двух типов ходов:

1. Перемещение наименьшего диска к следующему стержню (с намоткой назад к исходному стержню)
2. Созданиеодин допустимый ход, который не включает самый маленький диск.

wlog (без потери общности), давайте предположим, что самый маленький диск всегда перемещается к следующему стержню с большим номером (помечены 0, 1, 2).

Одним из результатов этого алгоритма является то, что диски с нечетными номерами перемещаются выше;Диски с четными номерами перемещаются ниже.

Другим результатом является то, что вы можете независимо определить диск для любого заданного номера хода: это бит с самым низким значением 1 в двоичном представлении этого числа.Например, для задачи с 3 дисками:

Move  binary disc
  1     001    1
  2     010    2
  3     011    1
  4     100    3
  5     101    1
  6     110    2
  7     111    1

Чтобы найти позицию, соответствующую любому ходу N:

1. Разделите двоичные файлы на отдельные цифры.
2. Маска всех битов - самый правый 1 бит в каждом.
3. Добавьте столбцы.
4. Отверните столбцы с четными номерами (чтобы показать, что диски перемещаются в противоположном направлении.
5. Уменьшите общий модуль 3.

Результатом является списокстолбцов, на которые опирается каждый диск.