MrShoor Nov 4 2013 at 21:30

Ханойская башня на пальцах

6 min

245K

Algorithms *

+56

Comments 29

Kalobok Nov 4 2013 at 22:57

Самое простое решение — готовая последовательность ходов: 1-2, 1-3, 2-3 для четного количества колец или 1-3, 1-2, 2-3 для нечетного. Числа — номера пирамидок, с которых или на которые надо переложить кольцо. Например, 1-2 означает либо с 1 на 2, либо с 2 на 1 — направление определяется размерами верхних колец. Повторяем нужную последовательность пока задача не окажется решена. Это решение не дает понимания сути процесса, зато очень легко применяется на практике без какой-либо вычислительной техники — достаточно уметь считать до трех. :)

MrShoor Nov 4 2013 at 23:02

Да, это решение описывается в русской википедии (единственное, другие решения только в английской вики). Я специально не стал на нем останавливаться, потому что понимания сути никакого.

Kalobok Nov 4 2013 at 23:06

В вики есть? Интересно. Не знал. Я его нашел случайно еще в школе. А теперь очень удобно издеваться над людьми в пьяных компаниях. :)

Nagg Nov 4 2013 at 23:16

Сразу вспоминается фильм «планета обезьян».
PS: ханойские башни на флеше без смс: igroflot.ru/logic/flash_game_206/

roman_pro Nov 5 2013 at 08:55

Мне больше по душе дзен-алгоритм (вроде так называли в учебнике «Алгоритмика»): «нетронутые поля меняются по кругу»

andyudol Nov 5 2013 at 14:29

Причём в обратном направлении.

dezconnect Nov 5 2013 at 09:00

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

Вы издеваетесь? Задача давалась нам классе в 3 на уроках информатики, причем для самостоятельного решения.

Варианты решений конечно хорошо описали, но те программистов кто не понимает такую элементарщину надо реально гнать из профессии.

-4

MAXH0 Nov 5 2013 at 09:34

Спешу Вас разочаровать — по современной программе ни в 3 классе, ни в 9 эта задача не предусмотрена. И я не знаю как в 3, но 9 классники ее самостоятельно не решают! Разве что 1-2 на группу из 10 чел. отобранных в группу программирования на доп занятия!
Хотя совершенно с вами согласен — кто не может решить — не программист, а кодер!

dezconnect Nov 5 2013 at 11:11

Я просто оставлю это здесь:

http://festival.1september.ru/articles/310523/

Шел тот самый 1995 год, у нас была похожая структура урока(Правда там был пакет роботландия(ну или что то сильно похожее, не помню уже названия точного, но «игры» те же) который еще на УКНЦ работал), всем желающим было предложено самостоятельно разработать алгоритм для решения Ханоских башен со сложностью до 8 колец. Как ни странно, но не справилось с задачей буквально пара тройка человек, из 27. По другим классам из параллели аналогичная ситуация. Вполне себе обычный гимназический класс был.

MAXH0 Nov 5 2013 at 13:38

Проект «Роботландия» хорош (насколько может быть хорош любой проект в современном копирастическом мире учебного книгоиздательства)…
Но к типовым программам он почти не имеет отношения. И к практике в школах — тем более.

dezconnect Nov 5 2013 at 20:05

Еще скажите что к обучению алгоритмизации он не имеет никакого отношения? И насколько я могу судить, многие учебники информатики содержат курс рассчитаный как раз на этот пакет.

Не имеет отношению к реальному программированию? Не имеет. Но это не позволяет на псевдокоде обучаться алогоритмам.

Dementor Nov 6 2013 at 14:03

программистов кто не понимает такую элементарщину надо реально гнать из профессии

