Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Пример рекурс алгоритмаЗадача о Ханойских башнях.

Основные принципы перегрузки операций | Запреты на перегрузку операций | Базовые и производные классы. | Struct card | Int data; | Динамическое распределение памяти | Free(newPtr); | Очереди | Алгоритм как абстрактная машина | Сопоставление алгоритмических моделей |


Читайте также:
  1. III. Программа и тестовые примеры
  2. III. Программа и тестовые примеры
  3. III. Программа и тестовые примеры
  4. III. Программа и тестовые примеры
  5. IV. Примеры анализа рекламных сообщений
  6. IV.Индивидуальная работа с учащимися (пример)
  7. Аллах привел в качестве примера о верующих жену

Отображение более сложных рекурсивных связей в алгоритмах покажем на примере задачи о Ханойских башнях. Эта интересная задача была сформулирована в 1883 году математиком Э.Люка. Многие учебные пособия по программированию используют ее как классический пример рекурсивного алгоритма.

Суть задачи состоит в следующем. Где-то далеко в окрестностях города Ханой стоят три башни. Одна из башен состоит из 97 золотых дисков, положенных друг на друга - как кольца в детской пирамиде. Диаметры всех дисков различны и уменьшаются от нижнего к верхнему. Необходимо перенести все диски с одной башни на другую. При этом диски можно переносить только по одному с любой башни на другую. Ставить диск на землю или надевать больший на меньший нельзя! Согласно легенде этой работой заняты монахи

из местного монастыря. День и ночь они заняты переносом дисков с башни на башню. Когда они закончат всю работу - наступит конец света. Кстати, это вполне похоже на правду: для перемещения N дисков на другой стержень (по одному, не кладя больший на меньший) нужно сделать 2n-1 перемещений, что легко следует по индукции.

Для определения подхода к решению поставленной задачи, рассмотрим общий случай с п дисками. Если мы сможем сформулировать решение для п дисков в терминах решения для n-1 диска, то поставленная проблема была бы решена, поскольку задачу для n-1 диска можно будет, в свою очередь, решить в терминах n-2 дисков и так далее до тривиального случая одного диска. А для случая одного диска решение получается элементарным. Нужно просто переместить один единственный диск со столбика А на столбик С.

Таким образом, если сформулировать решение для п дисков в терминах п-1 диска, то мы фактически получим алгоритм рекурсивной процедуры, с помощью которой можно легко достичь цели поставленной задачи. Рассмотрим словесное описание алгоритма. Если n=1, тогда переместить этот диск со столбика А на столбик С и остановиться. В противном случае, надо поступить следующим образом: 1. переместить верхние n-1 диск со столбика А на столбик В, используя столбик С как вспомогательный. 2. переместить оставшийся нижний диск со столбика А на столбик С. 3. переместить п-1 диск со столбика В на столбик С, используя столбик А как вспомогательный.

Можно с уверенностью сказать, что т акая последовательность действий даст корректное решение для любого значения п. Это вытекает из следующего. Если n=1, то корректность очевидна. Если n=2, то мы знаем, что уже имеем решение для случая (n-l)-ro диска, которое равно 1. аналогично, если n=3, мы снова имеем решение для (n-l)-ro диска, которое равно 2 и т.д.

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


Дата добавления: 2015-07-16; просмотров: 56 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Формы рекурсивных процедур.| Program Hanoi_Towers;

mybiblioteka.su - 2015-2024 год. (0.005 сек.)