Урок 2. Базовые алгоритмические структуры
Предмет: Информатика, 11 класс

Конспект урока

Информатика, 11 класс. Урок № 2.

Тема — Базовые алгоритмические структуры

Перечень вопросов, рассматриваемых в теме: алгоритм, блок-схема, следование, линейный алгоритм, ветвление, полная форма ветвления, неполная форма ветвления, разветвляющийся алгоритм, повторение, циклический алгоритм, цикл с предусловием, цикл с постусловием, цикл с параметром, комбинации базовых алгоритмических структур

Глоссарий по теме: следование, ветвление, повторение, цикл с предусловием, цикл с постусловием, цикл с параметром.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса

— М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 11 класса — М.: БИНОМ. Лаборатория знаний, 2012

Теоретический материал для самостоятельного изучения

В 1969 году нидерландский ученый Эдсгер Дийкстра доказал важную теорему. Суть ее в том, что для решения любой логической задачи можно составить алгоритм, используя лишь три алгоритмических структуры: следование, ветвление и повторение. Эти структуры называют базовыми.

Самой простой структурой является «следование».

Алгоритм реализован через последовательную алгоритмическую структуру, если все команды этого алгоритма выполняются один раз, причем в том порядке, в котором они записаны.

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

Рис. 1

Следующей конструкцией является «ветвление». Она встречается, если действия алгоритма зависят от некоторого условия.

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

Существуют полная и неполная формы ветвления.

В полной форме если условие выполняется, то алгоритм переходит к выполнению первой серии команд, а если не выполняется — то ко второй.

В неполной форме алгоритм выполняет серию команд только если условие истинно. В противном случае ничего не происходит.

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

Рис. 2

И, наконец, последняя алгоритмическая конструкция — «повторение».

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

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

Существует несколько разновидностей циклических алгоритмов.

Первый — цикл с заданным условием продолжения работы (цикл с предусловием или цикл-пока).

Второй — цикл с заданным условием окончания работы (цикл с постусловием или цикл-до).

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

Доказано, что при решении задач можно ограничиться только одним циклом — циклом с предусловием. Но в ряде случаев цикл с постусловием или цикл с параметром делают решение задачи легче.

Примером решения одной и той же задачи с помощью различных циклов может служить задача возведения некоторого числа a в натуральную степень n.