Изучение алгоритмических конструкций начнем с линейного алгоритма. В учебниках иногда используется термин «следование».

4)Линейный алгоритм

Изучение алгоритмических конструкций начнем с линейного алгоритма. В учебниках иногда используется термин «следование».

Алгоритм назовем линейным, если:1) выполняется каждый его шаг, и 2) только один раз.

Такого определения вполне достаточно. В некоторых учебниках используются слова «шаги выполняются последовательно, друг за другом», но эти слова означают наличие некоторого порядка. А порядков имеется два!

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

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

Линеен алгоритм обмена, алгоритмы деления угла или отрезка пополам и многие другие.

Ветвление неполное

Вернемся к нашему определению линейного алгоритма и попытаемся определить остальные алгоритмические структуры.

Для начала, откажемся от требования 1), обязательности выполнения каждого шага алгоритма.

Имеем алгоритм, в котором некоторые шаги могут не выполняться.

Получившаяся структура алгоритма называется. НЕПОЛНОЕ ВЕТВЛЕНИЕ

Согласно принципу детерминированности алгоритмов, исполнитель должен знать, выполнять отмеченный шаг или нет. Приходится ввести понятие «условие», то есть предложение, значение которого либо «истина», либо «ложь».

Если условие истинно – шаг алгоритма выполняется, иначе – нет.

Всевозможные условия являются объектом работы, то есть ДАННЫМИ, которые могут иметь либо значение истина, либо значение ложь. Образуются эти значения при сравнении двух переменных или выражений одного типа.

A=B;A<>B;X<>5;A>5;B<3;C<=A+B

Значения этих выражений «истинно» (true) или «ложно» (false) зависит от значений используемых переменных.

На языке блок-схем блок ветвления обозначается ромбом, имеет один вход и два выхода. Однако любой алгоритм должен обладать свойством результативности, то есть у него должен быть конец и только один. Обе ветви, для достижения конца соединяются, место соединения называется УЗЕЛ и на блок-схеме отмечается кружком.

Наличие двух выходов так же представляет собой проблему. Выходы должны быть разными. Поэтому они маркируются словами «да» и «нет» или знаками «+» и «-». Согласно первому выходу алгоритм продолжаем при истинности условия, которое вписывается в ромб, иначе – продолжаем согласно второму выходу. Лентяи просто ставят около выхода «да» точку. Этого достаточно для однозначного определения дальнейших шагов алгоритма.

Цикл

Ветвление - один из случаев нарушения линейности алгоритма.

Как уже отмечалось, на блок-схеме ветвление обозначается ромбом, внутри которого указывается условие. Блок ветвления имеет один вход и два выхода. Обе ветви, для достижения конца соединяются в узле.

Однако ветви могут соединиться и перед блоком условия!

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

Такая организация алгоритма называется ЦИКЛ.

Шаги, которые могут выполняться несколько раз подряд образуют ТЕЛО цикла. Выполнять или нет тело еще раз решает УСЛОВИЕ цикла.

Итак, любой цикл имеет ТЕЛО и УСЛОВИЕ ВЫХОДА.

Снова вспоминаем свойство алгоритма, что его можно исполнить и его можно записать.

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

В первом случае цикл называется циклом типа «пока», во втором – циклом типа «до».

Так выглядит оформление цикла с предусловием (цикла «пока») в разных языках программирования.

basic		pascal		C
10 if < усл.> then 40 20 <тело цикла "ПОКА"> 30 goto 10 40 while <усл.> <тело цикла "ПОКА"> wend		while <усл.> do begin <тело цикла "ПОКА"> end;		while <усл.> { <тело цикла "ПОКА"> }

А так выглядит оформление цикла с постусловием (цикла «до») в языках программирования.

basic		pascal		C
10 rem начало цикла 20 <тело цикла «ДО»> 50 if <условие> then 10		repeat <тело цикла "ДО"> until <усл.>;		do {<тело цикла "ДО">} while <усл.>

Основным различием циклов ДО и ПОКА является то, что в цикле ДО тело цикла один раз выполняется обязательно, а в цикле ПОКА возможна ситуация, когда тело цикла не выполнится ни разу.Изменив условие, для цикла ПОКА можно добиться выполнения цикла один (первый) раз, цикл будет работать как и цикл ДО.Запретить выполнение первого раза тела цикла типа ДО невозможно.Так как из цикла ПОКА можно получить цикл ДО, цикл ПОКА является более универсальным.

Попытки определить тип цикла по семантическому значению слов «до» и «пока» в русском языке обречены на неудачу.

Фразы:

Тело цикла выполняется до тех пор ПОКА позволяет условие

И Тело цикла выполняется ДО тех пор пока позволяет условие

Различаются только акцентом.

Как видим, задача может быть решена как использованием цикла «пока», так и использованием цикла «до».

Довольно часто выбор типа цикла несущественен.

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

Например, если вы собираетесь удалить пробелы, стоящие в начале строки, то, скорее всего, выберете цикл с предусловием, потому что надо сначала убедиться, что пробел имеется, и только затем его удалять (глупо поступать наоборот - сначала удалять, а потом проверять, стоило ли это делать). Зато ввод текста до точки трудно построить иначе как с постусловием, поскольку сначала требуется ввести очередной символ и только потом сравнивать его с точкой.

Для цикла ПОКА принято организовывать выход при значении условия "ложно", а для цикла ДО принято организовывать выход при значении условия "истина". Это следует знать, если вы работаете, скажем, на паскале.

Однако, Вы можете разработать свой язык программирования, где все будет наоборот. Требование придерживаться этих условий при работе с блок-схемами мне кажется неправильным.

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

Дата добавления: 2015-11-04