Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 2
Алгоритм. Управляющие структуры
Решение задач с помощью компьютера включает в себя следующие основные этапы:
На одном из этапов разрабатывается алгоритм будущей программы. Алгоритмом назовём последовательность действий, ведущих от начального состояния исходных данных к некоторому результату либо к пояснению, по какой причине задача не может быть решена.
Основные свойства алгоритма:
понятность – исполнитель алгоритма должен знать, как его выполнять;
дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определённых) шагов, этапов;
определённость – каждый шаг алгоритма должен быть чётким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче;
результативность – алгоритм должен приводить к решению задачи за конечное число шагов;
массовость – алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные должны выбираться из некоторой области, которая называется областью применимости алгоритма.
На практике будем пользоваться формами представления алгоритмов:
Для написания алгоритма решения конкретной задачи будет достаточно знаний об организации работы трёх управляющих структур:
Алгоритмические структуры развилка и цикл допускают так называемую вложенность других структур. Таким образом, алгоритм решения поставленной задачи будет представлять собой либо линейную последовательность алгоритмических структур, либо последовательность, представляющую собой сочетание линейных и вложенных друг в друга алгоритмических структур.
Линейные вычислительные алгоритмы
Под линейным вычислительным алгоритмом будем понимать последовательность действий, состоящую из команд ввода, вывода и присваивания значений некоторым величинам. При описании таких алгоритмов используется только одна управляющая структура – следование.
Из определения алгоритма следует, что он должен начинаться с описания величин, которые используются при вычислениях. Такие величины подразделяют на переменные и константы. Переменная – именованная величина, значение которой может меняться в ходе вычислений. Имя переменной – это последовательность из букв латинского алфавита, десятичных цифр и символов подчёркивания, начинающаяся не с цифры. Такую последовательность называют идентификатором. Переменные бывают различных типов: целые, вещественные, символьные и др, поэтому при их описании будем указывать тип каждой переменной. Константа – это величина, представляющая фиксированное числовое, строковое или символьное значение. После описания переменных и констант (если они есть) следует описание действий, которые и составляют собственно алгоритм решения поставленной задачи.
Помимо операций ввода-вывода основным элементарным действием в алгоритме является операция присваивания значения переменной. Формат команды присваивания:
<имя переменной> = <выражение>
Знак «=» следует читать как «присвоить». Под командой присваивания понимается последовательность действий:
Отметим три основных свойства команды присваивания:
Пример построения линейного вычислительного алгоритма
Пример. Разработать алгоритм и составить по нему программу (разработать консольный проект) для вычисления значений функции z = . Область определения функции не учитывать.
Алгоритм
объявление вещ: х, у, z
ввод х , у
z=(sin3(x2)+cos(y))/(x2/3+5)
вывод х, у, z
Разветвляющиеся вычислительные процессы
Управляющая структура «развилка».
Логические операции и операции отношения
При описании разветвляющихся вычислительных алгоритмов кроме управляющей структуры «следование» применяется структура «развилка», или «если–то–иначе». Применяется такая структура в случае, когда нужно выбрать одну из имеющихся последовательностей действий в зависимости от выполнения или невыполнения некоторого условия. Форма записи структуры:
если <условие> то
действия1
иначе
действия2
все_если
Работа структуры организована по принципу: если <условие> истинно (выполняется), то выполняются действия1; в случае ложности (невыполнения) <условие> выполняются действия2.
Возможна вложенность структур «если–то–иначе» любой глубины, т.е. вместо действия1 и/или действия2 может быть записана еще одна структура «развилка» и т.д.
<условие>, записанное после слова если, представляет собой логическое выражение. Логические выражения применяются для определения истинности или ложности определенных ситуаций. Логическое выражение – это два операнда, соединенные либо логической операцией, либо операцией отношения. Под логической операцией понимается одна из операций, связывающих два операнда: И, ИЛИ или операция отрицания НЕ, записываемая перед операндом. Если <условие> – два условия, связанные логической операцией И, то <условие> будет истинным в случае одновременного исполнения этих двух условий. Если <условие> – два условия, связанные логической операцией ИЛИ, то <условие> будет истинным в случае, когда хотя бы одно из этих двух условий будет выполняться. Результаты выполнения логических операций приведены в табл.
|
Значение операнда 1 (оп1) |
Значение операнда 2 (оп2) |
Результат операций |
||
|
НЕ(оп1) |
(оп1) И (оп2) |
(оп1) ИЛИ (оп2) |
||
|
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
Под операцией отношения понимается одна из операций, связывающих два операнда: > (больше), >= (больше или равно), < (меньше), <= (меньше или равно), = (==) (равно), < > (!=) (не равно). Операция отношения позволяет сравнивать числовые выражения по их значениям.
Пример. Определить условие попадания точки с координатами (x;y) в указанную область D:
Напишем условие попадания точки с координатами (x;y) в указанную область. Очевидно, что данная область должна быть разбита на две непересекающиеся области D1 и D2, т.е. D=D1UD2. Таким образом, можно установить, что точка может попасть в D1 или в D2.
Опишем условие попадания точки (х;у) в области D1 и D2:
D1: x>=-4 И x<=4 И y>=0 И y<=2
D2: x>=0 И x<=2 И y>=-2 И y<=0
Таким образом, условие принадлежности точки с координатами (x;y) области D будет следующим:
(x>=-4 И x<=4 И y>=0 И y<=2) ИЛИ (x>=0 И x<=2 И y>=-2 И y<=0)
В Excel( x – A3 y – B3):
ИЛИ(И(A3>=-4;A3<=4;B3>=0;B3<=2);И(A3>=0;A3<=2;B3>=-2;B3<=0))
Программирование разветвляющихся вычислительных процессов
Пример 1. Разработать алгоритм и составить по нему программу для вычисления значений функции y = f(x). Необходимо учитывать область определения функции:
При разработке алгоритма будем рассматривать промежутки числовой оси слева направо. Обозначения в алгоритме: ФНЗ – функция не задана; ФНО – функция не определена.
Записывая основной алгоритм решения задачи, вместо вычислений каждой части функции для упрощения будем писать блок1, блок2 и блок3. Поставим в соответствие каждому блоку алгоритм вычисления конкретной функции с учетом её области определения. Последний этап разработки алгоритма решения исходной задачи – подстановка в основной алгоритм вместо блоков 1,2,3 соответствующих вычислительных алгоритмов.
Сделаем небольшое замечание относительно записи текста алгоритма. Рекомендуется записывать текст алгоритма «ступеньками», т.е. новый блок «если – иначе» нужно записывать с отступом относительно предыдущего блока «если – иначе» и т.д. Так же следует поступать и при записи текста программы, соответствующей алгоритму. Одной из причин этого является то, что структура алгоритма и программы хорошо просматривается, что может помочь при обнаружении синтаксических ошибок.
Основной алгоритм:
объявление переменных вещ: х, у
ввод х
если х<5
блок1
иначе
если x<7
«ФНЗ»
иначе
если x<12
блок2
иначе
если х<=15
«ФНЗ»
иначе
блок3
все_если
все_если
все_если
все_если
Рассмотрим вычисления в каждом из блоков 1, 2 и 3 отдельно.
Блок1. Требуется вычислить функцию . При вычислении учитываем, что подкоренное выражение должно быть больше или равно нулю и при этом знаменатель не должен равняться нулю. Таким образом, получаем:
если cos(х)>0
печать у
иначе
«ФНО»
все_если
Блок2. Требуется вычислить функцию . Здесь никаких ограничений на вычисления нет. Таким образом, получаем:
печать у
Блок3. Требуется вычислить функцию . При вычислении учитываем, что подкоренное выражение должно быть больше или равно. Таким образом, получаем:
если 25-х>=0
печать у
иначе
«ФНО»
все_если
В основной алгоритм вместо блоков 1,2,3 подставим алгоритмы вычисления соответствующих частей функции. В итоге получаем алгоритм решения исходной задачи.
Алгоритм
объявление переменных вещ: х, у
ввод х
если х<5
если cos(х)>0
печать х,у
иначе
«ФНО»
все_если
иначе
если x<7
«ФНЗ»
иначе
если x<12
печать х,у
иначе
если х<=15
«ФНЗ»
иначе
если 25-х>=0
печать х,у
иначе
«ФНО»
все_если
все_если
все_если
все_если
все_если
Примечание. В качестве тестового примера можно ввести следующие значения: х=16 и х=30.
ЕСЛИ(<условие>;<выр_ист_условия>;< выр_ложн_условия>)
Пример 2. Разработать алгоритм и составить по нему программу для вычисления значений функции z = f(x,y) в зависимости от попадания точки с координатами (х,у) в область D (область D выделена серым цветом):
В задаче требуется вычислить функцию, вид которой зависит от координат точки координатной плоскости. Если точка с координатами (х,у) попадает в область D, то вычисляется первая часть функции (в алгоритме – блок 1), в противном случае – вторая часть (блок 2). Процесс написания алгоритма разобьем на четыре этапа:
написание основного алгоритма решения задачи;
определение условия принадлежности точки области D. Так как одна и та же точка не может принадлежать двум непересекающимся областям одновременно, разобьем область D на две области: D1 (треугольник) и D2 (кольцо);
написание вспомогательных алгоритмов вычисления каждой части заданной функции;
написание полного алгоритма решения исходной задачи и соответствующей программы.
Обозначения в алгоритме: ФНО – функция не определена.
Рассмотрим отдельно этапы алгоритма.
объявление вещ: x, y, z
ввод х, у
если () или ()
блок 1
иначе
блок 2
все_если
Таким образом, уравнение прямой .
.
.
|
Блок 1 |
Блок 2 |
|
если х-у ≠ 0 z=1/(x-y) печать х, у,z иначе «ФНО» все_если |
если ху > 0 z=ln(xy) печать х, у,z иначе «ФНО» все_если |
Написать программу, соответствующую алгоритму:
Алгоритм
объявление переменных вещ: х, у, z
ввод х, у
если (((x>=-3 и x<=0) и (y>=0 и y<=2*x/3+2)) или
((x-2)*(x-2)+y*y<=4 и (x-2)*(x-2)+y*y>=1))
если х-у ≠ 0
z=1/(x-y)
печать х, у,z
иначе
«ФНО»
все_если
иначе
если х*у > 0
z=ln(x*y)
печать х, у,z
иначе
«ФНО»
все_если
все_если
Примечание. В качестве тестового примера можно ввести значения х=1, у=1 и х=3, у=5.
Циклические вычислительные процессы.
Алгоритмические циклические структуры предназначены для решения задач, которые подразумевают выполнение одного и того же набора действий определённое количество раз. Выделяют три типа циклов: с параметром, с предусловием и с постусловием. Каждый цикл имеет заголовок и тело цикла.
Типы циклов
Цикл с параметром
На псевдокоде цикл записывается следующим образом:
для i=<начальное_значение> до <конечное_значение> шаг <размер_шага>
<операторы_тела_цикла>
все_для i
Параметр цикла i показывает, сколько раз должны быть выполнены операторы тела цикла; <начальное_значение> – значение, с которого начинает изменяться параметр цикла; <конечное_значение> – значение, до которого изменяется параметр цикла; <размер_шага> – значение, показывающее, на сколько изменяется параметр цикла после выполнения всех операторов тела цикла.
Среди операторов тела цикла могут быть условные операторы, циклы и другие операторы.
Работа цикла с параметром организована по схеме: параметру присваивается <начальное_значение>, затем проверяется, больше или нет значение параметра значения <конечное_значение>. Если нет, то выполняются операторы тела цикла. В противном случае цикл завершает свою работу. После очередного выполнения операторов тела цикла значение параметра цикла изменяется на <размер_шага>. Затем опять проверяется, больше или нет значение параметра значения <конечное_значение>. Если нет, то выполняется тело цикла. В противном случае цикл завершает свою работу и т.д.
Цикл с предусловием
На псевдокоде цикл записывается следующим образом:
пока <условие>
<операторы_тела_цикла>
все_цикл
Определение <условие> аналогично его определению в разделе «Разветвляющиеся вычислительные процессы». Тело цикла выполняется до тех пор, пока <условие> истинно. Когда условие станет ложным, выполняется строка, следующая за циклом.
Работа цикла с предусловием:
Используя оператор цикла с предусловием, необходимо следить за тем, чтобы операторы тела цикла воздействовали на условие, либо за тем, чтобы оно ещё каким-то образом изменялось во время вычислений в теле цикла. Для этого часто используют унарные операции ++ или – для изменения параметров, входящих в <условие>. Только при изменении условия можно избежать зацикливания.
Цикл с постусловием
На псевдокоде цикл записывается следующим образом:
цикл
<операторы_тела_цикла>
пока <условие>
Правила работы цикла с постусловием:
В противоположность циклам с параметром и предусловием, сначала проверяющим условия, в цикле с постусловием условие окончания работы этого цикла проверяется после выполнения операторов тела цикла. Данный цикл всегда выполняется, по крайней мере, один раз.
Пример. Вывести на экран таблицу из n значений функции .
Алгоритм решения задачи строится следующим образом. Из условий задачи видно, что значения x изменяются от a до b. Шаг h, на который изменяются значения x, вычисляется по формуле . Формула для изменения значений x выглядит следующим образом:
Т
Такие формулы называют рекурсивными, поскольку новое значение переменной зависит от предыдущего значения и вычисляется через него.
Каждый раз при получении нового значения x будем вычислять значение y по заданной формуле. Таким образом, необходимо повторить одну и ту же последовательность действий известное (это важно) число раз (в данной задаче количество повторений равно n). Для решения такого типа задач как раз и используются циклические вычислительные процессы. В нашей задаче будет использован цикл с параметром.
Алгоритм
объявление вещ: а,b,x,y,h, цел: n,i
// ввод концов отрезка
ввод a
ввод b
// задаем количество вычисляемых значений функции
ввод n
// вычисление шага
h=(b-a)/n
// задаем начальное значение аргумента
x=a
// цикл для построения таблицы значений
для i=1 до n шаг 1
// вычисляется значение функции
y=|cos(x)|+|x-1|
печать x,y
// вычисляем новое значение аргумента
x=x+h
всё_для i
// цикл для построения таблицы значений
для x=a до b шаг h
// вычисляется значение функции
y=|cos(x)|+|x-1|
печать x,y
всё_для x
Вычисление последовательностей
Циклические структуры используются для вычисления элементов рекуррентных последовательностей, обработки массивов, а также решения задач, которые предполагают использование численных методов.
Примеры вычисления последовательностей
Из данного определения видно, что для задания последовательности нужно знать закон образования n-го члена последовательности, т.е. функцию, которая ставит натуральному числу n в соответствие некоторое значение f(n): xn=f(n).
При вычислении возрастающих последовательностей должно быть задано условие, ограничивающее вычисление элементов такой последовательности.
Формула n-го члена рекуррентной последовательности (рекуррентная формула) аn=F(an-k ,an-k+1,аn-к+2,…,аn-1), где число k называется глубиной рекурсии и определяет количество предшествующих элементов, необходимых для вычисления аn. Смысл глубины рекурсии в том, что она максимальному количеству переменных, необходимых для вычисления элементов последовательности.
Примеры задач с использованием
рекуррентных последовательностей
Вычислить n-й элемент последовательности.
Вычислить сумму или произведение первых n элементов последовательности.
Найти количество элементов на данном отрезке последовательности, удовлетворяющих определенному условию.
Найти номер первого элемента последовательности, удовлетворя-ющего определённому условию.
Пример 1. Вычислить n-й элемент арифметической прогрессии а1=1, а2=3, а3=5 и т.д.
Написание алгоритма решения задачи будет состоять из двух шагов.
Выведем рекуррентную формулу. Так как разность прогрессии равна 2, то рекуррентная формула будет следующей: . Читается формула так: при i=1 ai=1; при i≥2 ai=ai-1+2, т.е. каждый последующий элемент равен сумме предыдущего и 2.
Определим глубину рекурсии. Поскольку каждый следующий элемент вычисляется только через один предыдущий, то глубина рекурсии равна 1. Следовательно, для вычисления элементов последовательности нужны две переменные. Однако в этом случае можно обойтись одной переменной. Для определения значения последующего элемента последовательности будем использовать рекурсивную формулу
Алгоритм
объявление цел: а,n,i
ввод n
//текущий элемент последовательности и его текущий номер
а=1,i=1
//вычисляем элементы последовательности
для i=2 до n шаг 1
а=а+2
всё_для i
печать а
Пример 2. Вывести на печать первые n (n≥3) чисел Фибоначчи. Распечатать все элементы и подсчитать, сколько среди них четных чисел. Числа Фибоначчи образуются по закону:
а1=1, а2=1, … , аi=ai-1+ai-2, ….
Написание алгоритма решения задачи будет состоять из двух шагов.
Рекуррентная формула задается в определении чисел Фибоначчи: .
Глубина рекурсии равна 2, поэтому для вычисления чисел Фибоначчи нужны три переменные.
Алгоритм
объявление цел: i, n, a1, a2, а3, s
//ввод количества вычисляемых элементов
ввод n
//инициализация
а1=1, а2=1, s=0
печать а1
печать а2
//цикл для вычисления элементов и количества четных элементов
для i=3 до n шаг 1
a3= a2+ a1
печать а3
если (остаток от деления а3 на 2)=0 //условие четности значения переменной а3
s=s+1
все_если
а1= a2
а2 = а3
всё_для i
печать s
Примечание. В алгоритме использована рекурсивная формула
Последовательности в примерах 1 и 2 являются возрастающими, поэтому вычисление элементов ограничивается заданием их количества.
Пример 3. Для заданных действительного x и целого n вычислить сумму .
Написание алгоритма решения задачи будет состоять из двух шагов.
Формула для вычисления суммы:
.
Здесь i обозначает номер текущего элемента последовательности, n – количество элементов последовательности, сумму которых нужно вычислить.
Глубина рекурсии в данном случае не определяется, так как данная формула не является рекуррентной.
Алгоритм
Объявление цел: i, n; вещ: х, s, а
//ввод количества элементов
ввод n
ввод x
//начальное значение номера элемента
i=1
//начальное значение элемента
а=sin(x)/x
//начальное значение суммы элементов
s=a
//цикл для вычисления элементов и их суммы
для i=2 до n шаг 1
a= (-1)i-1sini(x)/xi
s=s+a
всё_для i
печать s
Написать программу, соответствующую алгоритму
Примечание. В алгоритме использована рекурсивная формула
Пример 4. Для заданного вещественного х и малой величины eps вычислить сумму ряда .
Написание алгоритма решения задачи будет состоять из двух шагов.
Рекуррентная формула выводится из предположения, что слагаемые ряда являются членами бесконечно убывающей геометрической прогрессии. Пусть . Таким образом, рекуррентная формула выглядит следующим образом:
,
где . Значение а0 либо вычисляется по формуле ряда (записывается после знака суммы) – вместо параметра подставить его начальное значение, либо из записи самого ряда – первое слагаемое ряда. Формула для берется либо из формулы ряда , либо ее необходимо определить по изменению слагаемых ряда. Для нахождения формулы подставим в формулу i-1 вместо i: .
Для вычисления q необходимо знать, что есть факториал числа. Факториалом числа i называют произведение последовательных натуральных чисел от 1 до i включительно, т.е. i! = 1·2·3·…·(i-1)·i. Следовательно, (2i-1)! = 1·2·3·…·(2i-1), а (2i+1)! = 1·2·3·…·(2i-1)·2i·(2i+1). Вычислим . Получим рекуррентную формулу
.
При записи этой формулы наиболее частой ошибкой является следующая
запись этой формулы:
.
Эта формула не будет являться рекуррентной, так как в ней нет зависимости последующего элемента последовательности от предыдущего, следовательно, нет возможности применить стандартный алгоритм вычисления элементов и суммы этих элементов (описание см. ниже).
Глубина рекурсии равна 1, т.е. для вычисления элементов последовательности требуются две переменные. Как и в примере 1, обойдемся одной переменной.
Примечание. При вычислении суммы ряда решающую роль играет величина eps. Она задаётся для того, чтобы ограничивать количество вычисляемых элементов последовательности, добавляемых в сумму. При вычислении каждого элемента последовательности его модуль сравнивается с eps. Если он больше eps, то вычисления продолжаются, в противном случае вычисление элементов последовательности и добавление их в искомую сумму прекращается. Такой процесс называется вычислением суммы ряда с точностью eps. В качестве значения переменной eps можно взять 0,001 или 0,00001 и т.п.
Алгоритм
Объявление вещ: х, eps ,S, a, цел: i
ввод х, eps
//начальное значение номера элемента последовательности
i=0
//начальное значение элемента последовательности
a=1
//начальное значение суммы элементов последовательности
s=a
//цикл для вычисления элементов и суммы последовательности
покa |a|>=eps
//увеличиваем номер элемента
i=i+1
//вычисляем новый элемент
a=a*(-x)/(2*i*(2*i+1))
//добавляем его в сумму
s=s+a
все_цикл
печать s
Пример 5. Найти наименьший номер члена последовательности, для которого выполняется условие . Вывести на экран номер и все элементы , где . Последовательность задается формулой .
Написание алгоритма решения задачи будет состоять из двух шагов.
Формула для вычисления элементов последовательности:
,
где i – номер текущего элемента последовательности.
Глубина рекурсии в данном случае равна 1, т.е. для вычисления элементов последовательности нужны две переменные.
Алгоритм
Объявление цел: i; вещ: аt, ap, eps
ввод eps
//номер элемента равен 1
i=1
// текущий элемент
аt=0.01
печать at
//номер элемента увеличивается на 1
i++
// новый элемент
ap=ln2(at)+1
печать ap
// цикл для вычисления элементов последовательности
пока |at-ap|>=eps
//номер элемента увеличивается на 1
i++
//последующий элемент становится текущим
at=ap
//вычисляется последующий элемент
ap=ln2(at)+1
печать ap
всё_цикл
печать i
Структура алгоритмов вычисления
рекуррентных последовательностей
Как видно из решения задач, приведенные алгоритмы имеют общую структуру. Алгоритмы решения задач на нахождение элементов и/или суммы элементов последовательности можно записать в следующем виде:
задать начальное значение номера элемента i = i0
задать начальное значение элемента a = a0
задать начальное значение суммы элементов s = a0
цикл <условие_продолжения_вычислений>
i =i+1
a = f(a,a0)
печать a (если нужно)
s = s+a (если нужно)
все_цикл
печать s (если нужно)
Здесь f(a,a0) – это функция, описывающая зависимость последующего элемента последовательности от предыдущего.
Массивы
Математическим понятием, которое привело к появлению в языках программирования понятия «массив», являются матрица и ее частный случай – вектор. Таким образом, массив – совокупность элементов любого допустимого в языке программирования одного типа данных. В Excel массивом понимают совокупность ячеек, для которых определена некоторая формула. При этом совокупность ячеек представляет непрерывный диапазон. Основным отличием массива является невозможность изменения формулы для какой-либо части массива. Для того чтобы обозначить массив необходимо выполнить:
Для объявления массива необходимо указать:
Каждый массив может разбиваться на несколько подмассивов, которые так же можно разбивать и т.д. Количество таких разбиений, или измерений, называется размерностью массива. Это понятие необходимо отличать от понятия размера массива, определяемого как количество его элементов. При объявлении массива в каждом измерении указывается количество элементов этого измерения.
Нахождение приближенного значения корня нелинейного уравнения
Нелинейные уравнения – это уравнения, в которые переменная входит в степени больше чем 1. Решить уравнение – значит, найти его корень. Корнем называется такое значение переменной, при подстановке которого в уравнение вместо переменной уравнение превращается в верное равенство.
1. Методы нахождения корней уравнения f(x)=0
на отрезке [a;b] с заданной точностью eps
Постановка задачи заключается в следующем. Дан отрезок [a;b], на котором находится корень уравнения f(x)=0. Найти с заданной точностью eps корень этого уравнения. Рассмотрим три метода нахождения корней нелинейных уравнений.
1.1. Метод дихотомии (половинного деления)
Данный метод основывается на утверждении, что если на отрезке [a;b] содержится корень уравнения f(x)=0, то значения 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 иначе печать “на отрезке нет корня” все_если |
Метод хорд
Метод основывается на утверждении, что если на отрезке [a;b] содержится корень уравнения, то значения f(a) и f(b) имеют разные знаки, т.е. f(a)·f(b)<0.
Схема метода аналогична предыдущему. Разница заключается в поиске значения точки c. Для этого в методе хорд используется уравнение хорды – прямой, проходящей через две точки некоторой кривой. Возьмём т.А(a;f(a)) и т.B(b;f(b)) на кривой y=f(x). Уравнение прямой проходящей через эти точки . Пусть первая координата т.С(с;0) – принадлежит [a;b] и лежащая на оси Ох. Подставим координаты точки C в полученное уравнение. В итоге получаем уравнение для получения значений точек сi при вычислении корня исходного уравнения:
.
Вычисляется точка c. Если |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 и т.д. Графически этот метод изображен на рис.15.
Опишем алгоритм и соответствующую программу для нахождения корней уравнения 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=а-(b-a)*fa/ (fb-fa) fc=ln(c-3) пока (|f(c)|>=eps ) если (fa*fc<0) b=c иначе a=c; всё если c=а-(b-a)*fa/ (fb-fa) fa=ln(a-3) fb=ln(b-3) fc=ln(c-3) всё пока печать c печать fc иначе печать “на отрезке нет корня” все_если |
Метод касательных (Ньютона)
Метод основывается на утверждении, что если на отрезке [a;b] содержится корень уравнения, то значения f(a) и f(b) имеют разные знаки, т.е. f(a)·f(b)<0. Точность вычислений зависит от выбора точки, с которой начинаются вычисления. Выбор начальной точки x0 вычислений определяет условие . Схема метода аналогична предыдущим. Разница заключается в поиске значения точки c. Для этого в методе касательных используется уравнение касательной к графику функции: . Пусть первая координата т.С(сi;0) – принадлежит [a;b] и расположена на оси Ох. Подставим координаты точки C в полученное уравнение. В итоге получаем уравнение для получения значений точек сi при вычислении корня исходного уравнения:
.
Если |ci-ci-1|>=eps, то вычисления продолжаются. Если |ci-ci-1|<eps, то вычисления можно прекратить, а за значение корня взять одно из этих значений, т.е. корень уравнения вычислен с заданной точность eps. Если нет, то вычисляется новое значение сi и т.д. Графически этот метод изображен на рис.16.
Опишем алгоритм и соответствующую программу для нахождения корней уравнения ln(x-3)=0 на отрезке [3.5;5] с помощью этого метода:
|
Алгоритм |
|
объявление вещ: f_2p, fa, fb, a, b, c, c1, eps ввод а ввод b fa=ln(a-3) fb=ln(b-3) если fa*fb<0 ввод eps f_2p=-1/(a-3)2 если fa*f_2p>0 c1=a иначе c1=b все_если c=c1-ln(c1-3)/(1/(c1-3)) пока (|c-c1|>=eps ) c1=c c=c1-ln(c1-3)/(1/(c1-3)) всё_цикл печать c печать ln(c-3) иначе печать “на отрезке нет корня” все_если |
Нахождение приближенного значения определенного интеграла
Нахождение приближенного значения определенного интеграла
с заданной точностью
Существует несколько методов приближенного вычисления определенных интегралов . Численно определенный интеграл равен площади фигуры, ограниченной кривой y=f(x), осью Ox и прямыми x=a и x=b. Такую фигуру называют криволинейной трапецией (рис.17). Рассмотрим методы левых, правых и центральных прямоугольников, а также метод трапеций и метод Симпсона. Суть их в том, что отрезок [a;b] разбивается на n равных частей и находится длина каждого частичного отрезка по формуле . Следовательно, криво-линейная трапеция разбивается на множество элементарных трапеций, и её площадь считается как сумма площадей элементарных трапеций. Площадь же элементарной трапеции приблизительно равна площади элементарного прямоугольника или трапеции и вычисляется по соответствующей формуле.
Для формул прямоугольников площадь каждой элементарной трапеции заменяется площадью прямоугольника и вычисляется как произведение значения функции, аргументом которой будет левая или правая граница каждого частичного отрезка (для формул левых и правых прямоугольников соответственно) или центр каждого частичного отрезка (для формулы центральных прямоугольников) на шаг разбиения h.
В методе трапеций площадь каждой элементарной криволинейной трапеции находится по формуле площади обычной трапеции, известной из школьного курса математики.
В методе Симпсона берутся три ближайшие точки разбиения и по ним строится парабола, график которой приближенно описывает график функции на двух близлежащих частичных отрезках. Ищутся приближенно площади криволинейных трапеций на всех участках и складываются. Это и будет приближенное вычисление определенного интеграла по методу Симпсона. Для нахождения приближенного значения интеграла по методу Симпсона необходимо, чтобы количество частичных отрезков было четным.
В программировании для вычисления интеграла используется цикл, который продолжает свою работу до тех пор, пока ближайшие значения интегралов различаются не более чем на заданную точность eps.
Математические формулы для всех описанных методов приведены в табл.1.
|
Таблица 1 |
|
|
Название метода |
Формула |
|
Метод левых прямоугольников |
|
|
Метод центральных прямоугольников |
|
|
Метод правых прямоугольников |
|
|
Метод трапеций |
|
|
Метод Симпсона |
Общая схема вычисления интегралов с точностью eps:
ввод a
ввод b
ввод количества разбиений n
вычислить шаг h
ввод eps
вычисление интеграла i0
I1=0
пока |I0-I1|>=eps
I1=I0
увеличение количества разбиений n
вычислить новый шаг h
вычисление интеграла I0
все_пока
печать I0
Далее приведены примеры алгоритмов и соответствующих программ для вычисления приближенного значения определенного интеграла.
Вычислить интеграл с точностью eps методом левых прямоугольников:
|
Алгоритм |
|
объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n; ввод a,b,n,eps h=(b-a)/n x=a I0=ln(a-3) для i=1 до n-1 шаг 1 x=x+h I0=I0+ln(x-3) все_для i I0=I0*h I1=0 пока |I1-I0|>=eps I1=I0 n=2*n h=(b-a)/n x=a I0=ln(a-3) для i=1 до n-1 шаг 1 x=x+h I0=I0+ln(x-3) все_для i I0=I0*h все_цикл печать I0 |
Вычислить интеграл с точностью eps методом центральных прямоугольников:
|
Алгоритм |
|
объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n; ввод a,b,n,eps; h=(b-a)/n; x=a+h/2; I0=ln(a-3); для i=1 до n-1 шаг 1 x=x+h; I0=I0+ln(x-3); все_для i I0=I0*h I1=0 пока |I1-I0|>=eps I1=I0 n=2*n h=(b-a)/n x=a+h/2 I0=ln(a-3) для i=1 до n-1 шаг 1 x=x+h I0=I0+ln(x-3) все_для i I0=I0*h все_цикл печать I0 |
Вычислить интеграл с точностью eps методом правых прямоугольников:
|
Алгоритм |
|
объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n; ввод a,b,n,eps h=(b-a)/n x=a+h I0=ln(a-3) для i=2 до n шаг 1 x=x+h I0=I0+ln(x-3); все_для i I0=I0*h I1=0 пока |I1-I0|>=eps I1=I0 n=2*n h=(b-a)/n x=a+h I0=ln(a-3) для i=2 до n шаг 1 x=x+h I0=I0+ln(x-3) все_для i I0=I0*h; все_цикл печать I0 |
Вычислить интеграл с точностью eps методом трапеций
|
Алгоритм |
|
объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n; ввод a,b,n,eps h=(b-a)/n x=a I0=0 для i=1 до n-1 шаг 1 x=x+h I0=I0+ln(x-3) все_для i I0= h*((log(a-3)+log(b-3))/2+I0) I1=0 пока |I1-I0|>=eps I1=I0 n=2*n h=(b-a)/n x=a I0=0 для i=1 до n шаг 1 x=x+h I0=I0+ln(x-3) все_для i I0= h*( (log(a-3)+log(b-3))/2+I0) все_цикл печать I0 |
Вычислить интеграл с точностью eps методом Симпсона:
|
Алгоритм |
|
объявление вещ: a,b,h,eps,I0,I1,x,f2i_1,f2i; цел: i, n ввод a,b,n,eps; //если n – нечетное, то умножаем на 2 если n%2= =1 n=n*2 h=(b-a)/n f2i_1=0; //для «нечетных» точек f2i=0; //для «четных» точек x=a+h; для i=1 до (n-1)/2 шаг 1 f2i_1=f2i_1+log(x-3); x=x+h; f2i=f2i+log(x-3); x=x+h; все_для i f2i_1=f2i_1+log(x-3); I0=h*(log(a-3)+log(b-3)+4*f2i_1 +2*f2i)/3; I1=0 пока |I1-I0|>=eps I1=I0 n=2*n h=(b-a)/n x=a I0=0 для i=1 до (n-1)/2 шаг 1 f2i_1=f2i_1+log(x-3); x=x+h; f2i=f2i+log(x-3); x=x+h; все_для i f2i_1=f2i_1+log(x-3); I0=h*(log(a-3)+log(b-3)+4*f2i_1+ 2*f2i)/3; все_цикл печать I0 |
Примечание. Если сравнить результаты вычислений интегралов с точным значением определенного интеграла, то можно сделать вывод о том, что наиболее точным методом является метод Симпсона.
5
7
12
15
●
●
●
●
EMBED Equation.3
ФНЗ
EMBED Equation.3
НЗ
Криволинейная трапеция
EMBED Equation.3
2
2
s= s + 1
Следующее значение переменной
Предыдущее значение переменной
Следующее значение переменной
4
-2
-3
Предыдущее значение переменной
Следующее значение переменной
x = x+h
a= a + 2
Предыдущее значение переменной
a
b
y=f(x)
c
c
b
a
C(c;0)
B(b;f(b))
A(a;f(a))
a
b
y=f(x)
c1
c2
y=f(x)
c1
c2
Предыдущее значение переменной
Следующее значение переменной
s= s + a
y=f(x)
b
a
2
4
2
4
-2
D
y
x
Рис.17
Рис.16
Рис.15
Рис.14