«Ханойские Башни»

[Stauffenger]

Множество попарно различных по величине колец
случайным образом рассадили
по трём (других нет!) стержням,
но так, что
(*) нигде большее кольцо не лежит на меньшем.

Как, пересаживая со стержня на стержень по кольцу,
собрать все их на заранее указанный стержень,
но так, чтобы
никогда не было нарушено условие (*) ?

@темы: Поп-математика

Comments

[Wizzard Rick]

Элементарно, Ватсон.
Это способен сделать ребёнок трёх лет.

[Stauffenger]

Это интригует!
А поскольку лет уже поболе, то интересно бы увидеть здесь, как ..

[Wizzard Rick]

Элементарно - попарный перенос. Алгоритмизация десу.
Просто чем больше дисков - тем больше тупой бесполезной работы с повторениями. Вкратце:

***
1 2 3
4 5 6
9 8 7


X 1 X
X 2 3
4 5 6
9 8 7

***
X 1 X
3 2 X
4 5 6
9 8 7

***
3 2 1
4 5 6
9 8 7

***
2 X X
3 X 1
4 5 6
9 8 7

***
1 X X
2 X X
3 X X
4 5 6
9 8 7

***
1 X X
2 X X
3 X 5
4 X 6
9 8 7

***

2 X X
3 X 5
4 1 6
9 8 7

***

X X 2
3 X 5
4 1 6
9 8 7

***
X X 1
X X 2
3 X 5
4 X 6
9 8 7

***
X X 1
X X 2
X X 5
4 3 6
9 8 7

***
X X 2
1 X 5
4 3 6
9 8 7

***
1 2 5
4 3 6
9 8 7

***
X 1 X
X 2 5
4 3 6
9 8 7

***

X 1 4
X 2 5
X 3 6
9 8 7

***
X X 1
X X 4
X 2 5
X 3 6
9 8 7

***

X X 1
X X 4
X X 5
2 3 6
9 8 7


***

X X 4
1 X 5
2 3 6
9 8 7

***
X X 3
X X 4
1 X 5
2 X 6
9 8 7


***
X X 3
X X 4
X X 5
2 1 6
9 8 7

***
X X 2
X X 3
X X 4
X X 5
X 1 6
9 8 7

***
X X 1
X X 2
X X 3
X X 4
X X 5
X X 6
9 8 7

***
X X 1
X X 2
X X 3
X X 4
X X 5
8 X 6
9 X 7


Ну а дальше - перенести с третьего стержня на первый проблем никаких.

Ред: не люблю хтмл...

[Stauffenger]

Энцефалограмма процесса порождения сего, однако, симпатичнее!
И, похоже, не менее понятна.
Да и места поменьше б заняла.
А простым человечьим языком неужто никак?
По жизни увы, автоматом подрабатывать не довелось ..

[Фабий]

Алгоритм прост: следует последовательно повторять два шага:
1. Переместить наименьшее кольцо на следующий по порядку стержень (если она на третьем — то переход на первый).
2. Переложить ненаименьшее кольцо на другой стержень.

Для трёх — это всё)

[Stauffenger]

Благодарю за человеческий язык!
Опепация пункта 1. вполне понятна и выполняется без труда.
А вот пункт 2. таким совершенством уже не страдает, поскольку не ясно какое ненаименьшее.
Но даже если на это закрыть глаза,
всёравно остаётся куда более серьёзная закавыка, а именно:
как убедить в том, что эти инструкции всегда будут приводить к желаемому результату?
Честного слова тут, однако, маловато будет ..

[Фабий]

Stauffenger,
пункт.2 - там вариантов немного. Наименьшее отпадает, а из осташихся двух только одно на другое положить возможно ,не нарушая условий.
Насчёт док-ва — подумаю. Просто, всегда работало — эмпирически подтверждено)

[Wizzard Rick]

А простым человечьим языком неужто никак?

Запарюсь объяснять.
Проще наглядно.

Но принцип сам понятен - для освобождения кольца на стержне 1 чтобы положить на стержень 2 мы последовательно перекладываем верхние диски на стержень 3. Как показано на рисунке.

[Stauffenger]

Wizzard Rick:
Как показано на рисунке.

Извини, но это не рисунок, а плохо пригодный для человеческого восприятия Log некоторого автомата.

Wizzard Rick:
для освобождения кольца на стержне 1 чтобы положить на стержень 2, .. перекладываем верхние диски на стержень 3.

Вот это уже, по крайней мере, приятнее читать!
Более того, тут уже просматривается тень некоторой решающей стратегии.
Но только тень, ибо
не понятно как это связано с конечной целью, не говоря уже об убеждении в достижимости её.
Да и чёткости в операциях Фабия, однако, поболее будет ..

