 |
|
Алгоритм и его свойства
Алгоритм – это последовательность предписаний (команд), точное выполнение которых приводит к решению поставленной задачи.
Правильно построенные алгоритмы должны обладать следующими свойствами:
дискретность - алгоритм разбит на отдельные элементарные этапы (шаги), возможность выполнения которых не вызывает сомнений,
однозначность - команды, входящие в алгоритм, должны быть точными и понятными, порядок их выполнения должен быть единственно возможным, любая неопределенность или двусмысленность недопустима,
детерминированность - повтор результатов при повторе исходных данных,
результативность - алгоритм должен приводить к результату за конечное число шагов,
массовость - алгоритм должен быть пригоден для решения всех задач данного класса.
Схемы алгоритмов
Любой алгоритм можно представить или записать тремя способами:
· словесным (вербальным) - с использованием слов и предложений,
· табличным (аналитическим) - с помощью формул и таблиц,
· графическим - с помощью рисунков, геометрических фигур и символов.
Самым наглядным из них является графический способ – представление алгоритма схемой.
Схема алгоритма – это графическое изображение его структуры, отдельных составных частей и взаимосвязей между ними.
Схема алгоритма представляет собой совокупность специальных символов (блоков), соединенных между собой стрелками, которые указывают последовательность выполнения алгоритма. Внутри каждого блока может быть записан его номер и краткое содержание исполняемых им функций (операций).
Правила выполнения схем алгоритмов устанавливает Единая система программной документации (ЕСПД), в которую входят:
ГОСТ 19002-80 “Схемы алгоритмов и программ. Правила выполнения”
ГОСТ 19003-80 “Схемы алгоритмов и программ. Обозначения условные графические”
Перечень, наименование, обозначение и размеры наиболее употребляемых символов и отображаемых ими функций:
процесс - выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных,
решение - выбор направления выполнения программы или алгоритма в зависимости от некоторых переменных условий,
модификация – выполнение операций, меняющих команды или группу команд, изменяющих программу,
предопределенный процесс – использование ранее созданных или отдельно описанных алгоритмов или программ,
данные - преобразование данных в форму, пригодную для обработки (ввод) или регистрации результатов обработки (вывод),
дисплей - вывод данных на дисплей (монитор).
терминатор - начало, конец, прерывание процесса обработки данных при выполнении программы,
линии потока - линии, связывающие символы схемы: линии,
идущие справа налево или снизу вверх, должны иметь стрелки.
комментарий- добавление описательных комментариев или пояснительных записей
Пример записи
алгоритма:
Для построения удобных в работе схем алгоритмов необходимо руководствоваться следующими правилами:
ü каждая схема должна иметь точку начала и точку конца,
ü от точки начала блоки располагаются сверху вниз и слева направо,
ü направление линий потока сверху вниз и слева направо принимается за основное и, если линия потока не имеет излома, то стрелками ее можно не обозначать,
ü расстояние между параллельными линиями потока должно быть не менее 3 мм, между остальными линями схемы – не менее 5 мм,
ü количество входящих в блок линий потока не ограничивается, но выходить из него может только одна линия (исключение – блок решения, из которого всегда выходят две линии),
ü запись в блоках должна быть словесной или математической, а не в виде операторов конкретного алгоритмического языка: нужно показать, что делается в блоке, а не как это делается,
ü записи внутри блоков должны быть расположены так, чтобы их можно было читать слева направо и сверху вниз независимо от направления линий потока,
ü схема должна читаться без дополнительных пояснений автора,
ü используемые в некотором блоке переменные должны получать конкретные значения в предыдущих или в том же блоке,
ü входные и выходные блоки подпрограмм должны содержать перечень соответственно входных и выходных параметров,
ü блоки можно объединять в более крупные пунктирными линиями, при этом необходимо описать назначение объединенных блоков,
ü над левой частью блоков ставятся метки, которыми в программе будут помечены операторы, описанные в данном блоке, а в разрыве верхней левой линии ставится номер блока.
Базовые структуры
Преимущество компьютеров и в то же время трудность их использования состоит в том, что они без труда выполняют операции, которые весьма трудоемки или практически невыполнимы людьми, и наоборот, действия, которые нам кажутся столь очевидными, что мы и не пытаемся их анализировать, зачастую становятся проблемой, когда предпринимается попытка их запрограммировать. Внешне заманчивая возможность, предписав одним росчерком пера выполнение тысяч элементарных действий, ставит трудную задачу понимания сложности, проблему, для решения которой необходимо вооружить себя определенными средствами. Такие средства алгоритмизации и программирования носят название базовых (управляющих) структур.
Как всякое автоматическое устройство, компьютер способен выполнять некоторое число элементарных операций: сложение, вычитание, сравнение, запись и чтение данных. Причем он обладает способностью самостоятельно управлять выполнением этих операций во времени. Если попытаться явно выразить возможности этого управления, то можно выделить три основные (базовые) управляющие структуры : цепочка (следование), ветвление, цикл. Эти комбинируемые по желанию структуры дают нам конструктор, позволяющий описать процесс вычислений произвольной сложности и полностью контролировать действия, предписываемые программой.
Практика разработки алгоритмов показывает, что в отдельных случаях одна и та же задача может быть успешно решена по алгоритмам, имеющим различную структуру. Главное требование к алгоритму заключается в том, чтобы он правильно решал поставленную задачу. Для удовлетворения этого требования алгоритм должен быть легким для понимания, простым для доказательства его правильности и удобным для модификации.
Опыт практической алгоритмизации привел к формированию особой методики организации алгоритмов, использование которой уменьшает вероятность ошибок в процессе их разработки и записи, упрощает их понимание и модификацию. Эту методику алгоритмизации называют структурнымпрограммированием.
При структурном программировании алгоритм как бы собирается из трех базовых структур, каждая из которых имеет один вход и один выход – цепочек, ветвлений и циклов. С помощью этих структур можно построить алгоритмы любой сложности, подсоединяя одну структуру к другой и развивая алгоритм не только вширь, но и вглубь. Конструируемые по этой методике алгоритмы четки и понятны, легко поддаются проверке, так как состоят из ограниченного числа одинаково устроенных блоков.
Для использования методики структурного программирования при словесной записи алгоритмов необходимо, чтобы такая запись располагала специальными средствами, адекватно реализующими базовые структуры. Если таких средств в том или ином алгоритмическом языке нет, то для облегчения последующей работы по переводу алгоритма в программу (кодирования) необходимо отработать языковые шаблоны, эквивалентно представляющие базовые структуры.
Таким образом, в соответствии с принципами структурного программирования любой алгоритм можно представить, используя только три базовые структуры – цепочку, ветвление, цикл.
Цепочка
Самой простой базовой структурой является цепочка – последовательность операторов присваивания.
Цепочку можно представить следующей схемой:
Основное свойство цепочки – очередной оператор цепочки будет выполнен после выполнения всех предыдущих операторов, то есть все операторы цепочки выполняются последовательно друг за другом.
Алгоритм циклического обмена в этом случае будет выглядеть следующим образом:
Переменные a и b обмениваются своими значениями через переменную x.
По этому алгоритму можно написать последовательность операторов на Паскале:
x := a;
a := b;
b := x;
Ветвления
Одним из достоинств компьютеров является их способность делать выбор пути решения задачи в зависимости от выполнения заданных условий.
Выбор пути решения осуществляется в алгоритмических языках ветвлениями, которые могут быть представлены в двух формах:
· альтернатива,
· переключатель.
Альтернатива
Альтернатива является простейшей формой ветвлений. Она предполагает выбор одного из двух путей решения задачи, причем этот выбор зависит от выполнения заданных условий:
истина (да)ложь (нет)
Альтернативу можно описать словесно:
ЕСЛИ (условие)
ТО цепочка-1
ИНАЧЕ цепочка-2
В альтернативе может отсутствовать часть (ветвь) ИНАЧЕ, тогда она приобретает вид усеченной альтернативы: