11.1. Понятие алгоритма
|
| Алгоритм — понятная и конечная последовательность точных действий (команд), формальное выполнение которых позволяет получить решение поставленной задачи. Исполнитель алгоритма — человек, группа людей или техническое устройство, которые понимают команды алгоритма и умеют правильно их выполнять. Система команд исполнителя — команды, которые понимает и может выполнить исполнитель |
Любой исполнитель имеет ограниченную систему команд. Все они разделяются на группы:
- Команды, которые непосредственно выполняет исполнитель.
- Команды, меняющие порядок выполнения других команд исполнителя.
Компьютер является универсальным исполнителем.
| Запись алгоритма в виде последовательности команд, которую может выполнить компьютер, называют программой. |
Выделяют следующие способы представления алгоритмов (пример 11.1):
словесный способ (описание алгоритма средствами естественного языка с точной и конкретной формулировкой фраз);
графический способ (блок-схема) (графическое изображение команд алгоритма с использованием блоков в виде геометрических фигур, отрезков или стрелок, соединяющих эти блоки и указывающих на порядок выполнения команд);
программный способ (запись алгоритма в виде программы).
На практике могут применяться комбинации вышеперечисленных способов записи алгоритмов, а также другие способы представления: табличный, описание алгоритма с помощью математических формул, псевдокод (описание структуры алгоритма на частично формализованном языке).
11.2. Исполнитель Черепаха
В прошлом году вы познакомились с исполнителем Черепаха, который умеет строить рисунки и чертежи на координатной плоскости (пример 11.2).
Среда обитания исполнителя Черепаха – координатная плоскость (пример 11.2). Исходное положение Черепахи – точка с координатами (0, 0), перо опущено.
Основные команды исполнителя Черепаха представлены в примере 11.3
Пример 11.4. Прямоугольный участок, длина которого в 2 раза больше ширины, огородили забором длиной 120 метров.
Определить длину и ширину участка. Составить алгоритм и написать программу, выполнив которую, исполнитель Черепаха построит чертеж забора этого участка.
Масштаб: 1 м соответствуют 10 пикселям. Словесное описание алгоритма вычисления длины и ширины участка:
- Длина участка в два раза больше ширины, поэтому в сумме, длина и ширина составят три одинаковых части. Забор огораживает участок по периметру. Периметр прямоугольника равен удвоенной сумме длины и ширины, следовательно, он равен шести одинаковым частям.
- Значение ширины участка получается делением длины забора на шесть частей.
- Для нахождения значения длины участка удваиваем значение ширины.
Математическая запись действий:
1) (1 + 2) ∙ 2 = 6 (частей)
2) 120 ∶ 6 = 20 (м)
3) 20 ∙ 2 = 40 (м)
Словесное описание алгоритма рисования участка в масштабе 1:10:
| Установить размеры поля 500 × 300. Поднять перо В точку (-200, 100) Опустить перо Вперед (400) Направо (90) Вперед (200) Направо (90) Вперед (400) Направо (90) Вперед (200). |
11.3. Алгоритмическая конструкция следование
Существует большое количество алгоритмов, в которых все команды выполняются последовательно одна за другой в том порядке, в котором они записаны. В таких алгоритмах отсутствуют команды, меняющие порядок выполнения других команд. Программы такого вида вы составляли в прошлом году для исполнителя Черепаха.
| Алгоритмическая конструкция следование – последовательность команд алгоритма, которые выполняются в том порядке, в котором они записаны. |
Алгоритмическая конструкция следование отображает естественный, последовательный порядок выполнения действий в алгоритме.
Следование использовалось в примере 11.4, в котором описывались алгоритмы вычисления длины и ширины участка и построения прямоугольника исполнителем Черепаха.
Алгоритмическая конструкция следование представлена в примерах 11.5 и 11.6.
11.4. Вспомогательные алгоритмы
Часто в одной программе нужно рисовать одно и то же изображение несколько раз.
Получение этого изображения удобно оформить в виде вспомогательного алгоритма, который можно использовать нужное число раз.
| Вспомогательный алгоритм — это алгоритм, целиком используемый в составе другого алгоритма. |
Вспомогательный алгоритм решает некоторую подзадачу основной задачи.
Вызов вспомогательного алгоритма в программе заменяет несколько команд одной.
В языке Python вспомогательные алгоритмы записываются в виде функций. Формат описания функции приведен в примере 11.7.
Пример 11.8. Написать программу, выполнив которую исполнитель Черепаха нарисует следующий рисунок:
Данный рисунок состоит из трех одинаковых фигур. Для рисования одной из них можно оформить вспомогательный алгоритм – функцию figura(x, y, c).
Параметры x, y и c определяют координаты точки начала рисования фигуры и ее цвет. Каждая фигура, в свою очередь состоит из четырех одинаковых частей. Рисование одной части выполняет функция chast(). Для перемещения Черепахи в позицию с координатами (x, y) и ее поворота на 270° используется вспомогательный алгоритм p(x, y).
Описание основного алгоритма:
| рисование фигуры(-200,100,’red‘) рисование фигуры(0,100,’green‘) рисование фигуры(200,100,’blue‘) |
| Большинству исполнителей для выполнения алгоритма нужны команды, записанные на формальном языке. Для того, чтобы взаимодействие человека и технического устройства было плодотворным человек обучается формальным языкам, например языкам программирования. Другой путь – совершенствовать исполнителей так, чтобы они понимали естественный язык человека. Человечество пока еще в начале такого пути, однако уже сегодня существуют исполнители с голосовым управлением. Первыми бытовыми устройствами с голосовым управлением были стиральные машины и сотовые телефоны.
Голосовые помощники Google Assistant и Алиса, созданная компанией Яндекс, помогают осуществлять поиск, поддерживать бесседу, играть в игры, помогают управлять системой «Умный дом» и многое другое.
|
Пример 11.1. Способы представления алгоритмов:
| На разных этапах решения задачи могут применяться разные способы описания алгоритма. На этапе обсуждения используются словесные и формульные способы. На этапе проектирования рекомендуется использовать графическое представление. Для проверки результатов возможно табличное представление. Программный способ используют на этапе непосредственного применения для решения прикладных задач. |
Пример 11.2. Среда обитания исполнителя Черепаха:
Пример 11.3. Основные команды исполнителя Черепаха.
| Команда | Действие |
| penup() | Не оставлять след при движении |
| pendown() | Оставлять след при движении |
|
forward(X)
|
Пройти вперёд X пикселей |
|
backward(X)
|
Пройти назад X пикселей |
|
left(X)
|
Повернуться налево на X градусов |
|
right(X)
|
Повернуться направо на X градусов |
Пример 11.4. Блок-схема алгоритма.
Программа для исполнителя Черепаха.
| import turtle turtle.shape(‘turtle‘) turtle.setup(500, 300) turtle.penup() turtle.setpos(-200,100) turtle.pendown() turtle.forward(400) turtle.right(90) turtle.forward(200) turtle.right(90) turtle.forward(400) turtle.right(90) turtle.forward(200) |
Результат работы программы.
Пример 11.5. Алгоритм приготовления бутерброда.
- Отрезать ломтик батона.
- Положить на батон лист салата.
- Отрезать кусочек копченого мяса.
- Положить мясо на лист салата.
- Отрезать кусочек помидора.
- Положить помидор на мясо.
Пример 11.6. Алгоритм выполнения лабораторной работы по биологии «Строение инфузории туфельки».
- Рассмотреть под микроскопом внешний вид и внутреннее строение инфузории туфельки.
- Зарисовать инфузорию туфельку и обозначить названия ее органов.
- Подвести итог работе.
Пример 11.7. Формат описания функции.
Пример 11.8. Программа для исполнителя Черепаха:
Пример 11.8. Продолжение.
Начальная точка фигуры и ее часть:
Результат выполнения программы:
| Над проектом по созданию программы могут работать несколько человек (или десятков человек). Каждый из членов коллектива делает часть своей работы и оформляет ее как отдельный вспомогательный алгоритм. |
1. Что такое алгоритм?
2. Какие способы записи алгоритмов вам известны?
3. Что называют алгоритмической конструкцией следование?
4. Какие алгоритмы называются вспомогательными?
5. Для чего нужны вспомогательные алгоритмы?
Упражнения
1. Определите какой рисунок получится после выполнения Черепахой следующих программ? Изобразите рисунок в тетради и проверьте правильность своих действий, выполнив программы на компьютере.
2. Напишите для исполнителя Черепаха программы получения следующих изображений:
3. Придумайте свои рисунки и составьте программы для их рисования с помощью исполнителя Черепаха.
4. *Исполнитель Черепаха, может рисовать только отрезки. Проанализируйте рисунки. Какие из них сможет выполнить исполнитель Черепаха. Почему? Все ли из этих рисунков может нарисовать исполнитель Черепаха?
