Урок 8
§6. Алгоритмические структуры

6.3. Циклическая алгоритмическая конструкция

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

Циклическая структура (цикл) обеспечивает многократное выполнение одних и тех же команд. Существует несколько разновидностей циклических структур: цикл с предусловием (цикл-пока), цикл с постусловием (цикл-до), цикл с параметром. Любая циклическая структура состоит из двух частей — заголовка и тела цикла. Последовательность команд, повторяющуюся при выполнении цикла, называют телом цикла. Заголовок определяет количество повторений тела цикла. На рисунке 2.8 представлены блок-схемы цикла с предусловием и цикла с параметром.

Рис. 2.8. Блок-схемы циклов

Пример 4. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в которых параметры v и w обозначают цепочки цифр.

Команда нашлось (и) проверяет, встречается ли цепочка и в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Команда заменить (v, ш) заменяет в строке первое слева вхождение цепочки v на цепочку w.

Дана программа для исполнителя Редактор:

Выясним, какая строка получится в результате применения приведённой выше программы к строке, состоящей из N подряд идущих цифр 3 при:

1) N = 21;
2) N = 25.

Пусть N = 21. Исполнитель Редактор начинает работать со строкой, состоящей из одних только цифр 3: первые три цифры 3 сразу же заменяются цифрой 2, следующие три цифры 3 тоже заменяются цифрой 2, полученные две цифры 2 заменяются цифрой 3. После этого мы фактически возвращаемся к исходной задаче, которую должны решить для строки из 16 (21-3-3 + 1) подряд идущих троек:

Можно сказать, что при каждом повторении описанных выше действий из последовательности вычёркивается по пять цифр 3: 21[3] → 16[3] → 11[3] → 6[3] → 1[3] или 3.

Пусть N = 25. Тогда:

25[3] → 20[3] → 15[3] 10[3] → 5[3] → 1[2]2[3] или 233.

Итак, можно вычёркивать из последовательности по пять цифр 3, но только при условии, что в ней есть шесть и более идущих подряд троек.

Самостоятельно определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 22, 23 и 24 подряд идущих цифр 3.

Таким образом, можно сформулировать следующее правило преобразования строки из N подряд идущих цифр 3, соответствующее приведённому выше алгоритму:

1) если N mod 5 = 0, то N := 5, иначе N := N mod 5;
2) исполнить исходный алгоритм для строки, состоящей из N подряд идущих цифр 3.

Определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 2017, 12 345 подряд идущих цифр 3.

Определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 2015, 12 347 подряд идущих цифр 2.

Пример 5. Алгоритмы, реализованные через циклическую алгоритмическую конструкцию, представлены блок-схемами на рисунке 2.9.

Рис. 2.9. Циклическая алгоритмическая конструкция

Известно, что X, А, В, S — целые положительные числа. Выясните, какую задачу решает каждый из алгоритмов на рисунке 2.9.

Известно, что при некотором X результатом работы и первого, и второго алгоритмов является число 3. Укажите все значения X, при которых возможен такой результат.

Cкачать материалы урока