Основы алгоритмизации

ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

Для решения задачи на компьютере необходимо иметь исходные данные и программу, реализующую алгоритм решения задачи.

Алгоритм – это конечная последовательность однозначных предписаний, исполнение которых позволяет с помощью конечного числа шагов получить решение задачи, определяемое исходными данными.

Термин «алгоритм» происходит от латинизации имени великого арабского математика Муххамеда аль-Хорезми, который еще в IX в. разработал правила выполнения арифметических операций для многозначных чисел. Понятие «алгоритм использовалось математиками для описания последовательности решения математических задач (алгоритм решения квадратного уравнения, алгоритм сложения дробей и др.).

Любые алгоритмы обладают следующими основными свойствами.

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

Определенность (детерминированность). Каждое правило алгоритма должно быть четким и однозначным. Значения величин, получаемые в какой-либо момент времени, однозначно определяются значениями величин, полученными в предыдущие моменты времени.

Результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.

Массовость – алгоритм решения разрабатывается в общем виде, так чтобы его можно было применить для всего класса задач, различающихся исходными данными.

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

• выделение законченных частей вычислительного процесса;

• формальная запись каждого из них;

• назначение определенного порядка выполнения выделенных частей;

• проверки правильности выбранного алгоритма.

СПОСОБЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ

Существует несколько способов представления алгоритмов.

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

Задача	Описание алгоритма
Вычислить значение С, если оно определяется как: А-В, если А≥В А+В, если А<В	Исходные данные А и В ввести в память компьютера, проверить выполнение неравенства А>В. Если оно выполняется, то вычислить А-В. Результат обозначить как С и вывести его; в противном случае вычислить А+В, результат обозначить С и вывести его.

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

Этап 1. Ввести А,В

Этап 2. Если А>В, то перейти к этапу 4, иначе – к этапу 3.

Этап 3. С=А-В, перейти к этапу 5.

Этап 4. С=А+В.

Этап 5. Принять значение С за результат.

Этап 6. Вывести С.

Этот способ более компактен, но не является строго формальным.

Табличный способ. Алгоритм задается в виде таблиц и расчетных формул. Этот способ наиболее часто используется в экономических расчетах. Исходные данные и результаты вносятся в заголовки столбцов таблицы. Например:

Фамилия	Количество отработанных дней (К)	Тариф (Т)	Заработная плата (З=К х Т)
Буров	22	5,20
Котов	15	3,80

Операторный (язык операторных систем). При использовании этого способа вычислительный процесс изображается в виде последовательности символов (операторов). Они обозначают группы стандартных или нестандартных операций, реализующих законченную процедуру с указанием связи между отдельными операторами. Порядок выполнения – слева направо, стрелки указывают переход от логического оператора (проверки), знак «точка с запятой» (;) обозначает конец варианта и показывает, что между соответствующими операторами нет связи.

Этот способ значительно упрощает составление программы для компьютера, при этом вместо операторов подставляются соответствующие команды. Недостатком данного способа является его малая наглядность.

Графический (способ блок-схем). Каждый этап отображается в виде геометрических фигур – «блоков», форма которых зависит от выполняемой операции. Блок может иметь имя (метку). Линия соединения блоков показывает направление процесса обработки данных. Каждое направление называется ветвью. Перечень блоков, их наименование, функции, формы, размеры, взаиморасположение определяются ГОСТом 19.003 – 80.

Виды блоков алгоритмов

№ п/п	Наименование блока	Графическое представление бока	Функция блока
1	Линейный процесс		Выполнение операций, в результате которых изменяются значение, форма представления или расположение данных
2	Проверка условия, решение		Выбор направления выполнения алгоритма в зависимости от некоторых переменных уcловий
3	Ввод - вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов (вывод)
4	Начало-конец алгоритма (пуск-остановка)		Начало, конец процесса обработки данных
5	Преопределенный (заранее описанный) процесс, модуль		Использование ранее созданных или отдельно описанных алгоритмов (модулей)
6	Соединитель		Указание связи между прерванными линиями потока обработки данных
7	Комментарий		Связь между элементом схемы и появнением

ТИПЫ АЛГОРИТМОВ

Различают три основные структуры в построении алгоритмов: линейную, разветвленную и циклическую. Все реальные алгоритмы строятся на основе сочетания этих основных типов.

АЛГОРИТМ ЛИНЕЙНОЙ СТРУКТУРЫ

Алгоритм линейной структуры состоит из последовательности действий, формирующих одну ветвь вычислений. Примером линейного алгоритма может быть алгоритм расчета Y по формуле Y=*XХ

РАЗВЕТВЛЯЮЩИЙСЯ ОРГАНИЗМ

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

ЦИКЛИЧЕСКИЙ АЛГОРИТМ

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

параметр цикла – величина, с изменением значения которой связано многократное выполнение цикла;

начальное и конечное значения параметров цикла;

шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении.

Цикл организуют по определенным правилам. Циклический алгоритм из подготовки цикла, тела цикла, условия продолжения цикла.

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

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

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

5