Головоломка ханойская башня эксель

Задача ханойская башня

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

Задача : Есть три стержня. На одном из которых нанизаны диски. Диски располагаются в виде пирамидки(ханойской башни): в самом низу лежит самый большой диск, затем идёт чуть поменьше диск, затем ещё меньше диск и т. д. Необходимо переместить диски с одного стержня на другой. Можно использовать все три стержня, но при условии: перекладывать можно только по одному диску за ход, складывать диски можно только меньший на больший.

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

В основе метода математической индукции лежит принцип математической индукции.

Он заключается в следующем: некоторое утверждение справедливо для всякого натурального n, если оно справедливо для n = 1 и из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.

То есть, доказательство по методу математической индукции проводится в три этапа:

• во-первых, проверятся справедливость утверждения для любого натурального числа n (обычно проверку делают для n = 1);
• во-вторых, предполагается справедливость утверждения при любом натуральном n=k;
• в-третьих, доказывается справедливость утверждения для числа n=k+1, отталкиваясь от предположения второго пункта.

Используем метод математической индукции:

• Наша задача точно решается для одного диска. Это очевидно. Просто берём и перемещаем диск с одного стержня на другой.
• Пусть мы умеем перекладывать n дисков. Докажем, что тогда и n+1 мы также можем переложить.
• Пускай нам надо переложить n+1 дисков на второй стержень. Т.к. мы умеем перекладывать n дисков, то мы эту стопку переложим на третий стержень. Затем, положив самый большой диск на второй стержень, мы воспользуемся тем, что умеем перекладывать стопку из n элементов и переложим эту стопку с третьего стержня на второй. Таким образом, мы доказали, что задача решается для любого числа дисков.

Ещё раз о методе математической индукции. Мы доказали, что для одного диска всё работает отлично. Также мы доказали, что если для n дисков задача решается, то для n+1 тоже будет решаться. Но если вместо n подставить нашу 1, то уже для 2 тоже будет выполняться. В свою очередь 2 «тянет» за собой 3 и т.д. Таким образом, у нас задача будет решаться для любого натурального числа.

Сами наши рассуждения по поводу метода математической индукции нам подсказывают, что здесь можно воспользоваться рекурсией

Программу напишем на C#, т.к. этот язык в большинстве случаев принимается на олимпиадах по информатике. n-Количество дисков, i-номер стержня-источника, p-номер стержня-приёмника, v-вспомогательный стержень. Переменные соответственно i,p,v должны принимать значения от 1 до 3. Переменная n>0. Защита от «дурака» в данной функции не реализована. Если понадобится — реализуете сами. Также, здесь приведена сама функция Hanoy, которая и реализует всю работу. Остальные строки кода консольного приложения C# здесь опущены.

Как мы с вами разобрались, когда размышляли о математической индукции, чтобы переложить n дисков на стержень-приёмник, нам необходимо сначала переложить n-1 дисков на вспомогательный стержень, затем переложить самое большое кольцо на стрежень-приёмник, и повторить действия для n-1 дисков, переместив их из вспомогательного стержня, уже на стержень назначения. Таким образом, наша Ханойская башня из n элементов переместится со стержня источника на стержень-приёмник. Обратите внимание, что функция Hanoy вызывает сама себя, т.е. функцию Hanoy (Это и есть рекурсия!). Это происходит из-за того, что для перемещения Ханойской башни из n элементов, ей необходимо воспользоваться результатом своей же работы для n-1 элементов.

Запускаем нашу функцию Hanoy из функции Main (Для языка C# в консольном приложении) для 3х дисков:

Время работы пропорционально 2 n − 1, где n-количество дисков.

На сегодня всё. Надеюсь, Вам понравилась задача Ханойская башня. Давайте изучать классику Информатики вместе! Если у Вас что-то не получилось, пишите в комментариях. До новых встреч!

Источник

Информатика задача программирование

В основу эффективного решения головоломки «Ханойская башня» положен алгоритм, суть которого сводится к следующему: для перемещения башни, состоящей из n колец, с первого стержня на третий мы должны решить чуть более простую задачу переместить на второй стержень башню, состоящую из n-1 кольца. После этого нижний диск с первого стержня перемещается на третий и повторно осуществляется перемещение башни из n-1 кольца, но уже со второго диска на третий. Таким образом, число ходов, необходимых для перемещения башни из n колец, равно удвоенному числу ходов, необходимых для перемещения башни из n-1 кольца, и ещё одному ходу. Используйте эту закономерность для вычисления числа ходов, необходимых для перемещения башни из 64 колец. Вычислите, сколько времени займёт такое перемещение, если считать, что на один ход требуется 1 секунда.

НУЖНО СДЕЛАТЬ В EXCEL

Я вроде нашёл формулу 2 в степени n минус 1, но эта формула нужна для перемещения на третий стержень, а в задаче вроде нужно переместиться на 2

Хелп, я правда не знаю, что делать.

«. решить чуть более простую задачу переместить на второй стержень. «
третий стержкнь от второго отличается только расположением.
Измените первый ход и конечный результат тоже изменится.

«. После этого НИЖНИЙ диск . «
Хочется верить что это опечатка

В смысле? От того, прыгнем ли мы первым ходом на 2 или на 3 стержень, конечный результат — пирамида на 3 стержне, — ну никак не поменяется.

И, таки, да — НИЖНИЙ. Именно так эта головоломка и складывается.

«Используйте эту закономерность для вычисления числа ходов, необходимых для перемещения башни из 64 колец. Вычислите, сколько времени займёт такое перемещение, если считать, что на один ход требуется 1 секунда.»

Ну? И где здесь «нужно найти перемещение на второй» ? ГДЕ ?! С закрытыми глазами условие читаем ?
Ты ж уже формулу нашёл, так в чём проблема ?! Забивай в любую ячейку =СТЕПЕНЬ (2;64)-1 и получай свой результат. Тоже мне, блин, проблема на пустом месте.

Источник

Сортировка «Ханойская башня»

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.)

