Краткое содержание: Параграф § 6 / Информатика 11 класс

Алгоритмические конструкции

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

• Последовательная (линейная)
• Разветвляющаяся (ветвление)
• Циклическая (цикл)

Существуют также вспомогательные и рекурсивные алгоритмические конструкции.

Последовательная конструкция (линейный алгоритм)

Эта конструкция реализуется, когда все команды алгоритма выполняются строго один раз, в том порядке, в котором они записаны.

Разветвляющаяся конструкция (ветвление)

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

Циклическая конструкция (цикл)

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

• Цикл с предусловием (цикл-пока): Условие проверяется перед первым выполнением тела цикла. Если условие ложно, тело цикла не выполняется ни разу.
• Цикл с постусловием (цикл-до): Тело цикла выполняется хотя бы один раз, затем проверяется условие, чтобы определить, нужно ли повторить цикл.
• Цикл с параметром (счётный цикл): Используется, когда заранее известно количество повторений. Он включает заголовок, определяющий начальное значение параметра, конечное значение и шаг его изменения.

Применение алгоритмических структур

Различные задачи в информатике, такие как поиск пути для исполнителя или обработка строк (например, для исполнителя Редактор), демонстрируют практическое применение этих структур. Например, задача на поиск кратчайшей программы для исполнителя с заданным набором команд часто решается с помощью построения дерева решений. В этом дереве вершина нулевого уровня — это начальное значение, а ветви, исходящие из вершины, соответствуют командам, которые можно применить, приводя к результатам на следующем уровне. Корень дерева соответствует начальному значению, а вершины на уровне \( N \) соответствуют результатам, полученным после \( N \) команд.

Для некоторых задач удобно использовать обратное дерево решений, строя пути от результата к начальному значению, используя обратные команды. Например, если команды исполнителя 'прибавь 2' и 'умножь на 3', то обратными будут 'вычти 2' и 'раздели на 3'.

Пример работы исполнителя Редактор

Исполнитель Редактор работает со строками и может выполнять две команды: Нашлось (v), которое проверяет наличие цепочки \( v \) в строке; и Заменить (v, w), которое заменяет первое слева вхождение цепочки \( v \) на цепочку \( w \). Программы для Редактора часто используют цикл ПОКА и оператор ветвления ЕСЛИ.

Например, программа для Редактора может выглядеть так:

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

Эта программа демонстрирует использование циклической (ПОКА) и разветвляющейся (ЕСЛИ...ИНАЧЕ) структур для преобразования строки цифр.

Еще один пример: если программа для Редактора заменяет '333' на '2' и '22' на '3', то строка, состоящая из \( N \) подряд идущих цифр 3, преобразуется по следующему принципу. Количество цифр 3, деленное на 5, определяет, какой будет последняя цифра в результате (3, 2, или ничего), а остаток от деления влияет на последовательность преобразований.

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