Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Линейные алгоритмы).pdf

Для реализации метода половинного деления вычисляется значение функции в точке a (y=f(a)). Далее вычисляется координата середины интервала (a,b) по формуле x=(a+b)/2, где точка x - найденная координата середины (a,b). Таким образом, исходный интервал будет разбит на два равных интервала: (a,x) и (x,b), где корень уравнения принадлежит одному из них. Проверяется основное условие принадлежности корня одному из этих интервалов (a,x), которое представляет собой произведение значений функции на его границах f(a)*f(x)<0. На следующем шаге используется ветвление для выбора интервала в зависимости от истинности условия f(a)* f(x)<0. Если это условие истинно, то корень принадлежит интервалу (a,x), и правая граница b интервала (a,b) смещается в точку x (b=x). В противном случае левая граница a интервала (a,b) смещается в точку x.

Рисунок 14 - Блок-схема алгоритма решения уравнения методом половинного деления

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

Реализация алгоритма, использующего цикл с постусловием на языке Паскаль. В качестве примера была выбрана функция y=x² - 5. Заданная точность 0.01.

Program metod;

Var a, b, eps, x, y, z : real;

Begin

{Ввод границ интервала и погрешности}

WriteLn('Ведите левую и правую границы a, b и погрешность eps');

ReadLn(a, b, eps);

{Вычисление значения функции на левом интервале}

y := sqr(a) - 5;

{Цикл с постусловием}

repeat

x : = ( a + b)/2;

z := sqr(x) - 5;

if y*z < 0 then b := x

else

begin

a:=x;

y:=z

end;

until abs(b-a) <= eps;

{Конец цикла }

WriteLn('Корень уравнения', x:8:4);

end.

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

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

ЗАКЛЮЧЕНИЕ

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

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

Циклические алгоритмы в основном предназначены для решения практических задач, связанных с обработкой массивов или выполнением большого количества одинаковых операций. Например, написать программу умножения двух матриц n-го порядка без применения циклических конструкций практически невозможно. Часто на практике применяются вложенные друг в друга циклы. Но при написании программ с использованием вложенных циклов стоит обратить внимание на эффективность разработанных алгоритмов. Время работы алгоритма вычисляется как произведение количества выполненных алгоритмом операций на длительность выполнения каждой операции. Логично предположить, что два вложенных цикла увеличивают время работы программы примерно в n² раз, где n - количество команд в теле внутреннего цикла, а три вложенных цикла - в n³ раз. Поэтому на практике в вычислительных алгоритмах, как правило, лучше избегать конструкций, использующих много вложенных циклов.