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

  • Просмотров 1582
  • Скачиваний 5
  • Размер файла 202
    Кб

структуры функции 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),nk,v)

(1kn), где   действительное число, n  натуральное число, v=(v1,v2,…,vs) T  вектор с числовыми компонентами, g(,v)  функция, значения которой для  и v из области определения F(,n,v) мы вычислять можем. Тогда рекурсивная программа-функция: вычисляет значение F(,n,v) ровно за рекурсивных вызовов. Доказательство этого факта с использованием свойств A, B и C можно провести так: Отсюда, при n=2k имеем а при n=2k+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() в том, что они выписываются без всякого вывода и практически без затруднений. Контрольные