Как поступить
в Онлайн-школу и получить аттестат?

Подробно расскажем о том, как перевестись на дистанционный формат обучения, как устроены онлайн-уроки и учебный процесс, как улучшить успеваемость и повысить мотивацию!

Нажимая на кнопку, я соглашаюсь на обработку персональных данных

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

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

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

 

План занятия

 

  • Введение в тему.
  • Последовательное построение алгоритма.
  • Разработка алгоритма методом последовательного уточнения для исполнителя Робот.
  • Вспомогательные алгоритмы.

 

Цели занятия

 

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

 

Разминка

 

  • Что такое алгоритм?
  • Какие существуют формы представления алгоритмов?

 

 

Введение в тему

 

Тему «Конструирование алгоритмов» составляют важные разделы информатики, знание которых позволяет лучше понимать процессы алгоритмизации и способствует осознанному изучению программирования. 

 

Умение последовательно уточнять решение задачи способствует развитию алгоритмического мышления.  Понимание вспомогательных алгоритмов поможет в решении сложных практических задач.

 

Последовательное построение алгоритма


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

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

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


Другие названия метода последовательного построения алгоритма: «пошаговая детализация», «программирование сверху вниз», «нисходящее программирование».


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

 

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


Рассмотрим пример разработки алгоритма методом последовательного уточнения для исполнителя Робот.

 

Разработка алгоритма методом последовательного уточнения для исполнителя Робот


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


 

Система команд исполнителя Робот в среде КуМир (комплект учебных миров) можно разделить на 2 группы:

 

1. Команды-действия (Таблица 1).

 

Таблица 1. Команды-действия исполнителя Робот в среде КуМир

 

2. Команды-условия (Таблица 2). 

 

Таблица 2. Команды-условия исполнителя Робот в среде КуМир

 

Реализация ветвлений:

 

1. Полное ветвление. 

 

Общий вид конструкции полного ветвления:

 

если «условие»

то «команда 1»

иначе «команда 2»

все

 

2. Неполное ветвление.

 

Общий вид конструкции неполного ветвления:

 

если «условие»

то «команда»

все

 

Реализация циклов:

 

1. Цикл со счетчиком (применяется когда заранее известно количество повторений).

 

Общий вид конструкции цикла со счетчиком:

 

нц «количество повторений» раз

«команда 1»

«команда 2»

«команда n»

кц

 

2. Цикл с условием (применяется для проверки истинности условия).

 

Общий вид конструкции цикла с условием:

 

нц пока «условие» 

«последовательность команд»

кц

 

В одном условии можно применять несколько команд, используя логически связки И, ИЛИ, НЕ.

 

Рассмотрим пример разработки алгоритма методом последовательного уточнения для исполнителя Робот.


Задача 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. Вспомогательный алгоритм имеет имя, по которому к нему обращаются в основной программе.


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


Для простого примера рекурсию можно представить следующим образом (Рис. 14):

Рис. 14. Наглядный пример рекурсии

 

Рассмотрим пример задачи, которую можно решить построением рекурсивного алгоритма.

 


Задача 3. Найти факториал 5!

 

Решение:

 

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. Какой алгоритм называется рекурсивным? Когда следует применять рекурсивный алгоритм?


Предыдущий урок
Цели изучения курса информатики. Техника безопасности и организация рабочего места
Общие понятия и основы информатики
Следующий урок
Одномерные массивы целых чисел. Описание, заполнение, вывод массива
Алгоритмы и программирование
  • Северо-Западный район: географическое положение и природа. Города на старых водных торговых путях

    География

  • Сложноподчиненное предложение. Виды СПП. Повторение

    Русский язык

  • Уголовно-правовые отношения

    Обществознание

Зарегистрируйся, чтобы присоединиться к обсуждению урока

Добавьте свой отзыв об уроке, войдя на платфому или зарегистрировавшись.

Отзывы об уроке:
Пока никто не оставил отзыв об этом уроке