Форум программистов, компьютерный форум CyberForum.ru

Объяснить рекурсию (на примере ханойской башни) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Работа с массивами http://www.cyberforum.ru/cpp-beginners/thread207399.html
Определить значения и адреса элементов массива, вычисляемых по формуле X(катое)=a(катое)/k(факториал).
C++ Матрицы Помогите с программой: Дана квадратная матрица А порядка n. Найти А в четвертой степени http://www.cyberforum.ru/cpp-beginners/thread207390.html
C++ выводит неверный ответ
#include <iostream.h> #include <stdio.h> const int n = 100; int main (int argc, char * const argv) { int x; cout << "введите размер массива "; cin >> x; int mas;
Создать класс C++
Для соответствующего класса, перегрузить арифметические операции(+,-,*,/). При перезгузке арифметические действия должны выполняться относительно только числовых полей!!! Создать несколько объектов класса и проинициализировать их с помощью конструктора с параметрами. Создать несколько дополнительных объектов таким образом, чтобы: - первый объект являлся суммой двух других объектов; - второй...
C++ Абстрактные методы или указатели на функции? http://www.cyberforum.ru/cpp-beginners/thread207345.html
Сабж для класса систем дифференциальных уравнений вида y'=f(x,y) Что лучше: класс с полем указателя на вектор функцию и передача указателя в конструктор, или внутри класса абстрактный метод, а в программе его перекрывать? Оба метода работают. Но какой логичнее и/или лучше?
C++ Как поменять местами элементы вектора ? собственно вопрос совпадает с темой, как поменять местами 2 элемента вектора ? в C++ Добавлено через 25 минут все, не надо, сам разобрался. подробнее

Показать сообщение отдельно
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
16.12.2010, 21:11     Объяснить рекурсию (на примере ханойской башни)
Итак, объясняю, какова логика решения задачи про ханойские башни.
Суть в том, что у нас имеется пирамида из n дисков, которая надета на один из штырей, и ещё два штыря - временный и целевой. Суть решения заключается в том, чтобы разбить нашу задачу на подзадачи, а именно - делим нашу пирамиду на две части - на пирамиду из n - 1 дисков (верхний набор) и на один единственный диск. Так вот, мы (абстрактно) берём нашу пирамиду из n - 1 дисков, переносим её на временный штырь, затем переносим наш единственный диск на целевой штырь, а затем переносим всю пирамиду на целевой штырь поверх уже перенесённого последнего диска.
Поскольку мы не можем перенести всю пирамиду целиком, то мы меньшую пирамиду снова делим на две - пирамиду из уже n - 2 дисков и на отдельный диск и к полученной задаче применяем тот же алгоритм. В итоге мы добираемся до элементарной пирамиды из единственного диска, которую просто переносим на целевой штырь. Тут мы начинаем разворачивать рекурсию - вспоминать, что помимо перенесённой части изначальной пирамиды у нас есть ещё один диск - основание пирамиды. Теперь мы переносим это основание на целевой штырь, и всю нашу пирамиду (которая сейчас находится на временном штыре) переносим поверх её основания - диска, теперь находящегося на целевом штыре. Для этого снова применяем тот же алгоритм разбивания пирамиды на части. Перенеся часть пирамиды на основание, вспоминаем, что у полученной пирамиды так же отдельно есть основание, и переносим её на это основание. Так происходит до тех пор, пока вся изначальная пирамида из n дисков не окажется на целевом штыре.
Вся фишка нашей рекурсивной функции не в том, что она физически что-то куда-то переносит, а в том, что она просто-напросто меняет функции штырей, ведь для каждой нашей подзадачи как целевой, как временный, так и исходный штыри могут меняться местами, т.е. перенесли мы пирамиду из, скажем, 4 дисков на временный (для неё) штырь, перенесли последний, пятый диск на целевой штырь, а для перенесённой части пирамиды из 4 дисков изначально временный штырь становится исходным, а в качестве временного будет служить изначально исходный. При этом глобальные функции штырей сохраняются (ведь для нас-то важны не функции штырей в пределах какой-либо из подзадач, а их функции для нашей изначальной задачи - для пирамиды из n дисков, вот эти глобальные назначения штырей функция и выводит на экран). Так вот функция всё то, что я описал, и делает. Сначала проверяется, больше ли n нуля (есть ли ещё диски для переноса), затем вызывает сама себя для n - 1 штыря, и меняет функции штырей (в качестве временного теперь выступает целевой, а в качестве целевого - временный). Затем, внутри этой вызванной функции снова проверяется количество дисков и вызывается ещё одна копия функции уже для ещё меньшей пирамиды из (n - 1) - 1, и снова меняется функция штырей. Так происходит, пока функция не вызовется для пирамиды из одного диска. Тогда будет напечатан мнимый перенос диска с одного штыря на другой и вызвана функция уже для переноса части пирамиды поверх этого перенесённого последнего штыря. Затем снова будет напечатан перенос, и снова какая-то часть пирамиды будет перенесена поверх перенесённого диска. Таким образом наши разрозненные пирамидки будут собираться в одну - изначальную, состоящую из n дисков.
Вообще, главное здесь - понять, что функция и понятия не имеет о том, что нам нельзя класть больший диск поверх меньшего, это заложено в алгоритме, а функция лишь следует ему. Она на каждом шаге всего лишь печатает номера штырей - исходного и целевого, но если мы вспомним, что для каждого экземпляра функции назначения штырей меняются (целевой может стать временным, временный - исходным и т.д.), то становится очевидно, как происходит это мнимый обмен дисков.
 
Текущее время: 00:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru