Пусть функция 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. В последней строке предполагается, что .Эта строка соответствует равенству
Преобразования выполняются, пока последовательность не станет пуста. В этот момент в стеке окажется единственное число, которое и будет ответом.
Замечание. Последовательность по существу представляет собой стек отложенных заданий (вершина которого находится слева).