Алгоритмизация и программирование
Алгоpитм – это точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Название «алгоритм» произошло от латинской формы имени среднеазиатского математика аль-Хорезми — Algorithmi.
Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя характеризуют: среда, элементарные действия, система команд, отказы. Среда (или обстановка) — это «место обитания» исполнителя. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие. Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
В информатике универсальным исполнителем алгоритмов является компьютер.
2. Свойства алгоритмов
Можно выделить следующие основные свойства алгоритмов:
1) Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.
2) Дискретность (прерывность, раздельность) — т.е. алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов.
3) Определенность — т.е. каждое правило алгоритма должно быть четким, однозначным и не оставлять места для разночтений.
4) Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.
5) Массовость — означает, что алгоритм решения задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
3. Формы представления алгоритмов
Наиболее распространенными формами представления алгоритмов являются: словесная, графическая, псевдокоды и программная.
1) Словесная форма записи представляет собой описание последовательных этапов обработки данных на естественном языке (например, на русском).
Пример. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Алгоритм: 1) задать два числа; 2) если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3) определить большее из чисел; 4) заменить большее из чисел разностью большего и меньшего из чисел; 5) повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи за конечное число шагов.
Словесный способ не имеет широкого распространения, поскольку такие описания:
б) страдают многословностью записей;
в) допускают неоднозначность толкования отдельных предписаний.
2) Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. При графическом исполнении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного из действий. Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, называемая блочным символом. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
3) Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками.
С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются служебные слова и математическая символика, что приближает запись алгоритма к общепринятой математической записи. Служебные слова выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются для того, чтобы их можно было отличить от остального текста.
Пример. 1) задать два числа x и y; 2) ЕСЛИ x=y, ТО НОД=x и КОНЕЦ; 3) ЕСЛИ x>y, ТО x=x-y, ИНАЧЕ y=y-x; 4) ПЕРЕЙТИ в пункт 2.
4) Программная форма представляет собой тексты программ, написанных на различных языках программирования.
Ниже приведены графические обозначения на блок-схемах.
Структура “следование”
Полная развилка
Неполная развилка
Цикл с предусловие
Цикл с постусловием (цикл ДО)
Цикл с параметром
На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.
Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.