Управление исполнителями. § 29. Алгоритмы и исполнители

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

§ 29. Алгоритмы и исполнители

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

Алгоритм — это точное описание порядка действий некоторого исполнителя.

Исполнитель

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

стенка

Система команд исполнителя (СКИ):

вверх
вниз

вправо
влево

Состояние исполнителя:

Среда — это обстановка, в

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

Дискретность — алгоритм состоит из отдельных команд, каждая из которых

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

? Конечность (результативность) — для корректного набора данных алгоритм

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

Задача. Вычислите
S = 1 + 2 +

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

Ручное (непосредственное, «с пульта»):

Программное (по готовой программе):

бортовой компьютер

Программа — это

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

§ 30. Способы записи алгоритмов

Алгоритм «О»

Словесная форма:
Даны два натуральных числа. Пока первое число не меньше

Алгоритм «О»

По шагам:
Вход: два натуральных числа, a и b.
Шаг 1. Если

Алгоритм «О»

Блок-схема:

начало и конец алгоритма

ввод и вывод данных

условие (выбор)

операции с данными

начало

конец

a

Ручная прокрутка (трассировка)

Вход: два натуральных числа, a и b.
Шаг 1. Если

Переменные

Переменная — это величина, значение которой можно изменять во время работы

Языки программирования

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

101110000000111100000000
101110110000010000000000
0011101111000011
0111110000000100
0010101111000011
1110101111111000
1100110100100000

Алгоритм «О»:

сложно

Язык ассемблера

101110000000111100000000
101110110000010000000000
0011101111000011
0111110000000100
0010101111000011
1110101111111000
1100110100100000

mov ax, 15
mov bx, 4
m: cmp ax, bx

Языки высокого уровня

1) легко понимаются человеком
2) не «привязаны» к командам конкретного

Языки высокого уровня

1957: FORTRAN = FORmula TRANslator
для решения научных задач

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

§ 31. Примеры исполнителей

Формальный исполнитель

Формальный исполнитель — это исполнитель, который одну и ту же

Исполнитель Черепаха

вперед 30
вправо 90
вперед 30
вправо 90
вперед 30
вправо 90
вперед 30
вправо 90

градусов

повтори 4

Исполнитель Черепаха

повтори 4 [ вперед 30 вправо 45 ]

незамкнутая ломаная

повтори 45

Исполнитель Шифровальщик

Если цепочка символов начинается с гласной буквы, Шифровальщик переставляет последнюю

Исполнитель Шифровальщик

Если в цепочке символов чётное количество букв, Шифровальщик добавляет в

Исполнитель Шифровальщик

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

ПРИВЕТ ВАСЯ

А→Б

П→Р

РСКГЁУ ГБТА

Б→В

Я→А

Р→С

Шифр Цезаря

АВМПЛП

Расшифруйте:

НПСЛПГЭ

ЛМАЛТБ

← ЯБЛОКО

← МОРКОВЬ

← КЛЯКСА

Исполнитель Удвоитель

Работает с одним числом и умеет выполнять с ним две

Исполнитель Удвоитель

прибавь 1
умножь на 2

Какие числа можно получить?
при целом x ≥

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

§ 32. Оптимальные программы

Что такое оптимальная программа?

Оптимальная программа — это самая лучшая программа по

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

Используя команды:
1. прибавь 1
2. умножь на 2
написать самую

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

28

27

14

26

13

7

1

1

1

2

2

2

2

Ответ: 122

25

13

1

2

12

6

1

1

1

нельзя делить на 2!

дерево вариантов

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

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

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

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

Ошибки в программах

Синтаксические: исполнитель не понимает команду, так как она неверно

Ошибки в программах

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

вправо

столкновение со стенкой

При вычислениях: деление на 0.

Отладка – это

Вычислительные задачи

Задача. Сколько километров проехал автомобиль за 2 часа, если его

Вычислительные задачи

алг Путь
нач
вещ v, t, S
вывод "Введите скорость:

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

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

Зачем это нужно?

алг Два сапога
нач
Сапог
вправо; вправо
вправо
Сапог
кон

алг Сапог
нач

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

Вспомогательный алгоритм решает отдельную задачу и может быть использован при

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

1. Последовательное уточнение
(«сверху вниз»)

алг Два сапога
нач

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

2. «Снизу вверх» – сначала составить процедуры, потом

Проектирование «снизу вверх»

Сборка основной программы:

∙

∙

∙

∙

∙

∙

А

Б

В

Г

алг ТриПары
нач
влево; влево
вверх; вправо
Пара

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

§ 35. Циклические алгоритмы

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

Цикл – это многократное выполнение некоторой последовательности действий.

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

тело цикла

цикл – возврат к предыдущей команде

loop – петля

Выбор начального положения

нц 6 раз
вправо
закрасить
кц

в клетку Г

нц 6

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

нц 4 раз
| закрасить ряд
| к следующему ряду
кц

комментарии

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

нц 4 раз
| закрасить ряд
нц 6 раз
вправо

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

§ 36. Переменные

Зачем нужны переменные?

длина ряда – величина переменная

N

нц N раз
вправо
закрасить
кц
вниз
нц

Использование переменных

цел N
нц 4 раз
N:=2
нц N раз
вправо
закрасить

Процедуры с параметрами

алг Ряд(цел N)
нач
нц 4 раз
вверх
закрасить

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

§ 37. Циклы с условием

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

Вход: два натуральных числа, a и b.
Шаг

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

Подойти к стене:

Логическая команда — это запрос, на который исполнитель

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

Подойти к стене:

алг До стены
нач
нц пока слева свободно

закрасить

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

4 ряда неизвестной длины:

нц 4 раз
| подзадача 1
|

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

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

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

Привести Робота в клетку Б

влево
вниз

вправо
вниз

если слева свободно то

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

если слева свободно то
влево
вниз
иначе
вправо

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

вниз

влево
вниз

если слева свободно то
влево
все
вниз

иначе ничего

Вложенное ветвление

вверх

вниз

влево
вниз

если сверху свободно то а)

если снизу свободно то б)

Вложенное ветвление

если сверху свободно то
| работаем с задачей а

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

§ 39. Ветвления и циклы

Пример задачи

нц пока снизу свободно
если справа свободно то
вправо

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

Алгоритм решения любой задачи можно составить с помощью трёх

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

Пример: ввести число, которое обязательно должно быть положительным.

Анализ алгоритмов для Раздвоителя

нц пока N не ноль
вычти 1
кц

вычти 1
раздели

Конец фильма

ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
kpolyakov@mail.ru