Разработка алгоритма
Алгоритм– это точное предписание, определяющее вычислительный процесс, ведущий от исходных данных к искомому результату.
Алгоритм обладает следующими свойствами (они следуют из определения):
1. определенность (детерминированность)– каждая команда (или предписание) понятна исполнителю (человеку или компьютеру) и исключает неоднозначность исполнения;
2. результативность– реализация вычислительного процесса, предусмотренного алгоритмом, должна через определенное число шагов привести к результату или сообщению о невозможности его получения;
3. массовость– если алгоритм разработан для решения определенной задачи, он должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных;
4. дискретность– пошаговый характер процесса получения результата, состоящий в последовательном выполнении конечного числа заданных алгоритмом действий.
Различают следующие простейшие виды алгоритмов:
1. линейный, когда предписания алгоритма выполняются в той последовательности, в которой они представлены в алгоритме;
2. разветвляющийся, когда ход исполнения предписаний может меняться относительно их нахождения в алгоритме в зависимости от значений исходных или промежуточных данных;
3. циклический, когда предписания алгоритма выполняются многократно. В зависимости от характера повторений различают циклические алгоритмы с заданным и незаданным числом повторений (в этом случае такие алгоритмы называют итерационными).
Существуют следующие способы описания алгоритма: словесный, структурно-стилизованный, язык графических символов, операторный язык
Словесный способ
При словесном способе алгоритм задается в произвольном изложении на естественном языке. Недостаток этого способа состоит в том, что алгоритм строго не формализуем, многословен, допускает неоднозначности. Однако данный способ изложения алгоритма не требует специальных знаний и может применяться конечными пользователями. Именно на этом языке, как правило, сообщается неформальная постановка задачи на этапе формализации и он же может быть использован для представления результата первого этапа.
Как правило, именно этот способ используют при объяснении какой-либо задачи преподаватели, сопровождая его рисунками, схемами, графиками и т.д. Несмотря на указанные недостатки данного способа, он наиболее привычен и без него не обходится практически ни одна постановка задачи, поэтому примеров его использования можно найти множество в процессе обучения студента и в повседневной жизни.
Структурно-стилизованный способ
Структурно-стилизованный способ - это формализованное представление предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций. Данный способ представления алгоритма требует подготовки и специальных несложных знаний. Примером его может служить нотация Бэкуса – Наура, которая часто используется для описания структуры формализованных языков, например, языков программирования, в частности, Турбо-Паскаля. В этой нотации типовыми синтаксическими конструкциями являются продукции вида:
А::=В,
где А – определяемое продукцией понятие,
В – понятие или группа понятий, которые служат для раскрытия структуры понятия А;
знак «::=» имеет смысл «есть по определению».
Пример 1. Определим структуру понятия «оператор ввода» для Турбо-Паскаля. В соответствии с правилами этого языка, оператор ввода содержит название оператора (read) и операнд, показывающий, значения каких переменных вводятся; заканчивается оператор точкой с запятой. Таким образом, в состав оператора ввода входят две строковые постоянные величины – “read” и “;” и одна строковая переменная величина – операнд, который может включать произвольный по числу и составу набор имен переменных.
Для различения строковых постоянных и переменных условимся переменные заключать в угловые скобки, например, <операнд>, а постоянные – в кавычки, например, “read”. Тогда, очевидно, и само понятие «оператор ввода» является переменной величиной.
Запишем определения переменных с помощью упомянутой нотации:
<оператор ввода> ::= “read” <операнд> “;” .
В свою очередь понятие операнда также требует формального определения: это (в соответствии с правилами Турбо-Паскаля) заключенный в круглые скобки список имен переменных. Нотация Бэкуса-Наура позволяет записать это несколькими правилами:
<операнд> ::= “(“ <список имен переменных> “)”
<список имен переменных> ::= <имя> [“,” <список имен переменных>] .
Здесь квадратные скобки означают возможное отсутствие их содержимого в структуре определяемого понятия. Действительно, в конкретном операторе ввода может вводиться только одна переменная, тогда список вырождается в одно имя. Отметим также, что понятие списка имен переменных определено рекурсивно через себя же. Это часто используется при определении формальных структур.
Таким образом, получается набор правил, описывающих основные понятия языка. Следуя этим правилам, программист может составить правильную в синтаксическом смысле программу, т.е. эти правила могут рассматриваться как алгоритм.
Язык графических символов
Язык графических символов предполагает соотнесение каждому типу действий геометрической фигуры, представленной в виде блочного символа. Действия (блоки) соединяются линиями потока. Совокупность таких связанных блоков называется блок-схемой. Составление блок-схем регламентируется ГОСТ 19.003-80 и ГОСТ 19.002-80. Основными блоками, используемыми в блок-схемах, являются следующие:
Блок Название Характеристика
Тексты, которые записываются в блоки, не регламентируются: они должны отражать выполняемые действия и не быть ориентированными на тот или иной язык программирования. Если текст не помещается в блок, справа или слева к блоку приписывается комментарий, куда и помещается дополнительный текст.
Блоки: процесс, решение, модификация, предопределенный процесс, ввод-вывод, останов имеют единый вход (т.е. входящую линию потока), который располагается вверху блока. Например, для блока «процесс»:
Блоки: процесс, предопределенный процесс, ввод-вывод, пуск имеют единый выход (т.е. выходящую линию потока), который располагается внизу блока. Например, для блока «процесс»:
Блок решение имеет как минимум два выхода, которые подписываются словами ДА и НЕТ, например,
Блок модификация имеет выходы и входы (кроме входа в блок) со следующими значениями:
1. связь 1 – возврат к началу цикла. Имеет место, когда параметр цикла не превысил своего максимального значения;
2. связь 2 – вход в тело цикла;
3. связь 3 – выход из цикла, когда параметр цикла превысил свое максимальное значение.
Вход и выход в блок внутристраничного соединителя допускается в любом месте, например:
Вход в блок межстраничного соединителя допускается только сверху, а выход - только снизу, например:
Сами линии потока должны отвечать следующим требованиям:
1. должны быть параллельны внешним краям рамки листа;
2. допускается пересечение линий потока или изгиб под углом 90°, например:
3. для обозначения слияния место слияния обозначается точкой, например:
4. направление линий потока сверху вниз и слева направо считается основным. В противном случае, направление указывается стрелкой;
5. расстояние между параллельными линиями потока не менее 3 мм, между остальными символами схемы не менее 5 мм.