Пусть функция f с натуральными аргументами и значениями
определена рекурсивно условиями
где a -- некоторое число, а h и l -- известные функции.
Другими словами, значение функции f в точке x выражается через
значение f в точке l(x) . При этом предполагается, что для любого
x в последовательности
рано или поздно встретится 0.
Если дополнительно известно, что для всех x , то
вычисление f не представляет труда: вычисляем последовательно
f(0) , f(1) , f(2) ,
.
8.3.1. Написать нерекурсивную программу вычисления f для общего
случая.
Еще более сложный случай из следующей задачи вряд ли
встретится на практике (а если и встретится, то проще рекурсию не
устранять, а оставить). Но тем не менее: пусть функция f с
натуральными аргументами и значениями определяется соотношениями
где a -- некоторое число, а l , r и h -- известные
функции. Предполагается, что если взять произвольное число и
начать применять к нему функции l и r в произвольном
порядке, то рано или поздно получится .
8.3.2. Написать нерекурсивную программу вычисления f .
Обратной польской записью
(или постфиксной
записью) выражения называют запись, где знак функции стоит
после всех ее аргументов, а скобки не используются. Вот
несколько примеров:
Постфиксная запись выражения позволяет удобно вычислять его с
помощью стекового калькулятора.
Этот калькулятор имеет
стек, который мы будем представлять себе расположенным
горизонтально (числа вынимаются и кладутся справа),
и клавиши -- числовые и функциональные.
При нажатии
на клавишу с числом это число кладется в стек. При нажатии на
функциональную клавишу соответствующая функция применяется к
нескольким аргументам у вершины стека. Например, если в стеке
были числа
и нажата функциональная клавиша s , соответствующая функции от двух аргументов, то в стеке окажутся числа
-.5mm
Перейдем теперь к нашей задаче. В процессе вычисления значения
функции f мы будем работать со стеком чисел, а также с
последовательностью чисел и символов f, l, r, h,
которую мы будем интерпретировать как последовательность нажатий
клавиш на стековом калькуляторе. Инвариант такой:
если стек чисел представляет собой текущее состояние стекового калькулятора, то после нажатия всех клавиш последовательности в стеке останется единственное число, и оно будет искомым ответом.
Пусть нам требуется вычислить значение f(x) . Тогда вначале мы помещаем в стек число x , а последовательность содержит единственный символ f. (При этом инвариант соблюдается.) Далее с последовательностью и стеком выполняются такие преобразования:
Здесь x , y , z -- числа, X -- последовательность чисел, P -- последовательность чисел и символов f, l,
r, h. В последней строке предполагается, что
.Эта строка соответствует равенству
Преобразования выполняются, пока последовательность не станет
пуста. В этот момент в стеке окажется единственное число,
которое и будет ответом.
Замечание. Последовательность по существу представляет собой стек отложенных заданий (вершина которого находится слева).