§6. Алгоритмические структуры
Информатика. 11 класса. Босова Л.Л. Оглавление
6.1. Последовательная алгоритмическая конструкция
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, разветвляющиеся, циклические, вспомогательные и рекурсивные. Для записи любого алгоритма достаточно трёх основных алгоритмических структур: последовательной, разветвляющейся, циклической.
Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы.
Пример 1. Алгоритм, реализованный через последовательную алгоритмическую конструкцию, представлен блок-схемой на рисунке 2.4.
Рис. 2.4. Последовательная алгоритмическая конструкция
Выясните, какую задачу решает этот алгоритм. Чему равен результат работы алгоритма при х = 2?
Пример 2. Из курса информатики основной школы вам знаком исполнитель Вычислитель, выполняющий программы линейной структуры. Его система команд может содержать две и более команды с использованием арифметических операций.
Пусть исполнитель Вычислитель может выполнять следующие команды:
1) прибавь 2;
2) умножь на 3.
Подсчитаем, сколько разных программ, состоящих из трёх команд, можно составить для этого исполнителя, и выясним число различных значений, которые будут получены в результате их исполнения при начальном значении 2.
Так как каждую из команд вы можете выбрать одним из двух вариантов, а всего команд в программе три, общее число программ находится как N = 23.
Для удобства поиска числа разных вариантов значений, которые будут получены по этим программам, составим дерево решений (рис. 2.5). В его корневой вершине (0-й уровень) записывается начальное значение. Ветви дерева соответствуют командам: левые — первой, правые — второй. В каждой вершине дерева 1-го, 2-го и т. д. уровней записывается результат, полученный после применения команды к числу из вершины-предка. Путь к каждой из вершин соответствует последовательности команд (программе) для получения значения, находящегося в вершине. Таким образом в вершинах N-го уровня будут записанны результаты программ, состоящих из N команд.
В нашем примере все значения в вершинах третьего уровня различны. Иногда значения в вершинах одного уровня совпадают. Можно сказать, что в общем случае число различных значений на уровне не превышает числа его вершин.
Рис. 2.5. Пример дерева решений
Номер уровня, на котором впервые появляется необходимое число, равен минимальному количеству команд для его получения. В нашем примере число 8 записано в вершинах 2-го и 3-го уровней, следовательно, минимальное количество команд для его получения равно двум.
Для определения количества программ, с помощью которых требуемое число получается из заданного, можно подсчитать количество вершин дерева, в которых записано требуемое число.
Подумайте, почему при заданных условиях существует только две программы для получения из числа 2 числа 8.
Если количество уровней вершин в дереве решений превышает четыре, то строить такое дерево неудобно. Так же как и в случае, когда система команд исполнителя состоит из трёх и более команд.
Для некоторых задач удобнее строить обратное дерево решений: команды исполнителя меняются на «обратные», пути строятся от результата к начальному значению.
На рисунке 2.6 показан пример построения обратного дерева решений (из числа 8 получаем число 2; команды: 1) вычти 2; 2) раздели на 3).
Рис. 2.6. Пример обратного дерева
Этот приём удобно использовать, когда обратные команды неприменимы ко всем решений вершинам.
6.2. Алгоритмическая конструкция «ветвление»
Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды алгоритма будут выполняться. При каждом конкретном наборе входных данных алгоритмическая конструкция «ветвление» сводится к выполнению последовательной алгоритмической конструкции.
Пример 3. Алгоритм, реализованный через алгоритмическую конструкцию «ветвление», представлен блок-схемой на рисунке 2.7.
Рис. 2.7. Алгоритмическая конструкция «ветвление»
Выясните, какую задачу решает этот алгоритм. К какой последовательной алгоритмической конструкции сводится эта разветвляющаяся конструкция при:
1) х= -10;
2) х = 2;
3) х = 10?
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, при которых возможен такой результат.
САМОЕ ГЛАВНОЕ
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, разветвляющиеся, циклические, вспомогательные и рекурсивные. Для записи любого алгоритма достаточно трёх основных алгоритмических структур: последовательной, разветвляющейся, циклической.
Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы.
Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды алгоритма будут выполняться.
Алгоритм реализован с использованием циклической алгоритмической конструкции, если некая группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных данных.
Вопросы и задания
1. Какая алгоритмическая конструкция называется последовательной?
3. Какая алгоритмическая конструкция называется ветвлением? Как она связана с последовательной?
4. Как на блок-схемах изображается полное ветвление? Неполное ветвление?
7. Какая алгоритмическая конструкция называется циклической? Как она связана с ветвлением?
§ 5. Основные сведения об алгоритмах
§ 6. Алгоритмические структуры
§ 7. Запись алгоритмов на языках программирования