Задание 4. Разработайте рекурсивную подпрограмму
«Ханойская башня». Имеется три колышка. На первом нанизаны m пронумерованных колец. Необходимо расположить кольца в
том же порядке на любом из оставшихся колышков. При этом кольца можно
переносить только по одному, причем не разрешается класть кольцо с большим
номером на кольцо с меньшим номером.

5.8. Практикум. Полный и ограниченный перебор.

Реализация ограниченного перебора с
использованием рекурсии

Задания для самопроверки

Существует класс задач, в которых из некоторого количества вариантов
необходимо выбрать наиболее подходящий (оптимальный). Для таких задач далеко не
всегда удается найти алгоритм, который позволил бы получить решение без анализа
всех или большого количества комбинаций исходных данных, т.е. без осуществления перебора. Осуществление полного
перебора требует много времени. Вычислительная сложность решения задач с
использованием перебора обычно оценивается как 0(п!) или даже 0(пп).

Для решения задач данного типа применяют две
стратегии:

•       
формируют
сразу всю комбинацию исходных данных и выполняют ее анализ в целом;

•        
генерацию
и анализ комбинации осуществляют по частям.

Если имеется возможность, анализируя часть комбинации
исходных данных, оценить ее перспективность с точки зрения получения решения,
то вторая стратегия позволит получить результат за меньшее время за счет
исключения из рассмотрения всех комбинаций, в которые входит данная часть.
Исключение бесперспективных комбинаций (<отсечение вариантов) позволяет осуществить не полный, а ограниченный перебор.