Файл: Рекурсивные и итерационные алгоритмы: особенности и примеры использования (ПОНЯТИЕ РЕКУРСИВНОГО АЛГОРИТМА).pdf

//
/*подключим необходимые библиотеки*/
#include "stdafx.h"
#include "stdio.h"
#include <iostream>
#include <conio.h>
/*объявляем необходимые переменные*/
int N_polinom; //порядок полинома
float a, b; //начало и конец хорды
float epsilon; //погрешность нахождения корня
int polinom_massiv_length;
float *polinom_mas = 0;
using namespace std;
/*прототипы функций*/
float f_polinom(float x);
float f_iteration(float a, float b, float epsilon);
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL, "Russian"); //подключение русского языка
/*блок получения значений*/
puts("Введите порядок полинома\n");
std::cin >> N_polinom;
polinom_mas = new float[N_polinom+1]; //резервируем память под массив (не забыть потом подчистить за собой!!!)
/*принимаем из входного потока коэффициенты*/
/*для упрощения последующего программирования введем переменную длины массива, так как длина массива длиньше полинома на +1*/
polinom_massiv_length = N_polinom + 1;
std::cout << "Введите коэффициенты полинома, начиная с a0 и далее" << endl;
for (int count = 0; count < polinom_massiv_length; count++){
/*приглашение на ввод*/
std::cout << "Введите значение " << "a" << count << ": ";
std::cin >> polinom_mas[count];
}
/*получаем интервал и эпсилон*/
std::cout << "Введите начальный интервал поиска корня" << endl;
std::cin >> a;
std::cout << "Введите конечный интервал поиска корня" << endl;
std::cin >> b;
std::cout << "Введите допустимую погрешность" << endl;
std::cin >> epsilon;
/*вычисление корня*/
float koren = f_iteration(a, b, epsilon);
/*вывод значений корня*/
cout <<"X="<< koren << endl;
delete[] polinom_mas; //подчищаем за собой память
_gettch();
return 0;
}
/*функция построения полинома*/
float f_polinom(float x){
float temp_x=0;
for (int count = 0; count < polinom_massiv_length; count++){
temp_x += (pow(x, count))*polinom_mas[count]; //вычисление значения полинома
}
return(temp_x);
}
/*функция итерации*/
float f_iteration(float a, float b, float epsilon)
{
while (fabs(b - a) > epsilon)
{
a = b - (b - a) * f_polinom(b) / (f_polinom(b) - f_polinom(a));
b = a - (a - b) * f_polinom(a) / (f_polinom(a) - f_polinom(b));
}
// a - i-1, b - i-тый члены
return b;
}

Разберем подробно работу программы. В строках с 1 по 7 происходит подключение стандартных библиотек.

В строках с 8 по 12 объявляются необходимые переменные, такие как значение порядка полинома, начало и конец интервала приближений и необходимая точность.

В 13 строке подключается стандартное пространство имен, необходимое для корректной работы операторов cin и cout.

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

С 20 по 37 строчку происходит получение входных значений, необходимых для работы программы – степеней полинома, коэффициентов перед этими степенями, интервала расчёта и допустимой погрешности.

39 строка вычисление корня, 41 строка – вывод результата.

42-44 строки необходимы для корректной работы программы, здесь очищается память, ставится задержка в консоли, возвращается значение нормального завершения программы.

Разберем более подробно работу функций, вызываемых в строках 47-52 и 54-60.

Первая функция – это функция построения полинома. Она начинает работать с присвоения нулевого значения временной переменной temp. после этого, в каждой итерации цикла происходит увеличение значения этой переменной на величину, полученную умножением значения x в степени, совпадающей со значением номера элемента массива на значение этого элемента. Последним значением счётчика служит порядок полинома.

Эта функция рекурсивно вызывается во второй функции, которая производит вычисления двух значений a и b, где a – нижнее значение границы ходы, а b – верхнее. После этого, корень полинома считается за b и проверяется равенство – попадает ли этот корень в заданное значение точности. Если попадает – то значение b возвращается как корень полинома, если нет – то происходит еще одна итерация цикла.

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

На случайных параметрах программа отрабатывает без ошибок.

Рисунок 5 – Набор случайных входных параметров.

Рисунок 6 – Набор параметров для полинома, не имеющего корней.

ГЛАВА 4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕКУРСИВНЫХ АЛГОРИТМОВ

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

Рассмотрим – вычисление 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:\n";
std::cin >> n;
std::cout << "Result: chislo " << fib(n) << " eto " << n << "th po schetu chislo v ryade Fibonacci.\n";
return 0;
}

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

Рассмотрим задачу нахождение факториала.

#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:\n";
std::cin >> n;
std::cout << "Factorial " << n << " raven " << factorial(n) << "\n";
return 0;
}

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

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

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

#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:\n";
std::cin >> n;
std::cout << "Vvedite vtoroe chislo:\n";
std::cin >> m;
std::cout << "NOD raven "<< nod(m, n) << "\n";
return 0;
}

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

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

Рассмотрим реальную задачу из экономической теории.

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

Для чего человек несет свои сбережения в банк? Конечно же, чтобы обеспечить их сохранность, и самое главное - получить доходы. И вот здесь знание формулы простых или сложных процентов, а также умение составить предварительный расчет процентов по депозиту как никогда пригодится. Ведь прогнозирование процентов по вкладам или процентов по кредитам относится к одной из составляющих разумного управления своими финансами. Такое прогнозирование хорошо осуществлять до подписания договоров и совершения финансовых операций, а также в периоды очередного начисления процентов и причисления их к вкладу по уже оформленному депозитному договору.

Воспользуемся источником [11], для составления методики расчета.

Для начисления процентов по вкладам (депозитам), да и кредитам тоже, применяются следующие формулы:

- формула простых процентов;

- формула сложных процентов.

Порядок начисления процентов по вышеперечисленным формулам осуществляется с использованием фиксированной или плавающей ставки. Чтобы не возвращаться к данному вопросу в дальнейшем, сразу поясним значение слов и отличия фиксированной ставки и плавающей ставки.

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

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

Для начисления процентов с применением формул, необходимо знать параметры вложения средств на депозитный счет, а именно:

- сумму вклада (депозита);

- процентную ставку по выбранному вкладу (депозиту);

- цикличность начисления процентов (ежедневно, ежемесячно, ежеквартально и т.д.);

- срок размещения вклада (депозита);

- иногда требуется и вид используемой процентной ставки - фиксированной или плавающей.

Теперь рассмотрим названные выше стандартные формулы процентов, которые применяются для расчета процентов по вкладам (депозитам).

1. Формула простых процентов.

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

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

(7)

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

I – годовая процентная ставка;

t – количество дней начисления процентов по привлеченному вкладу;

K – количество дней в календарном году (365 или 366);

P – первоначальная сумма привлеченных в депозит денежных средств;

Sp – сумма процентов (доходов).

2. Формула сложных процентов.

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

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

Формула сложных процентов выглядит так:

(8)

где I – годовая процентная ставка;

j – количество календарных дней в периоде, по итогам которого банк производит капитализацию начисленных процентов;

K – количество дней в календарном году (365 или 366);

P – первоначальная сумма привлеченных в депозит денежных средств;