Тема 8 · Информатика
Алгоритмы и исполнители
Свойства алгоритма, способы записи, блок-схемы, формальные исполнители Робот и Черепашка. 100 заданий на отработку.
Простыми словами
Навигатор говорит: «200 метров прямо, затем направо». Водитель не думает, зачем, — просто выполняет. Так же работает компьютер: он выполняет команды формально, не вникая в смысл задачи. Поэтому алгоритм должен быть точным.
Алгоритм — понятное и точное предписание исполнителю выполнить последовательность действий, приводящую к решению задачи. Система команд исполнителя (СКИ) — все команды, которые он умеет выполнять.
Пять свойств алгоритма
| Свойство | Смысл |
|---|---|
| Дискретность | состоит из отдельных шагов |
| Понятность | команды входят в систему команд исполнителя |
| Определённость | каждый шаг понимается однозначно |
| Результативность | заканчивается результатом за конечное число шагов |
| Массовость | применим к разным исходным данным |
«ДПОРМ»: Дискретность, Понятность, Определённость, Результативность, Массовость — всего 5 свойств.
Способы записи и блок-схема
Алгоритм записывают словесно, в виде блок-схемы или на языке программирования.
Формальные исполнители
Робот ходит по клетчатому полю (команды «вверх», «вниз», «влево», «вправо»), Черепашка рисует линии («вперёд n», «направо k°»), Чертёжник перемещает перо по координатам. Команда, которой нет в СКИ, или невыполнимая команда (шаг в стену) приводит к отказу.
Робот выполняет «вправо» 4 раза, затем «вверх» 1 раз.
- По горизонтали двигают только «вправо»/«влево»: смещение клетки.
- По вертикали: клетка вверх.
- Всего команд: .
Команды в разные стороны взаимно уничтожаются: «вправо» 3 раза и «влево» 1 раз дают смещение клетки, хотя команд выполнено . Не путайте «сколько команд» и «на сколько клеток».
Черепашка и команда «повтори»
Запись повтори [вперёд направо ] — цикл: тело в скобках выполняется раз. Каждое выполнение рисует один отрезок длины , значит отрезков , а длина всей линии .
Если , Черепашка возвращается в начало и рисует правильный -угольник: — треугольник, — квадрат, — пятиугольник, — шестиугольник. Его периметр .
«повтори 5 [вперёд 3 направо 72]». Что получится и каков периметр?
- — фигура замкнётся: правильный пятиугольник.
- Периметр: .
Расстояние от старта до конца пути считают по теореме Пифагора: «вперёд 5, направо 90, вперёд 5» — катеты 5 и 5, расстояние .
Исполнитель-вычислитель
У исполнителя может быть система команд из действий над числом, например «прибавь 1» и «умножь на 2». Программа — последовательность таких команд.
Наименьшее число команд, чтобы из 1 получить 4.
- Удобно идти от конца: 4 чётное — получено умножением из 2; 2 — умножением из 1.
- — 2 команды.
Если команда одна, например «прибавь 3», число команд — частное: из 0 в 12 нужно команды.
В линейном алгоритме нет условий и повторений: выполняются все шаги по порядку, по одному разу. Число маршрутов Робота «только вправо и вверх» в клетку на 1 правее и 1 выше — 2: «вправо, вверх» или «вверх, вправо».
Готовые работы по теме
Собраны заранее — одним нажатием: распечатать с ключом, раздать ученикам ссылкой или QR-кодом, поменять настройки. Номер набора постоянный: по этой ссылке всегда та же работа.
теория этой темы, 8 заданий по подтемам и ключ — файлом DOCX, который можно править под себя.
Прохождение онлайн
Имя ученика никуда не отправляется: он вводит только номер по списку, а таблицу «номер → фамилия» видите только вы.
Классы, выданные работы и результаты учеников по кодам — в журнале учителя: без регистрации, хранится только на этом компьютере.