Содержание

Главная >> Информатика 11 класс. Босова

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

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

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

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

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

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

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

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

НАЧАЛО
ПОКА нашлось (333) ИЛИ нашлось (22)
    ЕСЛИ нашлось (333)
        ТО заменить (333, 2)
        ИНАЧЕ заменить (22, 3)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

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

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

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

Окончание >>>