Использование рекурсивных алгоритмов для решения экономических задач (стр. 3 из 3)

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

Технология, называемая восходящим динамическим программированием (bottom – up dynamic pгogгamming) основана на том, что значение рекурсивной функции можно определить, вычисляя все значения этой функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Она применима к любому рекурсивному вычислению при условии, что мы можем позволить себе хранить все ранее вычисленные значения. Это в результате позволит уменьшить временную зависимость с экспоненциальной на линейную.

Нисходящее динамическое программирование (top – down dynamic pгogгamming). Оно позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления.

Таким образом, современные информационные технологии содержат достаточно средств, чтобы сделать теоретически эффективные рекурсивные алгоритмы, также эффективными и широко используемыми на практике.Преимущества рекурсиизаключаются в следующих аспектах:

-часто это наиболее легкий метод написания алгоритма для задач, которые можно решить с помощью рекурсии (число фибоначчи, факториал);

-рекурсивно реализованные алгоритмы, при правильных на то основаниях, имеют лаконичную запись и менее трудоёмки при последующей отладке и модификации, они сокращают временные затраты на разработку, отладку и модификацию программных средств;

-целый ряд структур данных и многие объекты современных языков программирования рекурсивны по самой своей сути (фрактальные объекты, иерархия классов в объектно – ориентированном программировании, древовидные регулярные структуры данных) и программы для работы с такими структурами выглядят намного более естественно в рекурсивной реализации;

-рекурсия делает код более читабельным (позволяет читать код с любого места, не просматривая его весь, отслеживая все изменения переменной), что облегчает отладку;

-рекурсия защищает от ошибок типа: «действия выполнены в не верном порядке», «использована неинициализированная переменная» и других аналогичных.

Недостатки рекурсии заключаются в следующем:

-велика возможность войти в бесконечный цикл;

-при использовании некоторых формул слишком большие затраты памяти компьютера (к примеру, при вычислении числа Фибоначчи или факториалов, необходимо запоминать все значения чисел и вычислять одни и те же значения по многу раз);

-в случае, если вызываемых функций будет очень много, может произойти переполнение стека;

-следует избегать использования рекурсии в случаях, когда требуется высокая эффективность, так как они требуют времени и дополнительных затрат памяти и обладают худшей временной эффективностью.

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

2. Программная реализация рекурсии

2.1. Примеры решения задач с помощью рекурсии

Задача 1. Числа Фибоначчи

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

Рассмотрим – вычисление N – ого по счёту числа Фибоначчи. Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:

F_n=F_{n – 1} + F_{n – 2} .

#include <iostream>

int fib(int n) {

if(n < 3)

return 1;

return fib(n – 2) + fib(n – 1);

}

int main() {

int n = 0;

std::cout << "Vvedite nomer chisla:&bsol;n";

std::cin >> n;

std::cout << "Result: chislo " << fib(n) << " eto " << n << "th po schetu chislo v ryade Fibonacci.&bsol;n";

return 0;

}

Результат работы программы представлен на рисунке 2.1.

Рис. 2.1. Числа Фибоначчи

Задача 2. Нахождениефакториала

#include <iostream>

int factorial(int n)

{

if(n==1 || n==0) return 1;

return n* factoгial (n – 1);

}

int main() {

int n = 0;

std::cout << "Vvedite chislo:&bsol;n";

std::cin >> n;

std::cout << "Factorial " << n << " raven " << factorial(n) << "&bsol;n";

return 0;

}

Результат работы программы представлен на рисунке 2.2.

Рис. 2.2. Факториал числа

Задача 3. Нахождение наибольшего общего делителя

#include <iostream>

int nod(int m, int n)

{

if (n == 0) return m;

else

return nod(n, m % n);

}

int main() {

int n = 0;

int m = 0;

std::cout << "Vvedite pervoe chislo:&bsol;n";

std::cin >> n;

std::cout << "Vvedite vtoroe chislo:&bsol;n";

std::cin >> m;

std::cout << "NOD raven "<< nod(m, n) << "&bsol;n";

return 0;

}

Результат работы программы представлен на рисунке 2.3.

Рис. 2.3. Нахождение наибольшего общего делителя

Рекурсия является в мощным инструментом для программистов. Но не следует забывать, что краткость записи рекурсивных функций не всегда означает высокую скорость их вычисления. И есть ряд задач, в которых рекурсия просто вредна (такова, например, задача вычисления кратчайшего пути в графе).

2.2. Решение экономической задачи с использованием рекурсивного алгоритма

Одной и наиболее востребованной операцией в экономической сфере является расчет процентов по вкладу. Пример задачи: вкладчик положил в банк сумму в sum денежных единиц под pr процентов за один период времени (год, месяц, неделя и т.д.). Составить программу, возвращающую величину вклада по истечении m периодов времени (m = 24).

#include <iostream>

#include <windows.h>

using namespace std;

double rec_fun(double sum, double pr, int m, int i)

{

if(m==i)

return sum;

sum+=(sum*(pr/100));

return rec_fun(sum, pr, m, i+1);

}

int main ()

{

int m;

double sum, pr;

cout<<"Vvedite nachalnuyu summu vklada: "<< endl;

cin>>sum;

cout<<"Vvedite ejemesyachniy procent po vkladu: "<< endl;

cin>>pr;

cout<<"Vvedite colichestvo mesyacev:"<< endl;

cin>>m;

cout<<"Za "<<m<<" mesyacev summa vklada sostavit: "<<rec_fun(sum, pr, m, 0)<<endl;

return 0;

}

Результат работы программы представлен на рисунке 2.4.

Рис. 2.4. Задача о сумме вклада

Проверка правильности решения задачи на Excel:

Рис. 2.5. Расчет задачи на Excel

Результаты обоих решений сходятся, следовательно ошибки в расчетах не возникло, программа работает правильно.

Заключение

На основании проведенного исследования можно сделать несколько выводов:

-во – первых, рекурсивные алгоритмы есть универсальное средство решения разнообразных алгоритмических проблем. Любая разрешимая задача такого рода имеет рекурсивное решение, которое при этом отличается изяществом и простотой для восприятия человеком;

-во – вторых, рекурсивные алгоритмы часто имеют более низкую асимптотическую сложность, чем эквивалентные им итерационные. То есть теоретически они быстрее;

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

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

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

Список использованных источников

1. C/C++. Программирование на языке высокого уровня / Т. А. Павловская. – СПб.: Питер, 2003. – 461 с: ил.

2. Баррон Д. Рекурсивные методы в программировании (Мир, 1974, 80 стр.).

3. Головешкин В.А., Ульянов М. В. Теория рекурсии для программистов. М.: ФИЗМАТЛИТ, 2006. 296 с.

4. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983.

5. Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965.

6. Харви Дейтел и Пол Дейтел Как программировать на C++. Бином, 2006.

7. Громов Ю.Ю., Татаренко С.И. Языки СИ и С++ для решения инженерных и экономических задач. Тамбов: Издательство ТГТУ, 2001.

8. www.intuit.ru

9. www.cyberforum.ru

10. www.tehnari.ru