Информатика

Урок 5: Конструкции алгоритма

Алгоритмические конструкции

На сегодняшнем уроке поговорим о базовых и вспомогательных алгоритмах.

План урока:

Базовые алгоритмы

Вспомогательные алгоритмы

 

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

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

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

 

Базовые алгоритмы

Не так давно, 40 лет назад, ученые пришли к выводу, что существует 3 типа решения логических задач. Используя их по отдельности или комбинируя, можно одолеть любое по сложности логическое задание. Эти 3 структуры, подходы, назвали базовыми.

Основные алгоритмические конструкции:

1 algoritmicheskie konstrukcii

 

Следование

Является простейшей и самой распространенной из 3 базовых структур. Постоянно используется для решения бытовых и научных задач.

2 algoritmicheskie konstrukcii
Плакат для детского сада с линейным алгоритмом

Особенности алгоритмической конструкции следование:

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

Поэтому, такие решения называют линейными или простыми алгоритмами действий.

 

 3 algoritmicheskie konstrukcii
Пример использования линейного алгоритма для записи рецепта Источник

 

 

Ветвление

Если решение задачи может меняться в зависимости от определенного условия, появляется «если», возникает необходимость в разветвлении хода решения, в одном случае будет один перечень команд, в другом – иной. Таким образом, это конструкция с несколькими альтернативными блоками команд, выбор того или иного пути зависит от выполнения условий/значения входных данных.

4 algoritmicheskie konstrukcii
Мама дает указание, как попасть на представление Источник

Чтобы кратко записать условие, используют операции сравнения: >, < или =, логические связки (и, или, не). Для универсализации переменные обозначают большими латинскими буквами.

Если в задаче одно сравнение, то это простое условие, а если несколько – составное, сложное.

Особенности алгоритмической конструкции ветвления:

  • не линейная;
  • выполняемые команды будут зависеть от входных данных, есть от того, выполняется ли указанное условие (вопрос, на который есть ответ «да/нет»);
  • есть полная и неполная форма ветвления.

Алгоритмы решения на базе такой структуры называют разветвляющимися.

В неполной форме решение будет выполняться, только если условие истинно, иначе задача прекратится. В такой конструкции процесс продолжается только при положительном условии («если – то»). При отрицательном результате для условия процесс заканчивается.

5 algoritmicheskie konstrukcii

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

Пример решения одной задачи при помощи полной (а) и неполной (б) форм:

6 algoritmicheskie konstrukcii
Нахождение модуля числа 

Использование структуры разветвления в обучающих материалах для детей:

7 algoritmicheskie konstrukcii
Плакат, как правильно себя вести, если расстроен или зол Источник

 

Повторение

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

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

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

  • Продолжения выполнения цикла (цикл-пока или конструкция с предусловием).
  • Окончания работы алгоритма (цикл-до или структура с постусловием).
  • Заданное число повторений (с параметром).

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

8 algoritmicheskie konstrukcii
 

 

Цикл с предусловием

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

9 algoritmicheskie konstrukcii

Если с самого начала программы условие не выполняется, цикл не выполнится ни разу. Если же условие истинно всегда, может случиться бесконечный повтор, то есть зацикливание, поэтому, для большинства задач нужно указать условие окончания цикла.

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

 

Цикл с постусловием

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

10 algoritmicheskie konstrukcii

В таких заданиях также возможно зацикливание, если не корректно сформулировать условие выхода.

Схемы циклических алгоритмов на примерах:

11 algoritmicheskie konstrukcii
 

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

 

Цикл с параметром

Частный вид конструкций, подходит для ситуаций, когда известно число повторений того или иного действия.

12 algoritmicheskie konstrukcii

Параметр или счетчик цикла – величина, которая изменяется на определенный шаг с каждым выполнением команд. Параметр имеет исходное значение, он является целым числом, в процессе выполнения параметр постоянно сравнивается с условием, пока не достигнет указанного максимума. Шаг=1 не пишут, это значение по умолчанию. Благодаря счетчику в таких программах нет зацикливания.

На этом популярном ныне плакате указан линейный алгоритм выполнения гигиенической процедуры. Но в конце мы видим указанием на повтор выполняемых действий – повторить этапы для второй руки. Если бы процесс описывался в виде блок-схемы, очистка одной руки была бы выделена в отдельное тело цикла с указанием количества раз – 2 раза, по 1 разу для каждой руки.

