Обобщение и повторение.
Формы записи алгоритмов.
Типы алгоритмов.
Чтобы составить алгоритм, необходимо знать систему команд предполагаемого исполнителя, правила записи отдельных команд и всего алгоритма в целом.
Последовательность шагов, которые выполняются человеком при решении некоторой задачи, удобно записывать в виде нумерованного списка (словесная форма), графически с помощью блок-схемы.
Словесная форма - последовательность шагов, которые выполняются исполнителем, записывается в форме нумерованного списка. (1.2.3 … n).
Для обозначения шагов алгоритма используются следующие геометрические фигуры:
Таблица 1 – Фигуры (блоки) блок-схемы
Название фигуры | Изображение | Обозначаемое действие (шаг) алгоритма |
Овал | Начало или конец | |
Параллелограмм | Ввод или вывод | |
Ромб | Условие для принятия решения о выполнении действия | |
Прямоугольник | Выполняемое действие |
Последовательность действий указывается с помощью стрелок, соединяющих фигуры, обозначающие шаги алгоритма. Вот так, например, с помощью блок-схемы можно представить алгоритм действия человека при выполнении домашнего задания.
Рисунок 1 – Пример блок-схемы
Алгоритм, записанный на языке, понятном исполнителю, называется программой.
Алгоритм разрабатывается для решения некоторого класса задач. При этом:
1) выделяются объекты, устанавливаются их свойства, отношения между ними, возможные действия с объектами;
2) определяются исходные данные и результат;
3) определяется точная последовательность действий исполнителя для перехода от исходных данных к результату;
4) действия описываются командами, понятными исполнителю.
Линейные алгоритмы
Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным. Например, линейным является алгоритм приготовления бутерброда:
1. Отрезать ломтик хлеба
2. Намазать хлеб маслом
3. Отрезать ломтик сыра
4. Положить сыр на хлеб
С помощью блок-схемы данный алгоритм можно изобразить так:
Рисунок 2 – Пример блок-схемы линейного алгоритма
Алгоритм с ветвлениями
В жизни часто приходится принимать решение в зависимости от сложившейся обстановки. Если идёт дождь, мы берём зонт и надеваем плащ; если жарко, надеваем лёгкую одежду. Встречаются и более сложные условия выбора. В некоторых случаях от выбранного решения зависит дальнейшая судьба человека.
Логику принятия решения можно описать так:
ЕСЛИ <условие> ТО <действия 1> ИНАЧЕ <действия 2> - полное ветвление.
Пример: Алгоритм действия человека при открытии входной двери (когда позвонили в звонок)
Подойти к двери
Спросить кто там?
Если человек знакомый
Открыть дверь
Иначе не открывать
В некоторых случая <действия 2> могут отсутствовать.
ЕСЛИ <условие> ТО <действия 1> - не полное ветвление.
Форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий, называется ветвлением.
Изобразим алгоритм действия человека при открытии входной двери (когда позвонили в звонок) в виде блок-схемы:
| |||
Да
Рисунок 3 – Пример блок-схемы неполного ветвления
Рисунок 4 – Пример полного ветвления
Алгоритм с повторением
На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз, пока соблюдается некоторое заранее установленное условие.
Алгоритм с повторением или цикл - форма организации действий, при которой выполнение одной и той же последовательности команд повторяется, пока выполняется некоторое заранее установленное условие.
Алгоритм с ветвлениями или разветвляющийся алгоритм - форма организации действий, при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов.
Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием. Следует разрабатывать алгоритмы, не допускающие таких ситуаций.
Рисунок 5 – Пример алгоритма с повторением
Цикл будет повторяться ровно столько раз, пока туфелька не подойдет золушке.
Система программирования КуМир. Исполнитель Водолей
Интересный исполнитель водолей, в котором мы можем заниматься переливаниями. Те у нас есть сосуды каких-то размеров и нам нужно решить задачу, в которой нас просят, например оставить в одном из сосудов определенное количество литров.
Команды действий
алг наполни A (Наполняет колбу А)
алг наполни В (Наполняет колбу В)
алг наполни С (Наполняет колбу С)
алг вылей A (Выливает всю жидкость из колбы А)
алг вылей В (Выливает всю жидкость из колбы В)
алг вылей С (Выливает всю жидкость из колбы С)
алг перелей из A в B (Переливает жидкость из колбы А в колбу В до тех пор, пока не случится одно из событий (или оба одновременно):
- жидкость в колбе А закончилась,
- колба В заполнилась.
алг перелей из A в C (Переливает жидкость из колбы А в колбу C до тех пор, пока не случится одно из событий (или оба одновременно):
- жидкость в колбе А закончилась,
- колба C заполнилась.
алг перелей из B в A (Переливает жидкость из колбы B в колбу A до тех пор, пока не случится одно из событий (или оба одновременно):
- жидкость в колбе B закончилась,
- колба A заполнилась.
алг перелей из B в C (Переливает жидкость из колбы B в колбу C до тех пор, пока не случится одно из событий (или оба одновременно):
- жидкость в колбе B закончилась,
- колба C заполнилась.
алг перелей из C в A (Переливает жидкость из колбы C в колбу A до тех пор, пока не случится одно из событий (или оба одновременно):
- жидкость в колбе C закончилась,
- колба A заполнилась.
алг перелей из C в B(Переливает жидкость из колбы C в колбу В до тех пор, пока не случится одно из событий (или оба одновременно):
- жидкость в колбе C закончилась,
- колба В заполнилась.
Видеоурок по работе с данным исполнителем вы найдете по ссылке:
https://youtu.be/bFL0r-7E3VY
Давайте перейдем к примеру:
У нас есть три сосуда, 8,5 и 3 литра, и нам нужно перелить так, чтобы было 4 литра. Зеленым отмечено.
Домашняя работа
1. Повторить материал с 1 по 4 страницу;
2. Поработать в системе программирования КуМир с исполнителем Водолей (прислать результаты работы, на оценку).