Управление исполнителями

1. Управление исполнителями

§ 29. Алгоритмы и исполнители
§ 30. Способы записи алгоритмов
§ 31. Примеры исполнителей
§ 32. Оптимальные программы
§ 33. Линейные алгоритмы
§ 34. Вспомогательные алгоритмы
§ 35. Циклические алгоритмы
§ 36. Переменные
§ 37. Циклы с условием
§ 38. Разветвляющиеся алгоритмы
§ 39. Ветвления и циклы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
1

2. Управление исполнителями

2
Управление
исполнителями
§ 29. Алгоритмы и исполнители
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Что такое алгоритм?

Алгоритмы и программирование, 7 класс
3
Что такое алгоритм?
Алгоритм – это порядок выполнения
действий.
Исполнитель – это устройство или
одушевлённое существо (человек),
способное понять и выполнить
команды, составляющие алгоритм.
Формальные исполнители: не понимают
Мухаммед ал-Хорезми
(и не могут понять) смысл команд.
(ок. 783–ок. 850 гг.)
Алгоритм — это точное описание порядка действий
некоторого исполнителя.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

4. Исполнитель Робот

Алгоритмы и программирование, 7 класс
4
Исполнитель Робот
стенка
Среда — это обстановка, в которой
работает исполнитель.
Система команд исполнителя (СКИ):
вверх
вправо
вниз
влево
Состояние исполнителя:
? Какие команды может
выполнить Робот?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Свойства алгоритма

Алгоритмы и программирование, 7 класс
5
Свойства алгоритма
Дискретность — алгоритм состоит из отдельных команд,
каждая из которых выполняется ограниченное (не
бесконечное) время.
Понятность — алгоритм содержит только команды,
входящие в систему команд исполнителя.
Определённость — при каждом выполнении алгоритма
с одними и теми же исходными данными должен быть
получен один и тот же результат.
! Если какое-то свойство нарушено,
это не алгоритм!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Необязательные свойства алгоритма

Алгоритмы и программирование, 7 класс
6
Необязательные свойства алгоритма
? Конечность (результативность) — для корректного
набора данных алгоритм должен заканчиваться с
некоторым результатом (не зацикливаться).
? Корректность — для допустимых исходных данных
алгоритм должен приводить к правильному результату.
? Массовость — алгоритм можно использовать для
решения множества однотипных задач с различными
исходными данными (решение «в буквах»).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Одна задача – много алгоритмов

Алгоритмы и программирование, 7 класс
7
Одна задача – много алгоритмов
Задача. Вычислите
S = 1 + 2 + 3 + 4 + 5 + … + 99 + 100
? Как можно вычислять?
Решение К.Ф. Гаусса:
1 + 100 = 2 + 99 = 3 + 98 = …
= 50 + 51 = 101
S = 50 · 101 = 5050
? Какой алгоритм лучше? Почему?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Управление исполнителями

Алгоритмы и программирование, 7 класс
8
Управление исполнителями
Ручное (непосредственное, «с пульта»):
! Можно и без плана!
Программное (по готовой программе):
бортовой
компьютер
Программа — это алгоритм,
записанный на языке, понятном
компьютеру.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

9. Управление исполнителями

9
Управление
исполнителями
§ 30. Способы записи
алгоритмов
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Алгоритм «О»

Алгоритмы и программирование, 7 класс
10
Алгоритм «О»
Словесная форма:
Даны два натуральных числа. Пока первое число не
меньше второго, заменять его на разность первого и
второго. Результат работы алгоритма — полученное
первое число.
a
b
Исходные данные
5
2
Шаг 1
3
2
Шаг 2
1
2
? Меняется ли b?
неоднозначность естественных языков
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Алгоритм «О»

Алгоритмы и программирование, 7 класс
11
Алгоритм «О»
По шагам:
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Заменить a на a – b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Алгоритм «О»

