Финансовые функции и рекурсия

invest(sum,p,n) = sum×(1+p/100) n.

Однако в учебных целях нас будет интересовать рекурсивный вариант алгоритма решения задачи. Её параметризация реализована в постановке. Рекурсию будем осуществлять по параметру n. База рекурсии очевидна. В самом деле, если вклад положен на хранение и взят сразу, то есть до истечения первого периода времени начисления процентов, то возврату подлежит н

ачальная сумма вклада - sum. Далее, декомпозиция может быть реализована исходя из следующего факта. Положить некоторую сумму в банк на n периодов – это то же самое, что положить эту сумму на n – 1 период, взять и снова положить на 1 период. Соответствующий вариант программы-функции решения задачи выглядит так:

(1)

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

(2)

В данной и подобной ей задачах указанные декомпозиционные посылки программно реализуются приблизительно с равной степенью сложности и, тем самым, обе имеют право на существование. Однако может возникнуть ситуация, когда предпочтение должно быть отдано той или иной конкретной посылке. Например, если в последующем имеется необходимость перейти к нерекурсивному варианту программы, то лучше пользоваться посылкой первого типа, а если есть проблемы с доказательством правильности реализуемого алгоритма, то целесообразно работать с посылкой второго типа.

Нетрудно видеть, что общее количество рекурсивных вызовов при вычислении invest(sum,p,n) и invest1(sum,p,n) равно n. Можно было бы уменьшить это значение до величины floor(log2(n)) +1, где floor(a) - целая часть натурального числа a, исходя из следующих двух декомпозиционных посылок.

Пусть сумма sum=m× g денежных единиц помещена на вклад при ставке в p процентов за период. Тогда через n периодов sum возрастет до той же самой величины, что и совокупная сумма m отдельных вкладов по g денежных единиц каждый, также помещенных под р процентов за период. Не ограничивая общности, величину sum можно считать целым неотрицательным числом. В противном случае можно было бы перейти к иному номиналу денежных единиц. Значения m и g также будем считать целыми числами.

Положить некоторую сумму sum в банк на n периодов – это то же самое, что положить эту сумму на k (0£k£n) периодов, взять и снова положить на n-k периодов.

Основанную на этих посылках рекурсивную функцию для решения задачи 1 обозначим через inv(sum,p,n). Указанные посылки обнаруживают такие свойства этой функции.

Первая посылка.

В частности, при m=1 получаем:

Первая и вторая посылки. Пусть k=floor(n/2), тогда.

Отсюда при n=2×k сразу же получаем:

При n=2×k+1 имеем:

Выведенные соотношения для inv() позволяют записать такую программу для её вычисления:

Общее количество рекурсивных вызовов при счете по этой программе-функции можно было бы подсчитать с помощью следующей вспомогательной рекурсивной функции:

и оно действительно равно

Контрольные примеры.

Незначительная перестройка структуры функции inv(sum,p,n) позволяет получить еще один вариант её реализации, в котором количество рекурсивных вызовов в точности равно Сделать это можно так:

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

Пусть функция F(a,n,v) удовлетворяет условиям:

F(a,1,v) =g(a,v),

F(a,n,v) =a×F(1,n,v),

F(a,n,v) =F(F(a,k,v),n-k,v) (1£k£n),

где a - действительное число, n - натуральное число, v=(v1,v2,…,vs) T - вектор с числовыми компонентами, g(a,v) - функция, значения которой для a и v из области определения F(a,n,v) мы вычислять можем. Тогда рекурсивная программа-функция:

вычисляет значение F(a,n,v) ровно за рекурсивных вызовов.

Доказательство этого факта с использованием свойств A, B и C можно провести так:

Отсюда, при n=2×k имеем

а при n=2×k+1 получаем

Именно на этих соотношениях и базируется алгоритм, реализуемый программой-функцией F(a,n,v).

И в заключение замечания приведем пример функции, удовлетворяющей условиям A, B и С: где в области определения функции f(v) её значения мы вычислят умеем.

Задача о величине вклада после снятия денег в конце каждого периода

Вкладчик положил в банк сумму в sum денежных единиц под p процентов за один период времени. В конце каждого периода вкладчик после начисления процентов снимает со счета A денежных единиц. Определить сумму вклада через n периодов времени.

Решение. Данная задача весьма похожа на задачу 1. Рекурсивная программа-функция waste(sum,p,A,n) реализует декомпозицию, исходя из такого утверждения. Положить сумму sum в банк на n периодов со снятием в конце каждого периода по A денежных единиц – это то же самое, что положить данную сумму на тех же условиях на n – 1 период, взять, снова положить на 1 период и затем снять A единиц.

 Скачать реферат