Стр. 20 - Основы алгоритмов и структур данных

18 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
код c код b
стек возврата
(адрес возврата)
данные а данные b данные c
поколе
ние 1
поколе
ние 2
поколе
ние 3
40
40
а доходит до
вызова b
код а
Рис. 12. Использование оперативной памяти при работе программы
Адрес, следующий за вызовом команды, записывается в стек возврата, и
управление передается на первую команду вызываемой подпрограммы, b
захватывает память для своих данных. Последняя работа b – работа очистки
памяти. Когда b дошла до последней команды (до конца), она читает адрес из
стека возврата и предает на него управление.
Таким образом, a продолжает свою работу, и доходит до вызова c . Адрес
следующей за вызовом команды заносится в стек возврата, а управление
передается на первую команду c. с – рекурсивная функция. Каждое поколение
с, начиная с первого, в начале своей работы захватывает память для своих
данных, а в конце своей работы освобождает эту память, читает адрес из стека
возврата и передает на него управление.
4. МЕТОДЫ ПОИСКА
Задачи поиска разбиваются на 2 класса:
1-й класс. Исчерпывающий поиск – дает ответы на вопросы следующих
типов: существует ли способ, сколько существует способов, какой способ
лучше, перечислить все возможности. Ответ на такого рода вопросы, как
правило, требует полного или частичного перебора всех элементов или
вариантов.
Некоторые методы исчерпывающего поиска:
1. Исчерпывающий рекурсивный поиск.
2. Метод динамического программирования.
3. Метод ветвей и границ.