Финансовые функции и рекурсия — страница 5
структуры функции inv(sum,p,n) позволяет получить еще один вариант её реализации, в котором количество рекурсивных вызовов в точности равно Сделать это можно так: Замечание. В любых ситуациях, в которых возникают вопросы о быстродействии алгоритма, желательно по возможности минимизировать общее количество рекурсивных вызовов. В рассмотренной задаче построить алгоритм с рекурсивными вызовами можно было бы значительно проще, исходя из конечной формулы для решения задачи и дихотомии. Однако путь, который мы прошли, имеет свои достоинства. Он позволяет в общем случае выявить ограничения на рекурсивную функцию, достаточные для столь малого количества рекурсивных обращений при её вычислении. Фактически, из проведенных рассуждений вытекает такое утверждение. Пусть функция F(,n,v) удовлетворяет условиям: F(,1,v) =g(,v), F(,n,v) =F(1,n,v), F(,n,v) =F(F(,k,v),nk,v) (1kn), где действительное число, n натуральное число, v=(v1,v2,…,vs) T вектор с числовыми компонентами, g(,v) функция, значения которой для и v из области определения F(,n,v) мы вычислять можем. Тогда рекурсивная программа-функция: вычисляет значение F(,n,v) ровно за рекурсивных вызовов. Доказательство этого факта с использованием свойств A, B и C можно провести так: Отсюда, при n=2k имеем а при n=2k+1 получаем Именно на этих соотношениях и базируется алгоритм, реализуемый программой-функцией F(,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() в том, что они выписываются без всякого вывода и практически без затруднений. Контрольные
Похожие работы
- Доклады
- Рефераты
- Рефераты
- Рефераты
- Контрольные