Программистов практически не останется :(

Поделюсь печальным наблюдением на эту тему. Мы выбрали эту задачу на собеседование программистов C++ и Java в прошлом году. При этом разрешили пользоваться интернетом. Вот только ни википедия, ни разжованный вариант на стековерфлоу почему-то людям не помогали и за отведенные на решение часы хороший результат был в лучшем случае у одного из двадцати. Большинство не то что бы закодили, они даже сам алгоритм не смогли понять (ни итеративную, ни рекурсивную версии).

MrShoor Nov 6 2013 at 14:49

Вот вот. Это и стало причиной написания статьи. Сначала я узнал, что оказывается не все умеют решать Ханойскую башню, а когда полез смотреть в интернет, понял что понятного материала на эту тему нет. Я постарался объяснить понятнее, чем на вики и стековерфлоу.
Глядишь — теперь больше народу пройдет собеседование у вас :D

Triang3l Nov 5 2013 at 09:08

memcpy(tower[1], tower[0], sizeof(**tower));
memset(tower[0], 0, sizeof(**tower));

MrShoor Nov 5 2013 at 09:24

Что это значит — я прекрасно знаю, но к чему бы это?

blackstrip Nov 5 2013 at 10:36

Алогитмичиская сложность — поправьте этот подзаголовок в статье

MrShoor Nov 5 2013 at 10:39

Поправил, спасибо. Проверку орфографии не использую просто, вот как-то и пропустил.

Sergey40a Nov 5 2013 at 14:16

Моим первым приложением, использующем рекурсию, было не вычисление факториала, а именно Ханойская башня. Спасибо за статью.

Dima_Sharihin Nov 5 2013 at 15:19

Эту бы статью в годы моего детства, когда я пытался пройти эту локацию

P.S. для тех, кто не знает — это «инвертированные Ханойские башни» из Kyrandia 2

MrShoor Nov 5 2013 at 15:45

Кстати Ханойские башни встречаются во многих играх, в особенности во всяких квестах.

freuser Nov 5 2013 at 19:17

Искал этот рассказ, а нашёл на элементах такую же задачу с усложнением в виде дополнительного правила.

tyomitch Nov 5 2013 at 19:23

Прочитав заголовок, подумал, что автор предлагает надеть диски разного размера на пальцы, и перенадевать с одного на другой.
В качестве развлечения в дороге, например.
Milfgard, ловите идею, пока горячая :-)

Milfgard Nov 5 2013 at 19:26

Поймал, спасибо. Только не знаю, что с ней пока делать. Диски на пальцах держать неудобно, потому что диски большие и крулые, а пальцы, увы, сходятся у ладони. Я вот вырезал прототип трёх из бумаги, проверил. Да и вообще, тренд такой, что в дорогу берут либо компанейские настолки у нас, либо планшеты у Яблока и Гугла.

Nashev Nov 5 2013 at 19:46

Ну, можно не диски, а полоски разной длины с дырками у одного из концов… Типа ваших скидочных карт
Не знаю, правда, будет ли кто заморачиваться с покупкой…

Nashev Nov 5 2013 at 19:47

ещё альтернативное применение у них получится — закладки для книг

Milfgard Nov 5 2013 at 19:50

У нас для таких целей йо-йо и кубики Рубика берут. Одному в метро посидеть или в дороге поиграть. Особо циничное издевательство — подарить человеку кубик Рубика 2х2, который он сначала считает предельно простым, а потом, где-то через час, начинает сомневаться в собственном интеллекте. Были дорожные «НЛО» Рубика, но пошли плохо. Ещё хорошо лабиринты идут, в которых надо шарик прогнать через полосу препятствий. А вот любые головоломки кроме кубиков — не очень. Я же говорю, планшеты отлично заменяют.

tyomitch Nov 5 2013 at 19:46

Совсем необязательно дискам быть круглыми. Могут быть узкими и вытянутыми.

А если такая игра в «рабочем положении» будет напоминать кастет, тогда в неё можно будет играть и по дороге от электрички до дома тёмным вечером :-)

neomoto Nov 5 2013 at 20:45

когда-то сталкивался с задачей «постройки» башни с произвольным количеством дисков и осей и известной конечной осью(на которую собирать). К стыду своему, решить не смог. С интересом бы почитал об алгоритме для такого случая.

MrShoor Nov 5 2013 at 20:49

Для произвольного кол-ва дисков и осей задача перемещения за минимальное число ходов не решена. Только строить граф всех перемещений и делать поиск пути в графе.