13 algoritmicheskie konstrukcii
 

Еще гигиенический пример – чистить зубы 3 минуты, то есть выполнять очищающие движения по наружной и внутренней стороне зубов, пока не истечет указанное время. Можно указать, сколько раз нужно пройтись по каждому зубу (приблизительно по 10 движений в одной точке), но так сложнее – количество зубов, их размеры отличаются у людей разного возраста, как и скорость движений.

Разные циклические алгоритмы на примере произведения чисел 1…5:

Матмодель Р=1*2*3*4*5

14 algoritmicheskie konstrukcii
Источник

 

Вспомогательные алгоритмы

Зная и понимая, как работают базовые структуры, пользователь может строить более сложные конструкции. Для этого используют последовательное соединение, вложение (составные команды). Сложные алгоритмы могут расти как в длину, так вширь (цепочки дополняются новыми блоками) или вглубь (одни конструкции встраиваются в другие).

Если какой-то сложный блок алгоритма повторяется на нескольких участках, его можно вынести отдельно, как отдельную подструктуру (процедуру или подпрограмму). Другое название – вспомогательный или подчиненный алгоритм. После того, как такому блоку дается название, в алгоритм вставляется не вся его конструкция, а только название. Это значительно уменьшает размеры основного составного алгоритма.

 

ВОПРОСЫ И ЗАДАНИЯ

Вопрос: 1
Рассмотрите блок-схему. Какая алгоритмическая конструкция использовалась?

15 algoritmicheskie konstrukcii

1С предусловием
2С постусловием
3С параметром
Ответить
1
Вопрос: 2
Ознакомьтесь с примером алгоритма. Какой тип ветвления на ней представлен?

16 algoritmicheskie konstrukcii

1Полное ветвление
2Неполное ветвление
3Цикл с параметром
Ответить
2
Вопрос: 3
В каких алгоритмах выполнение команд зависит от условия:
1В разветвленных и циклических (если цикл с условием)
2В разветвлениях
3Во всех циклических
Ответить
1
Вопрос: 4
Какие алгоритмы описывают последовательное описание команд:
1Циклические
2Ветвления
3Линейные
Ответить
3
Вопрос: 5
Подчеркните лишнее слово:
1Алгоритм
2Счетчик
3Вирус
4Задача
5Цикл
Ответить
3
Вопрос: 6
Подчеркните лишнее слово:
1Повторение
2Действие
3Экран
4Шаг
Ответить
3
Вопрос: 7
Подчеркните лишнее слово:
1Текст
2Домен
3Команда
4Условие
5Блок-схема
Ответить
2
Допущено ошибок:
Оценка:
Подробнее
Ваши ответы:
1 вопрос:

Рассмотрите блок-схему. Какая алгоритмическая конструкция использовалась?

15 algoritmicheskie konstrukcii


1) С предусловием 2) С постусловием 3) С параметром
2 вопрос:

Ознакомьтесь с примером алгоритма. Какой тип ветвления на ней представлен?

16 algoritmicheskie konstrukcii


1) Полное ветвление 2) Неполное ветвление 3) Цикл с параметром
3 вопрос:

В каких алгоритмах выполнение команд зависит от условия:
1) В разветвленных и циклических (если цикл с условием) 2) В разветвлениях 3) Во всех циклических
4 вопрос:

Какие алгоритмы описывают последовательное описание команд:
1) Циклические 2) Ветвления 3) Линейные
5 вопрос:

Подчеркните лишнее слово:
1) Алгоритм 2) Счетчик 3) Вирус 4) Задача 5) Цикл
6 вопрос:

Подчеркните лишнее слово:
1) Повторение 2) Действие 3) Экран 4) Шаг
7 вопрос:

Подчеркните лишнее слово:
1) Текст 2) Домен 3) Команда 4) Условие 5) Блок-схема
Посмотреть ответы
Правильные ответы:
1 вопрос: С предусловием
2 вопрос: Неполное ветвление
3 вопрос: В разветвленных и циклических (если цикл с условием)
4 вопрос: Линейные
5 вопрос: Вирус
6 вопрос: Экран
7 вопрос: Домен