Алгоритмы и программирование, 7 класс
12
Алгоритм «О»
Блок-схема:
Условные обозначения
начало
начало и конец алгоритма
a, b
a < b?
ввод и вывод данных
да
нет
условие (выбор)
операции с данными
a a–b
присвоить a
значение a – b
a
конец
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

13. Переменные

Алгоритмы и программирование, 7 класс
13
Переменные
Переменная — это величина, значение которой можно
изменять во время работы алгоритма.
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Заменить a на a – b.
a a–b
Шаг 3. Перейти к шагу 1.
или
Шаг 4. Стоп.
a := a – b
Результат: значение a.
присваивание
значения
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

14. Управление исполнителями

14
Управление
исполнителями
§ 32. Оптимальные программы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

15. Составление программы

Алгоритмы и программирование, 7 класс
15
Составление программы
Используя команды:
1. прибавь 1
2. умножь на 2
написать самую короткую программу, которая из 6
получает 28.
дерево
6
вариантов
14
28
15
26
13
14
16
8
12
7
9
25
24
1
2
48
6
Ответ: 122
7
1
12
2
1
14
8
2
13
24
1
2
1
2
1
2
1
2
9
16
15
28
14
26
25
48
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

16. Составление программы (с конца)

Алгоритмы и программирование, 7 класс
16
Составление программы (с конца)
Ответ: 122
28
2
1
27
нельзя
делить
на 2!
25
26
26
1
2
13
7
1
2
1
25
13
12
12
6
13
7
27
14
1
13
дерево
вариантов
1
6
14
28
? Почему решение
«с конца» короче?
! Решение «с конца» короче, если в списке команд
есть необратимая операция (каждое целое число
можно умножить на 2, но не каждое делится на 2)!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17. Управление исполнителями

17
Управление
исполнителями
§ 33. Линейные алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

18. Что такое линейный алгоритм?

Алгоритмы и программирование, 7 класс
18
Что такое линейный алгоритм?
В линейном алгоритме команды выполняются в том
порядке, в котором они записаны.
СКИ Робота:
закрасить
использовать Робот
алг Переход
нужно
подключить
нач
закрасить
исполнителя
вниз
закрасить
служебные
(зарезервированные)
влево
слова языка
закрасить
кон
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

19. Управление исполнителями

19
Управление
исполнителями
§ 34. Вспомогательные
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмы и программирование, 7 класс
20
Вспомогательные алгоритмы
Вспомогательный алгоритм решает отдельную
задачу и может быть использован при
решении более сложных задач.
• чтобы он выполнился, его нужно вызвать
функцию или процедуру
• возврат: после завершения его работы
управление передаётся следующей команде
вызывающего алгоритма
Сапог
вправо
К.Ю. Поляков, Е.А. Ерёмин, 2018
алг Сапог
нач
...
кон
http://kpolyakov.spb.ru

21. Два метода составления программ

Алгоритмы и программирование, 7 класс
21
Два метода составления программ
1. Последовательное уточнение
(«сверху вниз»)
сначала:
потом:
алг Два сапога
нач
Сапог
вправо; вправо
вправо
Сапог
кон
алг Сапог
нач
...
кон
выделили части задачи,
для которых будем
писать процедуру
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

22. Управление исполнителями

22
Управление
исполнителями
§ 35. Циклические алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

23. Что такое циклический алгоритм?

Алгоритмы и программирование, 7 класс
23
Что такое циклический алгоритм?
начало
цикла
конец
цикла
нц 6 раз
вправо
закрасить
кц
Цикл – это многократное
выполнение некоторой
последовательности
действий.
тело
цикла
? А если ряд из 6000 клеток?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

24. Блок-схема циклического алгоритма

Алгоритмы и программирование, 7 класс
24
Блок-схема циклического алгоритма
начало
сделали 6 раз?
цикл – возврат
к предыдущей
команде
да
нет
вправо
loop – петля
тело
цикла
закрасить
конец
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

25. Вложенные циклы