[Wizzard Rick]

наверху - алгоритм. Цифры 1-9 - размер диска. Х - просто потому что это долбанный форум, в котором не работает многопробелие.

Как старый дзен-буддист, я тебе не дам решение, а покажу как это делается. Слова сформулируешь сам, ибо дзен, выраженный словами, таки не является истинным.

[Stauffenger]

Wizzard Rick: наверху - алгоритм ..

Извини, но вынужден повторить —
это плохо пригодный для человеческого восприятия Log некоторого автомата,
отработавшего из конкретного начального состояния.
В понятие Алгоритма, скажем, Тьюринг, Дейкстра, Ершов, Вирт, Кнут ..,
вкладывают нечто совсем иное.

Wizzard Rick: Как старый дзен-буддист ..

Полагаю, к такому случаю Бритва Оккама хороша.

Wizzard Rick: я тебе не дам решение, а покажу как это делается ..

Хорошо, что мой вопрос не о таинстве самовоспроизведения!

[Wizzard Rick]

Ну на хумансов мне, в принципе, пофиг. Не воспринимает - да и фиг с ним, их всё равно около 7 миллиардов.

[Stauffenger]

Wizzard Rick:
Ну на хумансов мне .. пофиг.
Не воспринимает - да и фиг с ним, их всё равно около 7 миллиардов.

Вот и осиротели ..

[Stauffenger]

От цзен-балды допустим,
как-то удалось убедить несчастный «хуманс» в том,
что чёткие инструкции, кои предложил Фабий (или более туманные — Wizzard Rick),
всегда позволят собрать все кольца на один стержень.
Но тут опять, мать её, закавыка:
Откуда следует, что это будет тот самый стержень,
который был указан изначально?

[Фабий]

Stauffenger, о ,а я и не заметил поправку насчёт заранее указанного...

[Фабий]

Кстати ,попарно различных — это что? В башнях Ханоя, вроде бы, все они разные по диаметру....

[Wizzard Rick]

Откуда следует, что это будет тот самый стержень,
который был указан изначально?

А это уже вопрос логистики. И преложить диски с одного стержня на другой - это уже другая задача, являющаяся оригинальными ханойскими башнями. Причём тоже примитивная.
просто при случайном разбросе дисков до приведения к нормали ответ неявен, потому что сначала надо самый большой диск уложить на указанный стержень.

[Wizzard Rick]

Да, маленький хинт оригинальных башен:
При перекладывании дисков со стержня 1 на стержень 3 с использованием промежуточного стержня 2 надо знать количество дисков.
Если их нечётное чисто - то перекладывание начинается с перемещения самого маленького диска на стержень 3.
Если их чётное число - на стержень 2.
Потому что самый первый ход сразу указывает на какой стержень будут падать чётные, а на какой - нечётные номера.

[Stauffenger]

Фабий:
Кстати, попарно различных — это что?

По определению, это означает, что какую пару ни возьми,
штуковины в ней различаются (в рассматриваемом случае, разумеется, диаметром)

Wizzard Rick: .. другая задача .. тоже примитивная.

Хорошо б до этой допереть .. примитивно как-нить ..

Wizzard Rick: ответ неявен ..
сначала надо самый большой диск уложить на указанный стержень..

Разумеется он должен там как-то оказаться, причём, в самом низу.
Но это не ответ, а лишь прекрасная ключевая идея!
Остаётся только снизойти до «хуманса»,
подавив в себе автоматные рецидивы..

[Wizzard Rick]

Хорошо б до этой допереть .. примитивно как-нить .

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

Впрочем в вышеуказанном варианте
X X 1
X X 2
X X 3
X X 4
X X 5
X X 6
9 8 7
- если стержень 1 - искомый, то задача решена. Просто диск 8 на стержень 1, затем диски 1-7 на него.
- если нам нужен стержень два - перекладываем диски 1-7 на стержень 1, затем перемещаем диск 8 на стержень 3, затем диски 1-7 - на стержень 3, затем диск 9 на стержень 2, и все диски на него.
- если нам нужен стержень три - перекладываем диски 1-7 на стержень 2, затем диск 9 на стержень 3 и все диски на него.

[Stauffenger]

Вот это уже много человечнее!
И вполне понятно как всё окажется на указанном стержне,
в допущении того, что найден убедительный способ
приведения системы в состояние, аналогичное указанному позицией выше.
Но допущение-то пока таковым и остаётся!
Более того, хотя о том в условии и не упоминается,
такое сведение к простому варианту, вообще говоря, не оптимально.