Определение и свойства алгоритма

Определение, свойства и описание алгоритма

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

Подготовил преподаватель Бурдин А.Б.

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

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

Термин «алгоритм» – это измененное имя арабского ученого Аль-Хорезми, жившего в IX в. в Багдаде, который впервые описал набор четких правил для счета, превративших впоследствии арифметику в алгебру.

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

Аль-Хорезми

Но, мы не будем принимать в расчет трактовки понятия «алгоритм», как работа светофора или стиральной машины.

Мы будем говорить только об алгоритмах обработки информации .

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

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

• Любой алгоритм должен иметь только одну точку входа (начало) и одну точку выхода (окончание).

• Результативность – в конце процесса, предусмотренного алгоритмом, должны быть получены результаты или выдано сообщение о невозможности решения задачи .

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

• Дискретность – расчленение процесса , предусмотренного алгоритмом, на отдельные этапы (элементарные операции).

Существует несколько стандартных способов записи алгоритмов:

• Словесное (на естественном языке) ;
• Графическое описание (блок-схемы) ;
• Программное описание (текст программ) .

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

Недостатком словесного описания алгоритма является его неформальность

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

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

Блок-схема — это последовательность блоков, соединенных между собой стрелками.

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

=b I = 1 to N Цикл по счетчику, то есть с определенным (конечным) числом шагов. " width="640"

Начало или конец алгоритма (пуск–остановка).

Начало (Конец)

Ввод a,b

(Вывод S )

Ввод исходных данных или вывод результатов (ввод-вывод)

S=0

H=(b-a)/N

Выполнение операции или группы операций (процесс).

Выбор направления выпол-нения алгоритма в зависимости от условий. Вопрос должен допускать только два ответа: « да » или « нет ».

X=b

I = 1 to N

Цикл по счетчику, то есть с определенным (конечным) числом шагов.

Начало

Ввод стороны квадрата в переменную a

Линейная структура

Алгоритм нахождения периметра квадрата.

p:=4*а

Вывод р

Конец

Начало

Примеры построения блок-схем

Линейная структура

В полученном алгоритме нет никакого выбора : исполнитель выполняет алгоритм от начала до конца. При любой непредвиденной ситуации (никто не ответил) он ведет себя неадекватно – все равно говорит.

Поднять трубку телефона

Набрать номер

Поговорить

Положить трубку

Конец

Начало

Примеры построения блок-схем

ветвление

Поднять трубку

Набрать номер

Ответ-или?

ДА

НЕТ

поговорить

Положить трубку

Конец

б ДА НЕТ а ДА НЕТ а=б ДА Вывод Конец " width="640"

Начало

Ввод чисел в переменную а, б

аб

ДА

НЕТ

а

ДА

НЕТ

а=б

ДА

Вывод

Конец

Циклы (конструкция повторения) используются для организации повторного выполнения какой-либо операции или блока операций (инструкций).

Цикл состоит из двух частей : условия

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

Цикл с постусловием

Цикл с предусловием

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

Использованная литература

Л-7, стр. 198-205 (Таганов Л.С.)

Л-6, стр. 98-106 (Фиошин М.Е.)

Л-1, стр.135-141 (Семакин И.Г.)

Самостоятельная (внеаудиторная работа

Построение блок-схем алгоритмов.

Начало

Есть 220V ?

ДА

НЕТ

ВКЛ. работает?

ДА

НЕТ

Двигатель работает?

ДА

НЕТ

Неисправность найдена

неисправность НЕ найдена

Конец