Описание алгоритмов с помощью блок-схем

Описание алгоритмов с помощью блок-схем.

Для разработки структуры программы удобнее пользоваться записью алгоритма в видеблок-схемы(в англоязычной литературе используется терминflow-chart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рисунке

Начало/конец алгоритма

Передача управления

Ввод данных

Блок вычислений

Начало (заголовок) цикла

Конец цикла

Ветвление

Вывод данных

Составим алгоритм вычисления квадратного корня из произвольного положительного вещественного числахметодом Герона и запишем его на естественном языке, а также в виде блок-схемы. Метод основан на многократном применении формулы:

при

.

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

А теперь займёмся самым любимым занятием школьников всех времён и народов – решением квадратного уравнения:

.

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

возможны три случая:

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

,.

2. Если, то имеется единственный корень (точнее, двукратный корень):

.

3. Если, то вещественных корней нет.

Блок схема алгоритма приведена на рисунке:

Следует заметить, что приведённый алгоритм предназначен для решения узкого класса задач – квадратных уравнений с «хорошими» коэффициентами. Если допустить, что коэффициенты могут принимать произвольные вещественные значения, есть опасность, что при определённых значениях коэффициента (например,) возникает аварийная ситуация (деление на ноль). Качественный алгоритм и качественная программа должны быть устойчивыми, то есть при любых входных параметрах завершение работы программы должно быть нормальным, хотя, возможно, и сопровождаться предупреждающим сообщением о некорректности входных данных. Свойством устойчивости обладает алгоритм решения квадратного уравнения, приведённый на рисунке:

Разработанный программистом алгоритм должен давать правильный ответ. Проверка алгоритма может оказаться непростым делом. В простых случаях такая проверка может быть выполнена с помощью заполнениятрассировочной таблицы. Каждый столбец такой таблицы соответствует определённой переменной, а каждая строка – одному шагу алгоритма. Для заполнения таблицы необходимо шаг за шагом проследить выполнение алгоритма, записывая в таблицу текущие значения выбранных для трассировки переменных. Такой метод позволяет выявить логические ошибки, допущенные при составлении или записи алгоритма, и определить, верен ли окончательный ответ. Составим в качестве примера трассировочную таблицу для алгоритма Герона вычисления квадратного корня из числа 2.

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