ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

 

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

Свойства алгоритма:

1) определенность (точность предписаний и однозначность результата);

2) массовость (ориентирован на класс задач, например решение системы произвольного количества уравнений при любых исходных данных);

3) дискретность (деление процесса решения на этапы, понятные человеку и ЭВМ);

4) результативность (результат должен быть обязательно – даже если его нет, должно быть сообщение об этом).

Способы описания алгоритмов:

1) словесный (описание действий, которые должны привести к решению задачи, например построение треугольника по трем его сторонам);

2) математический (в виде формул, например формула для нахождения корней квадратного уравнения);

3) графический (схемы алгоритмов);

4) на языке программирования.

 

Первые два способа описания известны из школы и в данном курсе будут, в основном, использоваться совместно – для составления плана решения при математической постановке задачи. При составлении плана решения мы будем руководствоваться наиболее перспективным методом программирования – сверху вниз (от общей постановки задачи – к отдельным шагам ее решения). План решения учитывает:

1) особенности задачи, математические методы ее решения;

2) возможности языка программирования и его основные конструкции:

– ввод / вывод данных и вычисление по формулам;

– принятие решения (в зависимости от некоторого условия);

– повторение некоторых команд (групп команд);

– выделение общих частей алгоритма в одну общую часть и обращение к ней в случае необходимости.

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

Условие задачи. Последовательность чисел вводится в ЭВМ с клавиатуры; в конце ее вводится признак конца последовательности (например, " 0" или отрицательное число).

План будем разрабатывать по методу сверху вниз: постепенно уточняя отдельные шаги.

 

План 1 (укрупненный).

1. Ввести в ЭВМ первое число.

2. Пока нет признака конца последовательности

обработать число и

прочитать следующее число.

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

 

Пункты 1 и 3 очевидные и реализуются просто, а пункт 2 - надо уточнить, как обработать число. Так, число может быть:

1) простым;

2) составным.

Если число простое, то множитель у него один – оно само, если составное, то оно должно делиться на делитель без остатка. Значения делителя могут быть любые в пределах от 2 до ]число/2[. Здесь запись ] X [ означает целую часть от X.

Уточним пункт 2.

2.1. Предположить, что число – простое.

2.2. Изменять делитель от 2 до ]число/2[ и выполнять:

если число делится на делитель, то

а) вывести значение делителя и

б) изменить предположение, что число простое, на противоположное.

2.3. Если число простое, то

выдать сообщение 'Простое число'.

2.4. Прочитать следующее число.

 

Чтобы убедиться, что пункт 2 выполняется верно, проверим его вручную.

Пусть число равно 12.

Делители должны быть: 2, 3, 4 и 6.

Проверяя работу пунктов 2.1 – 2.3, получаем в результате:

2 3 4 6

 

Теперь план, в котором описаны пункты 1, 2.1 – 2.4 и 3, может быть запрограммирован. Он содержит только типовые конструкции. Программу составим позднее.

 

 

5. Графическое описание алгоритмов.
схемы алгоритмов

 

Схемы алгоритмов и программ входят в состав программной документации и оформляются в соответствии с ГОСТ 19.701 – 90 (ИСО 5807 – 85) " Схемы алгоритмов, программ, данных и систем" (взамен ГОСТ 19.002-80, 19.003-80). При этом используются условные графические обозначения (УГО), которые вписываются в прямоугольник (см. рис. 1.4). Стороны прямоугольника имеют следующие размеры:

a = 10, 15, 20 и т.д. через 5 мм, b = 1, 5а или b = 2a.

Наиболее часто используемые блоки приведены в табл. 1.

Схема алгоритма представляет собой совокупность УГО, соединенных линиями связи. В качестве примеров можно рассмотреть рис. 5, 6, 7. Все линии на схеме (контуры элементов и соединения) имеют одинаковую толщину. Схема начинается блоком " Начало" и заканчивается блоком " Конец". Для каждого элемента схемы должно выполняться условие: существует, по крайней мере, один путь от блока " Начало" до блока " Конец", проходящий через этот элемент.

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

Таблица 1