Понятие алгоритма и его свойства

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

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

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, может быть запрограммирован. Он содержит только типовые конструкции. Программу составим позднее.