Лабораторная работа №19. Тема: «Решение задач, реализуемых с помощью алгоритмов с возвращением»Тема: «Решение задач, реализуемых с помощью алгоритмов с возвращением». Цель работы: составление на языке Pascal программ с использованием рекурсии. Программные средства: система программирования Borland Pascal. Задача о «Ханойских башнях». В большом храме Бенареса бронзовая плита поддерживает 3 алмазных стержня, на один из которых Бог нанизал во время сотворения мира 64 золотых диска, образующих пирамиду. С тех пор монахи каждую секунду перекладывают по одному диску согласно правилам: o За один раз можно перекладывать только один диск; o Нельзя класть диск на диск, меньший по размеру; o Можно пользоваться только одним резервным стержнем. Составить программу с использованием рекурсии. Решение: 1.
1 шаг 3 шаг
Х У Z
2 шаг
2. Перенесем верхушку пирамиды, состоящую из (n-1)-го диска, с первого стержня на второй, затем перенесем один диск с первого стержня на третий, а потом перенесем верхушку пирамиды, состоящую из (n-1)-го диска, со второго стержня на третий. 3. Далее повторим алгоритм переноса, но уже для (n-1)-го диска, затем для (n-2)-го диска и так далее, пока не опустимся до одного диска.
|
