Вообще, понятие "цикл" условно. У вас есть процесс с определённой структурой, который вы пытаетесь описать алгоритмом (как "грамматикой" на процессы).
И уже в сложных случаях просто смотреть, какой способ описания ближе к "природе задачи".
Если описать не алгоритмически, а чисто регулярным выражением приведённые в начале схемы варианты, то:
{ красить; шаг_вправо; проверка_всё_ли_покрашено; [проверка_краски; [сходить_в_сарай; проверить_наличие; [набрать]]}
или
{ {красить; шаг_вправо; проверка_всё_ли_покрашено; [проверка_краски]} [сходить_в_сарай; проверить_наличие; [набрать]]}
- по сути, как скобки поставить
Формально всегда есть много эквивалентных вариантов - и единственным формальным критерием может быть только формальная сложность (какая-то метрика типа количества чего-нибудь) и структурированность (соответствие каким-то ограничениям на структуру).
А дальше уже нужно вводить в дело содержательные критерии, системный анализ задачи - и какая формальная запись лучше, "естественнее".
Действие, выполняющееся в повторяющемся процессе не на каждой итерации, а иногда, можно рассмотреть как условное, а можно трактовать как тело внешнего цикла. Но в данной задаче основной процесс - это покраска, целевое штатное условие окончания - "забор покрашен", т.е. оно будет относиться к внутреннему циклу и дублироваться в условии внешнего (в случае Дракона входить в траекторию внешнего). А действия - сходить в сарай, набрать краски - вообще второстепенные, обеспечивающие.
Всё это говорит в пользу того, чтобы вообще рассматривать данный алгоритм как один цикл с условной частью.
СРАЗУ СКАЖУ, что нужно использовать как более общий, цикл с предусловием.
Потому что общий случай - 0 и более. Забор из нуля досок. Забор уже покрашенный. И т.п.
Нет ни одного аргумента в пользу цикла с постусловием, кроме очень редких оптимизирующих случаев. Но пока порассуждаю в рамках данного цикла с постусловием (а потом уже поговорим о переходе к WHILE).
Т.е. действуем по принципу: наружный цикл - главный, внутренний - вспомогательный (признак: естественно свёртывается до вспомогательного алгоритма), иначе наружный оформляем как условную часть единственного цикла.
В нашем случае сравним два описания:
Код:
REPEAT
Покрасить_доску;
Шаг_вправо;
IF есть_некрашенная_доска & краска_кончилась THEN
Попробовать_набрать_краски_в_сарае (* Вспомогательный алгоритм *)
END
UNTIL...
- абсолютно естественно
Или:
REPEAT
Красить_доски_пока_не_кончится_краска (* Даже само название вспом. алгоритма вымученное... *)
Попробовать_набрать_краски_в_сарае
UNTIL
И, несмотря на внешнюю простоту, у вас во вспом. алгоритме будет ещё один цикл.
И у вас появится плохая связность между вспомогательными алгоритмами (алгоритм Красить доски будет вынужден знать про то, что краска может кончаться и т.п.).
Т.е. с точки зрения задачи вариант с одним циклом гораздо лучше.
А если у вас основной цикл - не с простым условием, а, например, с вариантом остановки по сломанной доске (чтобы пойти и сказать хозяину забора). Тогда в случае двух вложенных циклов у вас это условие потащится дважды.
Пример из реальной жизни - это типа (тут уже не буду вымучивать что-то с REPEAT, а дам с WHILE):
Код:
i := 0; j := 0;
WHILE (i < M) & ~( X[i, j] - искомый ) DO
INC(j);
IF j > N THEN
j := 0;
INC(i)
END
END
Ну, сами можете перерисовать на ДРАКОНЕ (циклы с конъюнкцией в условии весьма выразительно на нём смотрятся).
Т.е. есть основная структура цикла WHILE не_конец_последовательности & ~текущий_элемент_удовлетворяет_условию DO перейти_к_следующему END
- и то, что последовательность тут имеет двумерную структуру (да хоть трёхмерную) - это частность. Более сложное действие перейти_к_следующему, содержащее условие. Вот и всё.
И попробуйте натянуть этот цикл на два вложенных. Будет жуткий и безграмотный for-for-if-break (как 99% и пишет).
Контрпример: если у вас в циклическом процессе есть более часто повторяющаяся внутренняя последовательность, которая может быть вообще упрятана в один вспомогательный алгоритм. То это естественным образом представляется как два цикла (хотя, конечно, можно заложить и в один, но будет "искажать смысл").
Например, цикл покраски отдельной доски.
Давайте уже, наконец, перейдём от REPEAT-ового заборного цикла к более общему WHILE.
Код:
Наполнить_ведро_краской;
Выбрать_левую_доску_как_текущую;
WHILE забор_не_кончился & есть_краска_в_ведре DO
(* Покрасить_доску. Лучше оформить как отдельный алгоритм, но для примера поставим вложенные циклы прямо сюда *)
WHILE текущая_доска_не_покрашена_до_конца & есть_краска_в_ведре DO
Макнуть_кисть;
WHILE кисть_ещё_мажет DO
Провести_кистью_по_некрашенному_месту_доски
END
END;
IF текущая_доска_покрашена THEN
Сделать_шаг_вправо
END;
IF нет_краски_в_ведре THEN
Попытаться_набрать_краску_в_сарае
END
END
Это и пример гораздо более общего алгоритма, и того, какие из действий циклического процесса стоит оформлять внутренним условием, а какие - внутренними циклами. И, кстати, обслуживающие главную логику действия в сарае таки целесообразно упрятать вообще в алгоритм Попытаться_набрать_краску_в_сарае.
И условие есть краска в сарае - нет краски в сарае - вообще не выносится на уровень основного алгоритма. Если к концу тела цикла в ведре нет краски => краски в сарае нет.
Инвариант данного цикла. Напоминаю, что инвариант - это "рамка", "рельсы цикла", а формально говоря, логическое условие, истинное до начала цикла и по окончании каждой его итерации (в том числе после последней итерации). Инвариант нарушается в теле цикла - и восстанавливается к концу тела цикла.
Содержательный инвариант накладывается на меняющиеся в цикле величины / состояния объектов.
У нас это состояние забора и состояние ведра.
Инвариант: все_доски_слева_от_текущей_покрашены_полностью & ( нет_краски_в_ведре => нет_краски_в_сарае )
(т.е. перед циклом и по окончании каждой итерации в ведре может не быть краски только тогда, когда нет краски вообще).
Постусловие: все_доски_покрашены ИЛИ нет_краски_в_ведре (* по причине отсутствия её в сарае *)
С точки зрения физической задачи можно оптимизировать и убрать лишнее действие похода в сарай, если вдруг красить уже нечего.
Код:
IF нет_краски_в_ведре & забор_не_кончился THEN
Попытаться_набрать_краску_в_сарае
END
Но тогда пустое ведро по окончании цикла перестаёт служить признаком глобального отсутствия краски. Если после цикла нам надо различать эту ситуацию, то потребуется какой-то отдельный флаг вместо признака пустого ведра... Поэтому в алгоритмах, где "поход за краской" ничего не стоит, проще первый вариант.
Инвариант для второго варианта: все_доски_слева_от_текущей_покрашены_полностью & (нет_краски_в_ведре => (нет_краски_в_сарае OR забор_покрашен))
Вообще, просто "ДРАКОНИстое" визуальное мышление очень плохо помогает составлять циклы.
ДРАКОН хорош для декомпозиции алгоритмов, для автоматной логики по состояниям на основе веток - и для условной логики. На самом деле, именно условия, разветвления логики - "ахиллесова пята" по ошибкам и по сложности восприятия алгоритмов. И ДРАКОН тут неплохо помогает.
А циклы со сложными условиями иногда неплохо ложатся на ДРАКОН как окончательное представление (когда выход по каждому конъюкту - отдельная отходящая вниз ось), но чтобы их нормально составлять, нужно мыслить формальнее и "текстовее".
Тогда и, кстати, никакой особой проблемы по риску ошибок на циклах не будет. Правильно составленному циклу уже "по барабану" - 0 или N раз выполняться ))
И мозгу не приходится прогонять комбинаторно все варианты.
В отличие от условной логики, где часто идёт "комбинаторный взрыв" (что хорошо известно при покрытии тестами, конечно).
Ну и на закуску нельзя не упомянуть, что именно в силу вот этих дилемм "вложенный цикл или цикл с IF" Эдсгер Дейкстра и ввёл свой обобщённый многоветочный цикл. WHILE условие_ветки_1 DO .... ELSIF условие_ветки_2 DO .... ELSIF условие_ветки_3 DO .. END (выполняется, пока истинна хотя бы одна из веток).
https://forum.oberoncore.ru/viewtopic.php?f=30&t=1225Цикл позволяет явно отклассифицировать все возможные варианты итераций в рамках одного циклического процесса. Т.е. "пока возможно каким-то образом, оставаясь в рамках инварианта, продвигаться вперёд, продвигаемся". А постусловие - конъюнкция отрицаний всех веток.
Часто полезно спроектировать циклический процесс как ЦД, хотя иногда реально потом лучше перейти к одному WHILE и поставить вложенные IF (т.к. между вычислениями условий нужны какие-то действия, и т.п.).
Код:
WHILE забор_не_докрашен & есть_краска_в_ведре DO
Покрасить_текущую_доску;
Шагнуть_вправо;
ELSIF забор_не_докрашен DO
Попытаться_набрать_краску_в_сарае
END
Вход
FAQ
Поиск
