Ханойская башня

Cтраница 4

Рекурсивное решение проблемы состоит из двух этапов. Первый этап решения заключается в сведении данной проблемы к новой, похожей на исходную, но несколько проще. При решении задачи Ханойской башни этот этап состоял в замене переноса 64 дисков переносом 63 дисков. Подобная замена может производиться повторно до тех пор, пока решение проблемы не станет тривиальным. Задача Ханойской башни будет решена, когда для переноса не останется ни одного диска. [46]

Рекурсия в программе ханойские башни. [47]

Полная картина работы программы ханойскиебашни для случая с общим количеством дисков, равным 3, приведена в табл. 4.1. Здесь также имена представлены первыми буквами. Действия на уровне 4, когда высота 0, не расписаны. Время, нужное программе ханойскиебашни для переноса башни, состоящей из п дисков, приблизительно пропорционально 2; можно сказать, что этот алгоритм имеет экспоненциальную сложность в смысле временных затрат. Алгоритмы этого типа применять нежелательно, поскольку даже для вполне разумных значений входных данных время выполнения может становиться слишком большим. Самые мощные современные вычислительные машины, решая задачу Ханойской башни, могут вычислить ( но не напечатать) одно перемещение за одну миллионную долю секунды. Даже при такой скорости для расчета переноса башни из 64 дисков им потребуется около миллиона лет. [48]

Страницы: 1 2 3 4