Более сложные случаи рекурсии

Пусть функция с натуральными аргументами и значениями определена рекурсивно условиями

где - некоторое число, а и - известные функции. Другими словами, значение функции в точке выражается через значение в точке . При этом предполагается, что для любого в последовательности

рано или поздно встретится .

Если дополнительно известно, что для всех , то вычисление не представляет труда: вычисляем последовательно

Написать нерекурсивную программу вычисления для общего случая.

Решение. Для вычисления вычисляем последовательность

до появления нуля и запоминаем ее, а затем вычисляем значения в точках этой последовательности, идя справа налево.

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

где - некоторое число, а , и - известные функции. Предполагается, что если взять произвольное число и начать применять к нему функции и в произвольном порядке, то рано или поздно получится .

Написать нерекурсивную программу вычисления .

Решение. Можно было бы сначала построить дерево, у которого в корне находится , а в сыновьях вершины стоят и - если только не равно нулю. Затем вычислять значения функции, идя от листьев к корню. Однако есть и другой способ.

Обратной польской записью (или постфиксной записью ) выражения называют запись, где знак функции стоит после всех ее аргументов, а скобки не используются. Вот несколько примеров:

Постфиксная запись выражения позволяет удобно вычислять его с помощью . Этот калькулятор имеет стек, который мы будем представлять себе расположенным горизонтально (числа вынимаются и кладутся справа), и клавиши - числовые и функциональные. При нажатии на клавишу с числом это число кладется в стек. При нажатии на функциональную клавишу соответствующая функция применяется к нескольким аргументам у вершины стека. Например, если в стеке были числа

и нажата функциональная клавиша , соответствующая функции от двух аргументов, то в стеке окажутся числа

Перейдем теперь к нашей задаче. В процессе вычисления значения функции мы будем работать со стеком чисел, а также с последовательностью чисел и символов f, l, r, h, которую мы будем интерпретировать как последовательность нажатий клавиш на стековом калькуляторе. Инвариант такой:

Пусть нам требуется вычислить значение . Тогда вначале мы помещаем в стек число , а последовательность содержит единственный символ f. (При этом инвариант соблюдается.) Далее с последовательностью и стеком выполняются такие преобразования:

Здесь , , - числа, - последовательность чисел, - последовательность чисел и символов f, l, r, h. В последней строке предполагается, что . Эта строка соответствует равенству

Преобразования выполняются, пока последовательность не станет пуста. В этот момент в стеке окажется единственное число, которое и будет ответом.

Библиографический список

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2007.

2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2007.

3. Окулов С.М. Программирование в алгоритмах. М.: Бином, 2007.

4. Кнут Д. Искусство программирования. Т. 4 Вып.2. Генерация всех кортежей и перестановок. М.: Вильямс, 2008.

5. Кнут Д. Искусство программирования. Т. 4 Вып.2. Генерация всех сочетаний и разбиений. М.: Вильямс, 2008.

6. Кнут Д. Искусство программирования. Т. 4 Вып.2. Генерация всех деревьев. История комбинаторной генерации. М.: Вильямс, 2008.

7. Седжвик Р. Фундаментальные алгоритмы на С++. М.: Вильямс, 2011.

8. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н.И. Лобачевского, 2004.

9. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2012.

Содержание

Введение 4

Тема 1. Алгоритмы на графах. 6

Лекция 1. Начальные понятия теории графов. 7

Лекция 2. Поиск в глубину и ширину. 21

Лекция 3. Эйлеровы и гамильтоновы циклы. 35

Тема 2. Алгоритмы комбинаторного перебора. 48

Лекция 4. Базовые комбинаторные объекты. 49

Лекция 5. Коды Грея. 55

Лекция 6. Применение методов комбинаторного перебора. 61

Тема 3. Общие методы разработки алгоритмов. 66

Лекция 7. Обход дерева и перебор с возвратом. 67

Лекция 8. Рекурсия. 78

Лекция 9. Построение итеративных алгоритмов по рекурсивным. 90

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 99

Шутов Антон Владимирович Медведев Юрий Алексеевич

СТРУКТУРЫ И АЛГОРИТМЫ КОМПЬЮТЕРНОЙ

ОБРАБОТКИ ДАННЫХ

Курс лекций

Издается в авторской редакции

Отпечатано в отделе оперативной полиграфии ВГГУ

600014, Г. Владимир, ул. Университетская, 2, тел. 33-87-40

101