 |
3. Рекурсия. Лекция 20. Нахождение приближенного значения корня нелинейного уравнения. 1. Методы нахождения корней уравнения f(x)=0
|
|
|
|
3. Рекурсия
В языке С++ допустимо рекурсивное определение функций, при котором функция может вызывать сама себя. Надо сказать, что такие функции работают медленнее, чем нерекурсивные. Однако они незаменимы при обработке динамических структур, например деревьев.
Пример. Вычислить сумму факториалов целых чисел, принадлежащих отрезку [m; n].
Это классическая задача, которую можно решить с использованием рекурсивной функции.
Ход выполнения работы
1. В файле f. h опишем рекурсивную функцию, вычисляющую факториал числа n:
int fact(int n)
{
if(n= =0 || n= =1) return 1;
else
return n*fact(n-1);
}
Как видно, среди операторов тела функции происходит ее вызов, т. е. функция является рекурсивной.
В файле главной функции запишем основной алгоритм решения задачи на языке С++:
#include " stdio. h"
#include " stdlib. h"
#include " iostream. h"
#include " iomanip. h"
#include " f. h"
int main()
{
int i, n, m, s;
cout< < " Введите границы отрезка m=";
cin> > m;
cout< < " n=";
cin> > n;
if(m< n)
{
//вычислим сумму
s=0;
for(i=m; i< =n; i++)
//вызываем функцию fact(); ее аргумент изменяется в цикле
s=s+fact(i);
//выведем значение суммы на экран
cout< < " summa=" < < s< < endl;
}
else
cout< < " Границы отрезка введены неверно" < < endl;
return 1;
}
Примечание. При вычислении 4! функция fact() будет вызывать сама себя три раза следующим образом:
4*fact(3)
3*fact(2)
2*fact(1)
Как только значение параметра этой функции достигнет 1, результат ее работы будет вычисляться в обратном порядке:
2*1=2
3*2=6
4*6=24
Лекция 20
Нахождение приближенного значения корня нелинейного уравнения
Цели:
ü познакомиться с алгоритмаминахождения приближенного значения корня нелинейного уравнения на заданном отрезкес заданной точностью;
|
|
|
ü методику написания и перевода таких алгоритмов на язык программирования С++ и разработки соответствующего проекта в среде Visual C++ 6. 0.
Нелинейные уравнения – это уравнения, в которые переменная входит в степени больше чем 1. Решить уравнение – значит, найти его корень. Корнем называется такое значение переменной, при подстановке которого в уравнение вместо переменной уравнение превращается в верное равенство.
1. Методы нахождения корней уравнения f(x)=0
на отрезке [a; b] с заданной точностью eps
Постановка задачи заключается в следующем. Дан отрезок [a; b], на котором находится корень уравнения f(x)=0. Найти с заданной точностью eps корень этого уравнения. Рассмотрим три метода нахождения корней нелинейных уравнений.
1. 1. Метод дихотомии (половинного деления)
Данный метод основывается на утверждении, что если на отрезке [a; b] содержится корень уравнения, то значения f(a) и f(b) имеют разные знаки, т. е. f(a)·f(b)< 0.
Схема метода
Отрезок делится пополам – середина обозначается через точку c (рис. 14). Если |a-b|> =eps, то вычисле-ния продолжаются. Эта проверка означает, что если |a-b|< eps, то длина отрезка, на котором находится корень уравнения, достаточна мала и вычисления можно прекратить, а за значение корня можно взять середину этого отрезка, т. е. корень уравнения вычислен с заданной точность eps. Происходит проверка f(a)·f(c)< 0 или нет. Если да, то значение c присваивается перемен-ной b, иначе значение c присваива-ется переменной a. Если |a-b|> =eps, то опять происходит проверка f(a)·f(c)< 0 или нет. Если да, то значение c присваивается переменной b, иначе значение c присваивается перемен- ной a и т. д. Графически этот метод изображен на рис. 14.
Опишем алгоритм и соответствующую программу для нахождения корней уравнения ln(x-3)=0 на отрезке [3. 5; 5] с помощью этого метода:
|
|
|
| Алгоритм | Программа |
| объявление вещ: fa, fb, fc, a, b, c, eps ввод а ввод b fa=ln(a-3) fb=ln(b-3) если fa*fb< 0 ввод eps c=(a+b)/2 fc=log(c-3) пока (|a-b|> =eps ) если (fa*fc< 0) b=c иначе a=c; всё если c=(a+b)/2 fa=ln(a-3) fb=ln(b-3) fc=ln(c-3) всё пока печать c печать fc иначе печать “на отрезке нет корня” все_если | #include " stdio. h" #include " math. h" #include " iostream. h" #include " iomanip. h" int main() { float fa, fb, fc, a, b, c, eps; cout< < " a="; cin> > a; cout< < " b="; cin> > b; fa=log(a-3); fb=log(b-3); if(fa*fb< 0) { cout< < " eps="; cin> > eps; c=(a+b)/2; fc=log(c-3); while(fabs(a-b)> =eps) { if(fa*fc< 0) b=c; else a=c; //вычисляется новая середина //отрезка c=(a+b)/2; //вычисляются значения //функций в новых точках fa=log(a-3); fb=log(b-3); fc=log(c-3); } cout< < " корень уравнения х*=" < < c< < endl; cout< < " значение f(x*)=" < < fc< < endl; } else cout< < " неверно введены концы" < < " отрезка" < < endl; return 1; } |
|
|
|
