Финансовые функции и рекурсия (стр. 2 из 7)

Основанную на этих посылках рекурсивную функцию для решения задачи 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 единиц.

(3)

Нетрудно понять, на какую посылку опирается при декомпозиции рекурсивная программа-функция waste1(sum,p,A,n), решающая ту же самую задачу о динамике вклада.

(4)

Замечание 1. Конечная формула для решения задачи 2 выглядит так:

Выводится она следующим образом.

Одно из преимуществ “формул” waste() и waste1() в том, что они выписываются без всякого вывода и практически без затруднений.

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

Замечание 2. В связи с задачей о динамике вклада может быть поставлен и такой вопрос. Сколько лет подряд вкладчик может снимать со счета по A денежных единиц в конце каждого периода после начисления процентов, если он положил в банк сумму в S единиц при ставке p процентов. Ответ на него может дать рекурсивная функция year(S,p,A):

Здесь случай неубывания величины вклада выделен отдельно (lo³S), рекурсия организована по остаткам вклада после периодов, в которых хватило денег на очередную выплату в A единиц.

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

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

Вкладчик положил в банк pv денежных единиц на nper периодов при неизменной банковской ставке в rate процентов. В дальнейшем он предполагает в конце (type=0) или начале (type=1) каждого периода вносить (забирать) по pmt денежных единиц. Какой будет величина вклада через nper периодов?

Решение. Данная задача является прямым обобщением задач 1 и 2 и может быть решена с помощью встроенной в Excel функции fv(). Однако нас будут интересовать её рекурсивные аналоги. Будем считать, что знак величины pmt определяет тип операции, совершаемой вкладчиком в конце или начале каждого периода. При pmt³0 деньги вносятся на счет, а при pmt<0 деньги снимаются со счета (в Excel наоборот!). Далее, пусть знак pv определяет, имеет ли вкладчик деньги на счету или он должен банку. При pv³0 деньги на счету есть, при pv<0 имеется задолженность в |pv| денежных единиц (в Excel наоборот!).

Пусть fv(rate,nper,pmt,pv,type) - функция для решения исходной задачи. Ниже приведено два варианта (fv1(), fv2()) рекурсивной реализации fv():

Дадим пояснения к функциям fv1() и fv2(), например, при type=0. Параметризация задачи фактически осуществлена в её постановке. Базой рекурсии для обоих предложенных вариантов служит случай nper=0. Иными словами, если pv денежных единиц положить в банк и сразу же их забрать, то будет возвращена та же самая сумма. Декомпозиция для fv1() и fv2() проведена, исходя из того, что решение исходной задачи по конечному результату равносильно соответственно совокупности следующих действий. Для fv1(): “Положить на тех же условиях pv денежных единиц в банк на nper-1 период, снять всю сумму с вклада и, наконец, на тех же условиях снова положить её на один период”. Для fv2(): “Положить на тех же условиях pv денежных единиц в банк на 1 период, снять всю сумму с вклада и, наконец, на тех же условиях снова положить её на nper-1 период”. Именно это и реализовано в соответствующих программах функциях.

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

Задача о изменяющихся процентных ставках

В банк положена сумма в S денежных единиц. Пусть банк проводит начисления в процентах: в течение n0 периодов - по ставке p0, затем в течение n1 периодов - по ставке p1 и т.д. и, наконец, в течение nk-1 периодов - по ставке pk-1. Считая nj (j=0. . k-1) натуральными числами, вычислить размер вклада через n0+n1+…+nk-1 периодов.

Решение. Рассмотрим векторы длин периодов n и процентных ставок p:

n=(n0,n1,…,nk-1) T, p=(p0,p1,…,pk-1) T.

Данная задача является обобщением задачи 1 и при длине вектора n, равной единице, совпадает с ней. Пусть revise(S,p,n) - решение задачи 4. Тогда, в силу сказанного, при length(n) =1 имеем

revise(S,p,n) =invest(S,p,n),

и это соотношение может служить базой рекурсии. Декомпозицию реализуем, исходя из следующих соображений. Пусть length(n) >1 и задача 4 решена для векторов n1 и p1, полученных отбрасыванием последнего компонента соответственно у векторов n и p. Образовавшийся при этом новый размер вклада обозначим через sum. Тогда для получения решения исходной задачи с векторами n и p остается подсчитать сумму, возвращаемую при инвестировании величины sum на последние nk-1 периодов под pk-1 процентов. Иными словами, необходимо еще раз решить задачу 1, то есть вычислить значение функции invest(sum,pk-1,nk-1). Именно эти соображения и использованы при написании функции revise():