Данный пост посвящается памяти истинного гуру программирования Андрея Mrrl Астрелина, который когда-то мне просто и доходчиво объяснил этот алгоритм. Псевдокод ниже по тексту — его авторства.

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

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

Если позволить себе только эти две вольности, то начальные условия головоломки можно интерпретировать как массив (диски — это числа), а задача сводится к тому, что данный массив требуется отсортировать.

Остальные условия мы (почти) не меняем:

• У нас два вспомогательных шеста (пара пустых массивов).
• Можем переносить диски по одному.
• Класть только меньшие на бо́льшие (раз мы разрешили одинаковые размеры дисков, то также можно класть перемещаемый диск сверху на другие такого же размера).
• Имеем право сравнивать переносимый диск только с самым верхними дисками (то бишь, все 3 массива являются стеками).

Наша задача: взять классический рекурсивный алгоритм головоломки…

… и превратить его в сортировку!

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

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

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

Что касается разрешения повторов, то это вообще не имеет никакого значения. Потому что подряд идущие одинаковые диски мы просто перемещаем как один диск.

Алгоритм

Назовем столбики A, B, C (A в начале непустой).

А->С() — переложить один диск с А на С.
top(A), top(С) — размер верхнего диска А или С. Если столбик пуст, то этот размер = MaxInt.
В->С(К) — переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхние диски А и С не меньше К).
swap() — переставить столбики В и С (или переименовать их — нам ведь все равно, где окажутся диски).
while(A) — цикл пока А не пуст.

Тогда работает такой алгоритм:

Сложность

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

Насчёт памяти можно сказать, что если используется рекурсия, то и затраты будут соответствующие.

Реализация

Свой вариант на Python пока не написал (сделаю это позже). Однако ниже в разделе «Ссылки» накидал несколько ссылок, по которым можно посмотреть имплементации на различных языках. Особенно интересен вариант на Джаве. Автор не стал брать за основу общеизвестный рекурсивный способ для решения головоломки, а построил кратчайшее дерево путей. Предположительно, это является самым эффективным решением, если писать сортировку в стиле «Ханойской башни».

Характеристики алгоритма

Название	Сортировка «Ханойская башня», Tower of Hanoi sort
Автор идеи	Эдуард Люка́
Класс	Сортировки вставками
Сравнения	Есть
Временна́я сложность	лучшая	?
	средняя	?
	худшая	O(2 n )

Ссылки

Tower of Hanoi / Ханойская башня

Статьи серии:

• Excel-приложение AlgoLab.xlsm
• Сортировки обменами
• Сортировки вставками
  • Сортировка библиотекаря
  • Пасьянсная сортировка
  • Сортировка «Ханойская башня»
  • Сортировка выворачиванием
  • Сортировка таблицей Юнга
• Сортировки выбором
• Сортировки слиянием
• Сортировки распределением
• Гибридные сортировки

В приложении AlgoLab данная сортировка теперь доступна. Хотя она относится к классу сортировок вставками, по причине экстравагантности алгоритма она помещена в раздел «Прочие сортировки». Ещё там есть ограничение — числа в сортируемом массиве могут быть только от 1 до 5 (связано с непростой прорисовкой дисков). Другие числа всё равно будут заменены на эти.

Также есть ограничение на размер массива — не более 20-ти элементов. Сделано это сугубо в Ваших же интересах — если возьмёте слишком большой массив, то, может так статься, что сортировать его придётся до глубокой старости.

Статья написана при поддержке компании EDISON Software, которая профессионально разрабатывает умное городское освещение и поддерживает сайты на питоне

Источник

Русские Блоги

Алгоритм (9) Ханойской башни и его реализация кода

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

оглавление

1. Что такое Ханойская башня

Ханойская Башня: проблема Ханойской Башни (также известной как Ханойская Башня) — образовательная игрушка, происходящая из древней легенды в Индии. Когда Брахма сотворил мир, он создал три алмазных столба, на одном из которых были сложены 64 золотых диска по порядку снизу вверх. Брахма приказал Брамину переместить диск на другой столбец в порядке размера снизу. И оговаривают,Невозможно увеличить диск на маленьком диске, только один диск может быть перемещен между тремя опорами одновременно。

2. Перемещение процесса Ханойской башни

Ханойская башня Анимация: демонстрирует процесс движения диска

(эта анимация поступает из сети)

Ниже показан процесс перемещения каждой пластины в трех случаях (n представляет количество дисков):

В-третьих, идея алгоритма Ханоты

Когда n равно 1, переместите диск из A в C напрямую;

Переместите (n-1) пластины выше столба A от A до B;

Переместите n-ую пластину над колонной A от A до C;

Переместите (n-1) пластин в столбце B первого шага из B в C

В реализации алгоритма мы используем идею рекурсии. Для имитации процесса движения и общего количества движений.

1. Пример кода

Результаты выполнения кода:

2. Расширенные проблемы

Если для перемещения диска требуется 1 секунда, сколько времени займет ожидание восстановления всех 64 дисков?

Когда используется диск, мощность 2 уменьшается на 1.
Когда два диска, мощность 2 уменьшается на 1
При наличии 3 дисков мощность 2 уменьшается на 1
При наличии 4 дисков мощность 2 уменьшается на 1
…
Когда n дисков, мощность 2 уменьшается на 1

Когда n = 64, это (от 2 до 64 степени минус 1) раз.

Результаты выполнения кода:

Для перемещения всех дисков потребуется около 584,9 миллиардов лет. Какое ужасное число!

Источник