Итеративные программы

Главное преимущество метода Бью- немана — Леви заключается в том, что он не требует рекурсии при решении задачи о башне; достаточным оказывается простое итерационное решение. В программе, построенной по итерационному принципу, повторяющиеся действия выполняются в виде обыкновенного цикла, а не за счет последовательности рекурсивных процедур. Хотя рекурсивные программы привлекают краткостью и изящной формой, они требуют большого объема памяти. На примере рассмотренной иллюстрации мы видим, что для рекурсивного решения задачи о башне необходим большой объем памяти, чтобы хранить информацию о всех незавершенных стадиях процедуры БАШНЯ. Итеративные программы, подобные той, которая основана на алгоритме решения Бьюнемана — Леви, почти совсем не требуют памяти. Однако заменить рекурсивную программу итерационной, подобно тому как мы сделали это в задаче о башне, удается редко.

Понятия рекурсии и итерации представляют собой одну из многих противоположностей в вычислительной математике. Это своеобразные «инь» и «ян» в подходе к процессам обработки информации с повторяющимися процедурами. «Инь» и «ян» — основные понятия древнекитайской мифологии и натурфилософии, полярные первоначала. Они лежат в основе книги «I Ching» («Книга изменений»), «Инь» и «ян» подобны двоичным знакам 0 и I, имеющим фундаментальное значение в кодировании, принятом при вычислениях на цифровых машинах. В книге «I Ching» «инь» представляется двойной горизонтальной черточкой (— —), а «ян» — одинарной (— ). Эти символы группируются в наборы по шесть, образуя 64 гексаграммы (см. рисунок на с. 92). Интерпретируемая соответствующим образом, каждая гексаграмма представляет определенный выбор. «Верующий» тянет соломинки тысячелистника, чтобы определить, какая из этих гексаграмм имеет отношение к его жизни. Показанное здесь расположение символов приписывают Ван Вэну, правившему в 1 ISO г. до н.э.

Говоря о двоичных цифрах, я вспомнил еще олин способ решения головоломки «Ханойская башня». Если пронумеровать диски последовательно, как 1,2,3,.,л, начиная с наименьшего и кончая наибольшим диском, то каждый шаг в процессе решения задачи можно представить двоичным числом. Например, чтобы решить задачу с пятью дисками, составим список пятиразрядных двоичных чисел в порядке натурального ряда. Вот первые восемь пятиразрядных двоичных чисел:

 

0 Коментариев

Вы можете быть первым =)

Оставить коментарий