Презентация "Базовые алгоритмические конструкции"

Базовые алгоритмические конструкции Из истории

Э́дсгер Ви́бе Де́йкстра (1930 – 2002)

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

В 1969 году доказал, что для записи любого алгоритма достаточно всего трех базовых алгоритмических конструкций:

• Следование
• Ветвление
• Цикл

Эта теория легла в основу структурного программирования,

одним из авторов которого был Эдсгер Вибе Дейкстра.

Виды алгоритмических конструкций и названия алгоритмов

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

Следование

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

Ветвление

• Циклический алгоритм

Повторение

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

Действие 1

Действие 2

Действие n

Алгоритм, в основе которого лежит конструкция

«следование», называется линейным.

Формат блока:

нач

<Действие_1>

<Действие_2>

. . .

<Действие_n>

кон

. . .

Конец

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

Начало

Примеры линейного алгоритма для исполнителя Робот

Задание: создать для исполнителя Робот линейный алгоритм с помощью блок-схемы и на школьном

алгоритмическом языке, исполняя который Робот нарисует на поле следующий узор и вернется в

исходное положение.

Начало

Конец

Вниз, закрасить

Вправо, закрасить

Вправо, закрасить

Влево

Вниз, закрасить

Вверх

Влево, закрасить

Вверх

Ветвление – алгоритмическая конструкция, в которой в зависимости от результата проверки условия («да» или «нет») предусмотрен выбор одной из двух последовательностей действий (ветвей):

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

Условие

Действие 1

Действие 2

Условие

Действие 1

да

нет

нет

да

Полная форма ветвления

Неполная форма ветвления

Формат блока:

нач

если <Условие>

то <Действие_1>

иначе <Действие_2>

все

кон

Формат блока:

нач

если <Условие>

то <Действие_1>

все

кон

Примеры разветвляющихся алгоритмов для исполнителя Робот

Справа свободно

• Вправо
• Закрасить

• Вниз
• Вправо
• Вверх
• Закрасить

да

нет

Задание: создать для исполнителя Робот алгоритм с помощью блок-схемы и на школьном

алгоритмическом языке, исполняя который Робот закрасит отмеченную клетку и не врежется в стену.

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

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

Тело цикла – это последовательность действий, повторяющихся многократно.

Единичное выполнение тела цикла называется итерацией.

Виды циклов Цикл с предусловием (Цикл – ПОКА, while – цикл) - цикл, который выполняется, пока истинно условие, указанное перед его началом.

Условие

Тело цикла

да

нет

Формат блока:

нц пока <условие>

<тело цикла> (последовательность действий)

кц

Если условие с самого начала ложно, то тело цикла может быть

не выполнено ни разу!

Пример цикла с предусловием для исполнителя Робот

Задание: создать для исполнителя Робот алгоритм с помощью блок-схемы и на школьном

алгоритмическом языке, исполняя который Робот закрасит отмеченные клетки по диагонали и не врежется в стену. Количество закрашиваемых клеток не известно.

снизу свободно

• Вниз
• Закрасить
• Вправо

да

нет

Виды циклов Цикл с постусловием (Цикл – До) - цикл, в котором условие проверяется после выполнения тела цикла.

Условие

Тело цикла

да

нет

Формат блока:

нц

<тело цикла> (последовательность действий)

кц при <условие>

Тело цикла всегда выполняется хотя бы один раз!

Пример цикла с предусловием для исполнителя Робот

Задание: создать для исполнителя Робот алгоритм с помощью блок-схемы и на школьном

алгоритмическом языке, исполняя который Робот закрасит отмеченные клетки по диагонали и не врежется в стену. Количество закрашиваемых клеток не известно.

Снизу стена

• Вниз
• Закрасить
• Вправо

да

нет

Виды циклов Цикл с параметром (цикл со счетчиком, цикл – Для) – цикл с заданным числом повторений. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.

Формат блока:

нц для i от iнач до iкон

<тело цикла> (последовательность действий)

кц

Тело цикла

Счетчик

i:= iнач, iкон

Пример цикла с параметром для исполнителя Робот

Задание: создать для исполнителя Робот алгоритм с помощью блок-схемы и на школьном

алгоритмическом языке, исполняя который Робот закрасит отмеченные клетки.

• Вниз
• Закрасить
• i := i + 1

i:= 1, 7