Циклические алгоритмы. Команда повторения

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

Однако «неоднократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма (так называемое «зацикливание»), является нарушением требования его результативности – получения результата за конечное число шагов.

Рассмотрим графическое представлениециклического блока алгоритма. В него входят в качестве базовых следующие структуры: логический элемент с проверкой условия Р и блок S, называемый телом цикла. Здесь тело цикла S расположено после проверки условия Р ( цикл с предусловием ), поэтому может случиться, что при определенных условиях блок S не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется цикл-пока.

Рис. 4.3. Графическая форма представления
цикла с предусловием (цикл - пока)

При словесном представлении алгоритма команда, организующая повторение в цикле-пока, имеет вид:

Таким образом, если Р не выполняется, то предусмотрен выход из цикла на команду, записанную после строки «Конец цикла». Здесь условие Р – это условие на продолжение цикла.

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

Истинность условия Р в этом случае причина окончания цикла.

Рис. 4.4. Графическая форма представления
цикла с постусловием (цикл - до)

При словесном представлении алгоритма команда, организующая повторение в цикле-до, имеет вид:

Возможна ситуация с постусловием и при организации цикла-пока. Итак, цикл-до завершается, когда условие Р становится истинным, а цикл-пока – когда Р становился ложным, то есть цикл-до выполняется «До» истинности условия, а цикл-пока выполняется «пока» указанное выражение остается истинным. Современные языки программирования имеют достаточный выбор операторов, реализующих как циклы-пока, так и циклы-до.

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

4.5. Разработка алгоритмов методом пошаговой детализации.
Вспомогательный алгоритм

Эффективным методом построения алгоритмов является метод пошаговой детализации (последовательного построения). При этом сложная задачаразбивается на ряд более простых задач. Для каждой подзадачи составляется свой, относительно решения основной задачи, вспомогательный алгоритм. Требования к ним продиктованы необходимостью как решения подзадач, так и последующей их «стыковки» в основном алгоритме. Эти подзадачи могут, в свою очередь, потребовать разбиения на ещё более простые задачи, и т. д. В результате некоторые вспомогательные алгоритмы могут стать основными по отношению вспомогательным алгоритмам более низкого уровня. Основной алгоритм содержит команды обращения к вспомогательным алгоритмам. Процесс пошаговой детализации заканчивается, когда задачи очередного уровня окажутся совсем простыми. Метод пошаговой детализации универсален. Он применим для решения задач из разных областей жизни.

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

При составлении и использовании вспомогательных алгоритмов важно знать, что является для них исходными данными (аргументами) и результатами. Иногда команды вызова вспомогательного алгоритма содержат указание на имена тех переменных, которые вносят в него исходные значения, а так же переменных, в которые перед выходом из него попадут значения результата для дальнейшего использования вне вспомогательного алгоритма. Иногда результатом работы вспомогательного алгоритма может стать значение некоторой сигнальной переменной («флажка»), сообщающее об истинности какого-то условия или о наличии какого – либо факта.

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

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

Согласно концепции структурного программирования, вспомогательный алгоритм должен:

– иметь заголовок (имя), с помощью которого его можно вызвать (обратиться нему, чтобы начать его выполнение) из двух вспомогательных или основного алгоритмов (это нужно для «состыковки» алгоритмов);

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

– иметь возможность вызвать другие алгоритмы;

– быть относительно небольшим;

– иметь один вход (т.е. его выполнение всегда начиналось в одной точке, независимо от того, откуда и при каких условиях он был вызван) и один выход. Это гарантирует его замкнутость и упрощает работу с состыкованными алгоритмами;

– обладать единственной функцией, что служит ключом к хорошо спроектированному итоговому алгоритму.

Таким образом, при проектировании основного алгоритма нужно сначала определить необходимый набор функций, а затем разработать вспомогательный алгоритмы.

Методы последовательной детализации применяется при любом конструировании сложных объектов. Это естественная логическая последовательность мышления конструктора: постепенное углубление в детали. В нашем случае, речь идет тоже о конструировании, но только не технических устройств, а алгоритмов. Достаточно сложный алгоритм другим способом практически построить невозможно.