Урок 49. Алгоритмическая конструкция «следование». Линейный алгоритм Материалы урока Печатная версия материалов Вопросы на повторение Что называется алгоритмом? Перечислите способы записи алгоритмов. Что такое величина? Назовите типы величин, которые используются для записи алгоритмов. Какие геометрические фигуры можно использовать в блок-схеме? Что означает элемент блок-схемы «прямоугольник»? Перечислите свойства алгоритмов. Вопрос Попробуйте описать алгоритм процесса приготовления себе чая. Как представлены действия в вашем алгоритме? Можно сказать, что данные действия должны выполняться последовательно. И вот сегодня на уроке мы узнаем, как называется алгоритм, в котором действия выполняются последовательно, и как называется такая структура; научимся исполнять и составлять такие алгоритмы и познакомимся с исполнителями данных алгоритмов. Ежедневно человеку приходится решать много различных задач: в учёбе, во время путешествий, на работе, в повседневной жизни. Все эти задачи описываются своим алгоритмом, и их огромное количество. Но для записи любого алгоритма достаточно трёх основных алгоритмических конструкций: следование, ветвление и повторение. Эту идею предложил и доказал Эдсгер Вибе Дейкстра, нидерландский учёный, известный своими работами в области алгоритмики. Сегодня на уроке мы изучим одну из трёх алгоритмических конструкций — следование. Следование — это алгоритмическая конструкция, отображающая естественный, последовательный порядок действий. Алгоритмы, в которых используется только структура «следование», называются линейными алгоритмами. Примером конструкции «следование» может служить чтение какого-нибудь произведения, где страницы нужно перелистывать одну за другой, а следующая начинается только тогда, когда закончится предыдущая. Графическое представление этой алгоритмической структуры представлено на рисунке 1. Рис. 1 Рассмотрим алгоритм приготовления растворимого какао-порошка. Как вы думаете, данный алгоритм будет линейным? алг приготовление какао нач взять чашку насыпать 1–2 чайные ложки какао-порошка налить горячее молоко насыпать сахар по вкусу всё перемешать кон Почему вы так решили? Обоснуйте свой ответ. Приведите примеры линейного алгоритма из повседневной жизни. Задание 1 Дан фрагмент линейного алгоритма. Определите значение переменной b после выполнения алгоритма. a := 1 b := 4 a := a 3 + b2 b := a*2 - b Верно 30 Далее Для решения данного фрагмента алгоритма удобнее использовать таблицу значений переменных, задействованных в алгоритме: Шаг алгоритма Переменные а b 1 1 4 2 17 4 3 17 30 Составленная таблица значений переменных моделирует работу исполнителя этого алгоритма. Пока мы рассматривали с вами линейные алгоритмы, исполнителем которых являлся человек. Давайте теперь рассмотрим линейные алгоритмы для формальных исполнителей с заданной системой команд. Рассмотрим формального исполнителя Робот. Ему доступны пять команд перемещения: вверх, вниз, влево, вправо, закрасить. При выполнении каждой из них Робот перемещается на одну клетку в соответствующем направлении. По команде «закрасить» он закрашивает клетку, в которой находится. Исполнителя Робот будем обозначать звёздочкой. Задание 2 Составьте линейный алгоритм, выполнив который Робот нарисует на клетчатом поле узор и вернётся в исходное положение, обозначенное звёздочкой. А теперь подумайте, что произойдёт, если Робот приступит к выполнению этой же программы в обстановке, в которой между двумя клетками есть стена: Да, действительно, это приведёт к разрушению Робота. Это особенность линейных алгоритмов, которая состоит в том, что исполнитель не может уклониться от выполнения ни одной из последовательно идущих команд. Поэтому линейные алгоритмы используют редко или для конкретного (частного) случая. Решение задач Задание 3 Некоторый исполнитель может выполнять над целыми числами, кроме операций сложения, вычитания, умножения и деления, ещё две операции: div — вычисляется целое частное и mod — вычисляется остаток от деления.