- Последовательная алгоритмическая конструкция (следование)
- Алгоритмическая конструкция «ветвление»
- Циклическая алгоритмическая конструкция
- знать типы базовых алгоритмических конструкций: следование, ветвление, цикл
- уметь составлять алгоритм для формального исполнителя, используя базовые алгоритмические конструкции
- Практически во всех предметных областях существуют стандартные алгоритмы. Приведите примеры известных вам алгоритмов из разных предметных областей.
Последовательная алгоритмическая конструкция
В 1969 году нидерландский учёный Эдсгер Дейкстра доказал теорему о том, что для решения любой задачи можно придумать алгоритм, который будет включать в себя лишь три алгоритмических конструкции: следование, ветвление и повторение (цикл). Их называют базовыми. Дополнительной структурой является рекурсия.
Алгоритм реализован через последовательную (линейную) алгоритмическую конструкцию, если все команды алгоритма выполняются один раз строго по порядку друг за другом.
Пример 1
Рис. 1. Пример 1
Рассмотрим блок-схему алгоритма
(рис. 1), реализованного через последовательную алгоритмическую конструкцию. Определим, чему равен результат работы алгоритма при Х = 5.
Решение
Представим решение задачи в виде таблицы. Пусть Х = 5, тогда
Таблица 1. Пример 1 (решение)
|
Шаг
|
Команда
|
Y
|
|
1
|
Y := X + 2 * X
|
15
|
|
2
|
Y := Y * X
|
75
|
|
3
|
Y := Y + 1
|
76
|
|
4
|
Y := X + Y
|
81
|
Представление алгоритма в виде таблицы с последовательностью шагов называется трассировочной таблицей.
Ответ: 81.
Упражнение 1
Определите результат работы алгоритма, представленного на рис. 1 для значения X = 1.
Алгоритмическая конструкция «ветвление»
Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды алгоритма будут выполняться.
Пример 2
Определите результат работы алгоритмической конструкции «ветвление», представленной в виде блок-схемы на рис. 2, при значении N = 3.
Рис. 2. Пример 2
Решение
Представим решение задачи в виде таблицы. Пусть N = 3, тогда
Таблица 2. Пример 2 (решение)
|
Шаг
|
Команда
|
Результат
|
N
|
R
|
|
1
|
N < 0?
|
Нет
|
3
|
-
|
|
2
|
N < 5?
|
Да
|
3
|
0
|
Ответ: 0.
Упражнение 2
Определите результат работы алгоритма, представленного на рис. 2, для значений N = 7; N = −3.
Циклическая алгоритмическая конструкция
Алгоритм реализован с помощью циклической алгоритмической конструкции (цикл), если в нём существует последовательность команд, которая может выполняться многократно в зависимости от входных данных.
Последовательность команд, повторяющаяся при выполнении цикла, называется телом цикла.
Любая циклическая конструкция содержит в себе элементы алгоритмической конструкции «ветвление».
Цикл обеспечивает многократное повторение одних и тех же команд и, как правило, состоит из двух частей: условия выхода (или продолжения) цикла и тела цикла. Выделяют три основные конструкции циклов.
Рис. 3. Три основные конструкции циклов
Пример 3
Исполнитель Редактор получает на вход строку цифр и преобразует её. Он может выполнять две команды, в обеих командах x и y обозначают цепочки цифр:
- заменить (x, y): заменяет в строке первое слева вхождение цепочки x на цепочку y. Если в строке нет вхождений цепочки x, то выполнение команды заменить (x, y) не меняет эту строку;
- нашлось (y): проверяет, встречается ли цепочка y в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Найдите сумму цифр в строке, которая получится в результате применения приведённой ниже программы к строке, состоящей из 20 цифр 3.
НАЧАЛО
ПОКА нашлось (333) ИЛИ нашлось (222)
ЕСЛИ нашлось (222)
ТО заменить (222, 3)
ИНАЧЕ
заменить (333, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
Данный алгоритм сначала заменяет все ‘333’ на ‘2’, в итоге получится 9 двоек и одна тройка. После чего заменит 9 двоек на три тройки. А три тройки на одну двойку. В итоге получим 23. В сумме это 5.
Ответ: 5.
Упражнение 3
Исполнитель Редактор получает на вход строку цифр и преобразует её. Он может выполнять две команды, в обеих командах x и y обозначают цепочки цифр:
- заменить (x, y): заменяет в строке первое слева вхождение цепочки x на цепочку y. Если в строке нет вхождений цепочки x, то выполнение команды заменить (x, y) не меняет эту строку;
- нашлось (y): проверяет, встречается ли цепочка y в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Найдите сумму цифр в строке, которая получится в результате применения приведённой ниже программы к строке, состоящей из 20 цифр 3 и 20 цифр 2.
НАЧАЛО
ПОКА нашлось (333) ИЛИ нашлось (222)
ЕСЛИ нашлось (222)
ТО заменить (222, 3)
ИНАЧЕ
заменить (333, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Итоги
- Существует три базовые алгоритмические конструкции: последовательные, разветвляющиеся, циклические.
- Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды в нём выполняются один раз, строго по порядку.
- Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит какие именно команды алгоритма будут выполняться.
- Алгоритм реализован через циклическую алгоритмическую конструкцию, если некоторая группа команд в нём может повторяться многократно в зависимости от входных данных.
Контрольные вопросы
- Охарактеризуйте, как работают базовые алгоритмические конструкции.
- Как вы считаете, достаточно ли трёх базовых конструкций для реализации любого алгоритма?
- Как изображаются знакомые вам базовые алгоритмические конструкции на блок-схеме?
- С какими алгоритмическими конструкциями вы можете связать следующие объекты: времена года, часы, жизнь человека, лабиринт?
- Приведите примеры из математики, связанные с базовыми алгоритмами. Обоснуйте, как можно применить ту или иную структуру для решения задачи.
Упражнение 1
5
Упражнение 2
1.2; 2.3
Упражнение 3
10
