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

[Kalobok]

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

[MrShoor]

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

[Kalobok]

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

[Nagg]

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

[roman_pro]

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

[andyudol]

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

[dezconnect]

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

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

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

[MAXH0]

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

[dezconnect]

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

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

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

[MAXH0]

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

[dezconnect]

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

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

[Dementor]

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

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

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

[MrShoor]

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

[Triang3l]

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

[MrShoor]

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

[blackstrip]

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

[MrShoor]

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

[Sergey40a]

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

[Dima_Sharihin]

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



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

[MrShoor]

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

[freuser]

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

[tyomitch]

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

[Milfgard]

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

[Nashev]

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

[Nashev]

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

[Milfgard]

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

[tyomitch]

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

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

[neomoto]

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

[MrShoor]

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