СВЕТ: СПАСИБО
01-12-2023
Читать статью
Калужский Александр: Задача про Цаплю: https://www.youtube.co..
24-11-2023
Сергей: спасибо большое
Сегодня разберём известную задачу Ханойская башня. Подобные задачи способствуют повышению уровня грамотности при написании программ, развивают алгоритмические способности и поднимают общий тонус для участия в экзаменах и олимпиадах по информатике.
Задача: Есть три стержня. На одном из которых нанизаны диски. Диски располагаются в виде пирамидки(ханойской башни): в самом низу лежит самый большой диск, затем идёт чуть поменьше диск, затем ещё меньше диск и т. д. Необходимо переместить диски с одного стержня на другой. Можно использовать все три стержня, но при условии: перекладывать можно только по одному диску за ход, складывать диски можно только меньший на больший.
Нам необходимо составить алгоритм для решения данного задания при любом количестве n. Для начала докажем, что задача вообще имеет решение при любом количестве n. Для этого будем использовать метод математической индукции.
В основе метода математической индукции лежит принцип математической индукции.
Он заключается в следующем: некоторое утверждение справедливо для всякого натурального n, если оно справедливо для n = 1 и из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k+1.
То есть, доказательство по методу математической индукции проводится в три этапа:
Используем метод математической индукции:
Ещё раз о методе математической индукции. Мы доказали, что для одного диска всё работает отлично. Также мы доказали, что если для n дисков задача решается, то для n+1 тоже будет решаться. Но если вместо n подставить нашу 1, то уже для 2 тоже будет выполняться. В свою очередь 2 "тянет" за собой 3 и т.д. Таким образом, у нас задача будет решаться для любого натурального числа.
Сами наши рассуждения по поводу метода математической индукции нам подсказывают, что здесь можно воспользоваться рекурсией
Пишем программу:
Программу напишем на C#, т.к. этот язык в большинстве случаев принимается на олимпиадах по информатике. n-Количество дисков, i-номер стержня-источника, p-номер стержня-приёмника, v-вспомогательный стержень. Переменные соответственно i,p,v должны принимать значения от 1 до 3. Переменная n>0. Защита от "дурака" в данной функции не реализована. Если понадобится - реализуете сами. Также, здесь приведена сама функция Hanoy, которая и реализует всю работу. Остальные строки кода консольного приложения C# здесь опущены.
public static bool Hanoy(int n, byte i, byte p, byte v) { if (n>0) { // Перекладываем сначала стопку из n-1 элементов на вспомогательный стержень. // А стержень приёмник играет пока роль вспомогательного. Hanoy(n - 1, i, v, p); // Перекладываем самый большой диск из стержня-источника на стержень-приёмник. Console.WriteLine(i + "->" + p); // Перекладываем стопку из n-1 элементов уже на стержень-приёмник. // А стержень-источник играет пока роль вспомогательного. Hanoy(n - 1, v, p, i); } return true; }
Как мы с вами разобрались, когда размышляли о математической индукции, чтобы переложить n дисков на стержень-приёмник, нам необходимо сначала переложить n-1 дисков на вспомогательный стержень, затем переложить самое большое кольцо на стрежень-приёмник, и повторить действия для n-1 дисков, переместив их из вспомогательного стержня, уже на стержень назначения. Таким образом, наша Ханойская башня из n элементов переместится со стержня источника на стержень-приёмник. Обратите внимание, что функция Hanoy вызывает сама себя, т.е. функцию Hanoy (Это и есть рекурсия!). Это происходит из-за того, что для перемещения Ханойской башни из n элементов, ей необходимо воспользоваться результатом своей же работы для n-1 элементов.
Запускаем нашу функцию Hanoy из функции Main (Для языка C# в консольном приложении) для 3х дисков:
static void Main(string[] args) { Hanoy(3, 1, 2, 3); Console.ReadKey(); }
Время работы пропорционально 2n − 1, где n-количество дисков.
На сегодня всё. Надеюсь, Вам понравилась задача Ханойская башня. Давайте изучать классику Информатики вместе! Если у Вас что-то не получилось, пишите в комментариях. До новых встреч!