Алгоритмы и программирование, 7 класс
25
Вложенные циклы
Б
В
А
Вложенный цикл – это
цикл внутри другого
цикла.
нц 4 раз
| закрасить ряд
нц 6 раз
вправо
закрасить
кц
| к следующему ряду
вниз
нц 6 раз
влево
кц
кц
? Где остановится Робот?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

26. Управление исполнителями

26
Управление
исполнителями
§ 37. Циклы с условием
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

27. Что такое цикл с условием?

Алгоритмы и программирование, 7 класс
27
Что такое цикл с условием?
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Заменить a на a – b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
? Это цикл?
? Число повторений известно?
? Когда завершится? a < b
? При каком условии продолжается?
К.Ю. Поляков, Е.А. Ерёмин, 2018
a b
http://kpolyakov.spb.ru

28. Логические команды

Алгоритмы и программирование, 7 класс
28
Логические команды
Подойти к стене:
? Как управлять с пульта?
Что нужно уметь определять?
Логическая команда — это запрос, на который
исполнитель отвечает «да» или «нет».
логическое
сверху стена
сверху свободно
значение
справа стена
справа свободно
снизу стена
снизу свободно
слева стена
слева свободно
Обратная связь — это данные, которые передаются от
датчиков к управляющему устройству.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

29. Цикл с условием

Алгоритмы и программирование, 7 класс
29
Цикл с условием
Подойти к стене:
? А если нет
стенки?
алг До стены
нач
нц пока слева свободно
влево
кц
цикл выполняется,
кон
пока условие
истинно
Зацикливание — это ситуация, когда цикл
выполняется бесконечно.
? А если Робот рядом со стеной?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

30. Управление исполнителями

30
Управление
исполнителями
§ 38. Разветвляющиеся
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

31. Что такое разветвляющийся алгоритм?

Алгоритмы и программирование, 7 класс
31
Что такое разветвляющийся алгоритм?
Привести Робота в клетку Б
а)
б)
Б
Б
влево
вниз
? Как различить
два случая?
выполняется,
если условие
ложно
К.Ю. Поляков, Е.А. Ерёмин, 2018
вправо
вниз
условие
если слева свободно то
влево
выполняется,
вниз
если условие
иначе
истинно
вправо
вниз
все
http://kpolyakov.spb.ru

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

Алгоритмы и программирование, 7 класс
32
Разветвляющийся алгоритм
если слева свободно то
влево
вниз
иначе
вправо
вниз
все
начало
да
условие
действие 1
нет
действие 2
? Как улучшить?
если слева свободно то
влево
иначе
вправо
все
вниз
К.Ю. Поляков, Е.А. Ерёмин, 2018
конец
http://kpolyakov.spb.ru

33. Ветвление в неполной форме

Алгоритмы и программирование, 7 класс
33
Ветвление в неполной форме
а)
б)
? Как различить
Б
Б
вниз
влево
вниз
если слева свободно то
влево
все
вниз
иначе ничего
два случая?
начало
да
действие
условие
нет
пусто!
делать не нужно!
конец
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

34. Управление исполнителями

34
Управление
исполнителями
§ 39. Ветвления и циклы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмы и программирование, 7 класс
35
Базовые алгоритмические конструкции
Алгоритм решения любой задачи можно составить с
помощью трёх базовых конструкций — следования,
ветвления и цикла.
следование:
ветвление:
цикл:
начало
начало
начало
да
действие 1
действие 2
условие
действие 1
нет
действие 2
условие
да
тело цикла
нет
действие 3
конец
К.Ю. Поляков, Е.А. Ерёмин, 2018
конец
конец
http://kpolyakov.spb.ru

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

Алгоритмы и программирование, 7 класс
36
Цикл с постусловием
начало
? Может ли не выполниться
ни разу?
тело цикла
нет
условие
да
? Что происходит, если
условие истинно?
Пример: ввести число, которое
обязательно должно быть
положительным.
конец
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru