valemak
@valemak
Фрилансер

Есть ли реализация на любом языке программирования немного изменённой головоломки «Ханойская башня»?

Нужна реализация на любом языке программирования немного изменённой головоломки "Ханойская башня". Единственное отличие от классики - перед перемещениями на первом стержне находятся все диски, но они при этом не упорядочены по диаметру, могуть быть в произвольном порядке. То есть необязательно выполняется условие "изначально меньшие диски расположены выше чем большие".

Остальные правила те же: перемещая со стержня на стержень, нужно собрать диски на одном из них в упорядоченном состоянии. Большие при этом нельзя класть на меньшие, за 1 раз разрешается переносить только 1 диск, стержней всего 3.

К сожалению в рунете ничего не обнаружил. Пробовал гуглить по иностранным сайтам, но ввиду моего слабого английского эти поиски успехом не увенчались. Своими силами составить программу тоже не получается. Кто подскажет, где найти?
  • Вопрос задан
  • 3243 просмотра
Решения вопроса 2
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
Я не уверен в оптимальности решения, но как минимум оно даёт корректные результаты: https://gist.github.com/jcmvbkbc/8050585
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Назовем столбики A,B,C (A в начале непустой).
Введем операции:
А->С() - переложить один диск с А на С
top(A), top(C) - размер верхнего диска А или С. Если столбик пуст, то этот размер - MaxInt.
В->С(К) - переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхие диски А и С не меньше К)
swap() - переставить столбики В и С (или переименовать их- нам ведь все равно, где окажутся диски)
while(A) - цикл пока А не пуст.
Тогда работает такой алгоритм:
while(A){
  K=top(A);
  while(top(C) < K){
      B->C(top(C));
      swap();
  }
  A->C();
}
while(C){
  B->C(top(C));
  swap();
}
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы