Алгоритм - точное предписание исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число шагов.

 

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

 

- Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

- Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола.

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

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

 

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

 

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

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

- Циклический алгоритм – алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.

Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.

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

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

 

Требования, предъявляемые к алгоритму:

 

Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

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

 

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

 

Алгоритмы записываются в виде:

 - словесных правил;

- псевдокода;

- блок схем;

- программ и т.д.;

 

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

 

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

 

ПРИМЕР : Найти наибольшего из трёх заданных чисел a, b, c.

 

 1. Сравнить a и b. Если a>b,то в качестве максимума t принять a, иначе (a<=b) в качестве максимума принять b (t=b).

 2. Сравнить t и c. Если t>c, то перейти к шагу 3. Иначе (t<c) принять в качестве максимума c (t=c).

 3. Принять t в качестве результата.

 

 

НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА :

 

- отсутствие наглядности;

- недостаточная точность.

ДОСТОИНСТВА : С его помощью можно описать любые алгоритмы, в том числе и вычислительные.

СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ ДЛЯ СЛОВЕСНОЙ ЗАПИСИ АЛГОРИТМОВ:

 1. Знак присваивания, слева от которого записывают ту переменную, которой присваивается значение, записанное справа от знака присваивания. Например, х:=х+1

 2. Для задания значения исходных данных используют указания: ВВЕСТИ

 3. Для запоминая промежуточных результата используют вспомогательные переменные.

 4. Для указания начала и конца алгоритма используют указания: НАЧАЛО и КОНЕЦ.

 5. Все шаги нумеруют.

Пример алгоритма построения треугольника по трём сторонам:

 1. Начало.

2. На произвольной прямой выбрать точку А. Раствором циркуля, равным а, отложить отрезок АВ=а.

 3. Из точки А провести окружность радиуса в.

 4. Из точки В провести окружность радиуса с.

 5. Конец.

 

ГРАФИЧЕСКИЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМА

 

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

Внутри блока записывается описание команд или условий.

Для указания последовательности выполнения блоков используют линии связи (линии соединения).

Последовательность блоков и линий образуют блок-схему алгоритма.

 

ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК- СХЕМ АЛГОРИТМА.

 

1. В блок-схеме можно использовать строго определённые типы блоков.

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

3. Для удобства блоки могут помечаться метками(буквами или цифрами).

4. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, подлежащих вводу/выводу.

5. Внутри блока действия для присваивания переменных значений используется знак присваивания.

Пример нахождения максимума трех чисел

 

 ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ ПРОГРАММ

 

Алгоритм, записанный на языке программирования называется программой.

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

Пример программы на языке программирования Паскаль:

PROGRAM RR;

VAR A,B,C, max: INTEGER;

BEGIN

WRITE(‘ ВВЕДИТЕ A, B, C');

READLN(A,B,C);

IF A>B THEN max:=A

ELSE max:=B;

IF C>max THEN max:=C;

WRITELN(max);

END.