Конспект урока: Конструирование алгоритмов

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

Исполнитель — это объект (живой организм (неформальный исполнитель) или техническое устройство (формальный исполнитель)), который выполняет заданный алгоритм.

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

Алгоритм метода последовательного построения алгоритма:

1. Определение исходных данных и результатов, которые должны быть получены. На данном этапе считается, что исполнитель — это идеальный объект, который может решить любую задачу.
2. Проверка выполнимости исполнителем конкретной задачи. Если исполнитель не может выдать ответ на задачу, то разбить задачу на несколько действий (частей). Если и теперь исполнитель снова не может выполнить поставленную задачу, нужно продолжить упрощение алгоритма — разбить части задачи на ещё более простые. Так нужно поступать до тех пор, пока все части задачи не станут понятны конкретному исполнителю.
3. Объединение полученных частей задачи для получения алгоритма, решающего конкретную задачу. 

Исполнитель Робот — это формальный исполнитель, деятельность которого осуществляется на клетчатом поле, где он может перемещаться, обходя препятствия (стены).

Задача 1

Имеется бесконечное клетчатое поле, размеры которого неизвестны. Внутри поля в произвольном месте располагаются две стены, соединённые под углом 90 градусов. Робот располагается в клетке, которая направлена вправо. 

На рис. 1 показан возможный способ расположения стен и Робота (Робот обозначен ромбом).

Создайте алгоритм, закрашивающий все клетки, расположенные правее вертикальной стены, выше горизонтальной стены и примыкающие к ним, кроме угловой клетки. Например, для приведённого рисунка Робот должен закрасить следующие клетки (рис. 2).

Рис. 1. Возможное расположение Робота и стен

Конечное положение Робота — произвольное. Алгоритм должен решать задачу для произвольного размера поля и любого допустимого расположения стен внутри прямоугольного поля. При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться.

Рис. 2. Пример результата выполнения программы Роботом

Решение

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

Представим решение задачи линейным планом действий, предполагая, что исполнитель Робот является идеальным (рис. 3)

Рис. 3. Линейный алгоритм

2. Начнём написание программы с операции Вставка -> использовать Робот (рис. 4)

Рис. 4. Заготовка программы

3. Создадим стартовую обстановку как на рис. 1 (Робот -> Редактировать стартовую обстановку). С помощью нажатия на границы ячеек расставим стены и переместим Робота на нужную позицию, взятую также из рис. 1. Созданную стартовую обстановку сохраним под названием Обстановка задания 1.fil (рис. 5).

Рис. 5. Создание стартовой обстановки

4. Выполним сохранение новой программы под названием Задание 1 в папку, где находится файл Обстановка задания 1.fil. 

5. Детализируем все 3 пункта, описанные в рис. 3.

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

Рис. 6. Закрашивание клеток стены

7. Смещение на одну клетку вверх вне цикла позволит осуществить переход без закрашивания клетки (рис. 7).

Рис. 7. Пропуск одной незакрашенной клетки (вне цикла)

8. Теперь проверим несвободность слева, закрасим и сместимся вверх (рис. 8) 

Рис. 8. Закраска вертикальной стены

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

Рис. 9. Программа к задаче 1

Пример работы программы представлен на рис. 10.

Рис. 10. Пример работы программы к задаче 1

Чтобы подобные программы работали корректно, следует загружать нужные стартовые обстановки (Робот -> Загрузить обстановку).

Вспомогательный алгоритм (подпрограмма) — это алгоритм, целиком применяемый другим алгоритмом.

Задача 2

Создать программу для исполнителя Робот с использованием вспомогательного алгоритма Узор (рис. 11).

Рис. 11. Рисунок к условию задачи 2

Решение

1.  Чтобы наглядно показать отличия программы, написанной с использованием вспомогательного алгоритма и без неё, сравним две программы.

2. Программа, написанная без использования вспомогательного алгоритма (рис. 12).

Рис. 12. Программа без вспомогательного алгоритма

3. Программа, написанная с использованием вспомогательного алгоритма (рис. 13).

Рис. 13. Программа с вспомогательным алгоритмом

Рекурсивный алгоритм — это алгоритм, вызывающий себя непосредственно или через другие алгоритмы.

Решение

1. Известно, что факториал вычисляется путём умножения всех чисел от одного до значения самого числа под факториалом.

2. В нашем случае, чтобы найти 5!, можно записать следующее решение:

1! = 1,

2! = 1 × 2 = 2,

3! = 1 × 2 × 3 = 6,

4! = 1 × 2 × 3 × 4 = 24,

5! = 1 × 2 × 3 × 4 × 5 = 120. 

3. Граф, представленный на рис. 15, — процесс решения задачи, описанный в пункте 2.

Рис. 15. Дерево решений факториала 5!

4. Представим решение задачи с помощью блок-схемы (рис. 16).

Рис. 16. Блок-схема решения задачи 2

В дальнейшем, опираясь на блок-схему, можно написать программу для нахождения факториала числа. 

Контрольные вопросы

1. Перечислите команды-действия исполнителя Робот в среде КуМир.
2. Перечислите команды-условия исполнителя Робот в среде КуМир.
3. Чем отличается конструкция полного ветвления от неполного ветвления?
4. В чём заключается принципиальное отличие цикла со счётчиком от цикла с условием? В каких случаях следует применить каждый из них?
5. Какой алгоритм называется рекурсивным? Когда следует применять рекурсивный алгоритм?