ИЗУЧЕНИЕ ИНСТРУКЦИЙ

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

Ключевые слова

• следование

• ветвление

• повторение

• линейные алгоритмы

• разветвляющиеся алгоритмы

• циклические алгоритмы

Человеку в жизни приходится решать множество различных задач. Решение каждой из них описывается своим алгоритмом, и разнообразие этих алгоритмов очень велико. Вместе с тем для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения. Это положение выдвинул и доказал Э. Дейкстра в 70-х гг. прошлого века.

Эдсгер Вибе Дейкстра (1930-2002) — выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

Следование

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

Графическое представление алгоритмической конструкции «следование» приведено на рис. 1.

Рис. 1. Алгоритмическая конструкция «следование»

Пример 1. Линейный алгоритм приготовления отвара шиповника.(рис.2)

Обратите внимание, что многие из предписаний этого алгоритма могут потребовать детализации — представления в виде некоторой совокупности более мелких предписаний.

Пример 2. У исполнителя Робот есть четыре команды перемещения (вверх, вниз, влево и вправо), при выполнении каждой из них Робот перемещается на одну клетку в соответствующем направлении. По команде закрасить Робот закрашивает клетку, в которой он находится. Запишем линейный алгоритм, исполняя который Робот нарисует на клетчатом поле следующий узор и вернётся в исходное положение, обозначенное звёздочкой (рис.3)

Пример 3. Дан фрагмент линейного алгоритма:

х:=2

у:=х*х

У:=У*У

х:=у*х

s:=x+y

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

Составленная нами таблица значений переменных моделирует работу исполнителя этого алгоритма.

Пример 4. Некоторый исполнитель может выполнять над целыми числами кроме операций сложения, вычитания, умножения и деления ещё две операции: с помощью операции div вычисляется целое частное, с помощью операции mod — остаток.

Например: 5 div 2 = 2; 5 mod 2 = 1; 2 div 5 = 0; 2 mod 5 = 2.

Покажем, как с помощью этих операций можно реализовать алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим количеством банкнот по 500 (k500), 100 (k100), 50 (k50) и 10 (k10) рублей.(рис.5)

https://www.yaklass.ru/p/informatika/8-klass/osnovy-algoritmizatcii-14923/osnovnye-algoritmicheskie-konstruktcii-13987/re-f874a988-2062-48c6-800e-64baab38bfb8

Выполните свои задания и совместно с друзьями постарайтесь выполнить итоговое задание. Пройдите тестирование.

рис.1

рис.2

рис.3

рис.4

рис.5

САМОЕ ГЛАВНОЕ


Для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения.

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

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

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


1) цикл с заданным условием продолжения работы;

2) цикл с заданным условием окончания работы;

3) цикл с заданным числом повторений.