Глава 3. Основы алгоритмизации
§ 3.1 Алгоритмы и исполнители
Сейчас мы узнаем, как превратить любую задачу в чёткий план действий, который поймёт и человек, и компьютер.
Что такое алгоритм и зачем он нужен?
Каждый день ты решаешь кучу задач: зарегистрироваться в новой соцсети, найти НОД двух чисел для домашки, отсортировать треки в плейлисте. Некоторые задачи требуют времени на размышление, а другие ты делаешь на автомате — как будто кто-то уже написал для тебя инструкцию.
📱 Пример: Регистрация ВКонтакте
Давай представим: ты объясняешь другу, как зарегистрироваться ВКонтакте. Вот что ты скажешь:
- Зайди на сайт vk.com
- Нажми кнопку «Зарегистроваться»
- Введи номер телефона
- Подтверди вход кодом из СМС
- Введи информацию о себе (имя, фамилия, дата рождения, пол)
- Подтверди ввод данных
Поздравляю — ты только что создал алгоритм!
🎨 Ещё один пример
Как нарисовать весёлого ёжика? Можно разбить процесс на шаги — сначала овал (тело), потом лапки, иголки, мордочку. Каждый шаг ведёт к результату.
Алгоритм — это инструкция для достижения цели
Регистрация аккаунта, рисование ёжика, нахождение НОД, сортировка мусора — на первый взгляд это совершенно разные процессы. Но у них есть общая черта: каждый можно описать последовательностью кратких указаний, точное следование которым позволяет получить нужный результат.
💡 Определение
Алгоритм — это описание последовательности шагов в решении задачи, приводящих от исходных данных к требуемому результату.
Любой алгоритм преобразует исходные данные в нужный результат
[Исходные данные] → [Алгоритм] → [Результат]
Алгоритмами являются правила сложения и вычитания, умножения и деления чисел, многие грамматические правила, правила геометрических построений и так далее.
Пример: из одной системы счисления в другую
Следующий алгоритм приводит к тому, что из одного натурального числа получается другое натуральное число:
- Исходное число переводится в двоичную систему счисления
- Подсчитывается число единиц в полученной двоичной записи исходного числа
- Если число единиц в двоичной записи нечётное, то к этой записи справа приписывается 1, если чётное — 0
- Число, соответствующее дополненной двоичной записи, переводится в десятичную систему счисления
Получившееся таким образом число является результатом работы алгоритма.
🔢 Примеры работы
Например, если исходным было число 21, то результатом работы алгоритма будет число 43, а если исходным числом было 15, то результатом работы алгоритма будет число 30.
Кто выполняет алгоритмы? Знакомься — исполнитель!
Каждый алгоритм предназначен для определённого исполнителя.
💡 Определение
Исполнитель — это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
Исполнители бывают разные: роботы, черепашки, бытовая техника — все они выполняют свои команды
Виды исполнителей
🤖 Формальный исполнитель
Не вникает в смысл того, что он делает, и не рассуждает, почему он поступает так, а не иначе. Ему дали команду — и ту же команду формальный исполнитель всегда выполняет одинаково.
👤 Неформальный исполнитель
Может выполнять команду по-разному в зависимости от ситуации.
Характеристики формального исполнителя
Формальные исполнители необычайно разнообразны, но для каждого из них можно указать следующие характеристики:
🎯 Что он умеет делать
Построение цепочек символов, выполнение вычислений, построение рисунков на плоскости и т. д.
🌍 Где он работает
Область, обстановка, условия, в которых действует исполнитель
📋 Система команд исполнителя
Совокупность всех команд, которые могут быть выполнены неким исполнителем
⚙️ Как он выполняет команды
Непосредственный (ручной) или программный режим
🎮 Режимы работы исполнителя
Непосредственное (ручное) управление: исполнитель немедленно выполняет каждую поступившую команду. В таком режиме работает пульт кондиционера или телевизора.
Программное управление: исполнителю сначала задаётся полная последовательность команд (программа), а затем он выполняет все эти команды в автоматическом режиме. Например, в память стиральной машины заложены разные достаточно сложные программы стирки.
Примеры исполнителей
Давайте рассмотрим несколько примеров исполнителей и их систем команд.
🐢 Пример 1: Исполнитель Черепаха
Исполнитель Черепаха перемещается на экране компьютера, оставляя след в виде линии.
Система команд Черепахи:
- Вперёд n (где n — целое число) — вызывает передвижение Черепахи на n шагов в направлении движения
- Направо m (где m — целое число) — вызывает изменение направления движения Черепахи на m градусов по часовой стрелке
- Запись: Повтори k [<Команда 1> <Команда 2> … <Команда n>] — означает, что последовательность команд в скобках повторится k раз
🤔 Задание
Подумайте, какая фигура появится на экране после выполнения Черепахой следующего алгоритма:
Повтори 12 [Направо 45 Вперёд 20 Направо 45]
🔢 Пример 2: Исполнитель Вычислитель
Система команд исполнителя Вычислитель состоит из двух команд, которым присвоены номера:
- 1. вычти 1
- 2. умножь на 3
Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза. При записи алгоритмов для краткости указываются лишь номера команд.
✅ Пример работы
Например, алгоритм 21212 означает следующую последовательность команд:
- умножь на 3
- вычти 1
- умножь на 3
- вычти 1
- умножь на 3
С помощью этого алгоритма число 1 будет преобразовано в 15:
((1 · 3 – 1) · 3 – 1) · 3 = 15
🤖 Пример 3: Исполнитель Робот
Исполнитель Робот действует на клетчатом поле, между соседними клетками которого могут стоять стены. Робот передвигается по клеткам поля и может выполнять следующие команды, которым присвоены номера:
- 1. вверх
- 2. вниз
- 3. вправо
- 4. влево
При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается.
Робот на клетчатом поле должен двигаться так, чтобы не врезаться в стены
🤔 Задание
Что произойдёт с Роботом, если он выполнит последовательность команд 32323 (здесь цифры обозначают номера команд), начав движение из клетки A?
Какую последовательность команд следует выполнить Роботу, чтобы переместиться из клетки A в клетку B, не разрушившись при этом от столкновения со стеной?
🔢 Пример 4: К пятизначному натуральному числу
К пятизначному натуральному числу применяется следующий алгоритм:
- Вычислить сумму первых трёх цифр
- Вычислить сумму последних двух цифр
- Записать полученные два числа друг за другом в порядке возрастания (неубывания)
✅ Пример работы алгоритма для числа 56789:
- 5 + 6 + 7 = 18
- 8 + 9 = 17
- Упорядочив, получаем 1718
В старших разрядах наименьшего пятизначного числа должны быть самые маленькие цифры из возможных. В нашем случае это: 17 = 1 + 7 + 9.
Есть единственный вариант, позволяющий получить вторую сумму из двух цифр: 18 = 9 + 9.
Составим наименьшее пятизначное число: 17999.
Составим наибольшее пятизначное число: 99098.
При разработке алгоритма важно учитывать
Выделить объекты
Определить фигурирующие в задаче объекты, их свойства, отношения между объектами и возможные действия с объектами
Определить данные
Определить исходные данные и требуемый результат
Определить последовательность
Определить последовательность действий исполнителя, обеспечивающая переход от исходных данных к результату
Записать команды
Последовательность действий записывается с помощью команд, входящих в систему команд исполнителя
Можно сказать, что алгоритм — план управления исполнителем
Разработка алгоритма требует планирования — от исходных данных к результату
Свойства алгоритма
Не любая инструкция, последовательность предписаний или план действий может считаться алгоритмом. Каждый алгоритм обязательно обладает следующими свойствами:
Пять ключевых свойств делают последовательность команд настоящим алгоритмом
🧩 Дискретность
Свойство дискретности означает, что путь решения задачи разделён на отдельные шаги (действия). Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель может приступить к выполнению следующей команды.
💡 Понятность
Свойство понятности означает, что алгоритм состоит только из команд, входящих в систему команд исполнителя, т. е. из таких команд, которые исполнитель может воспринять и по которым может выполнить требуемые действия.
🎯 Определённость
Свойство определённости означает, что в алгоритме нет команд, смысл которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какую команду выполнять следующей.
Благодаря этому результат алгоритма однозначно определяется набором исходных данных: если алгоритм несколько раз применяется к одному и тому же набору исходных данных, то на выходе всегда получается один и тот же результат.
🏁 Результативность
Свойство результативности означает, что алгоритм должен обеспечивать получение результата после конечного, возможно очень большого, числа шагов.
При этом результатом считается не только обусловленный постановкой задачи ответ, но и вывод о невозможности по какой-либо причине продолжения решения данной задачи.
⚙️ Массовость
Свойство массовости означает, что алгоритм должен обеспечивать возможность его применения для решения любой задачи из некоторого класса задач.
Например, алгоритм нахождения корней квадратного уравнения должен быть применим к любому квадратному уравнению, алгоритм перехода улицы должен быть применим в любом месте улицы, алгоритм приготовления лекарства должен быть применим для приготовления любого его количества и т. д.
Пример: решето Эратосфена
Рассмотрим один из методов нахождения всех простых чисел, не превышающих некоторое натуральное число n. Этот метод называется «решето Эратосфена» по имени предложившего его древнегреческого учёного Эратосфена (III в. до н. э.).
📝 Алгоритм решета Эратосфена
Для нахождения всех простых чисел, не больших заданного числа n, следуя методу Эратосфена, нужно выполнить такие шаги:
- Выписать подряд все натуральные числа от 2 до n (2, 3, 4, …, n)
- Заключить в рамку 2 — первое простое число
- Вычеркнуть из списка все числа, делящиеся на последнее найденное простое число
- Найти первое неотмеченное число (отмеченные числа — зачёркнутые числа или числа, заключённые в рамку) и заключить его в рамку — это будет очередное простое число
- Повторять шаги 3 и 4 до тех пор, пока не останется неотмеченных чисел
✅ Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:
- дискретности — процесс нахождения простых чисел разбит на шаги
- понятности — каждая команда понятна ученику 8 класса, выполняющему этот алгоритм
- определённости — каждая команда трактуется и выполняется исполнителем однозначно; имеются указания об очерёдности выполнения команд
- результативности — через некоторое число шагов достигается результат
- массовости — последовательность действий применима для любого натурального n
Возможность автоматизации деятельности человека
Разработка алгоритма, как правило, трудоёмкая задача, требующая от человека глубоких знаний, изобретательности и больших временных затрат. Решение задачи по готовому алгоритму требует от исполнителя только строгого следования заданным предписаниям.
🎮 Пример: игра с победной стратегией
Из кучи, содержащей любое, большее 3, количество каких-либо предметов, двое играющих по очереди берут по одному или по два предмета. Выигрывает тот, кто своим очередным ходом сможет забрать все оставшиеся предметы.
Алгоритм выигрыша для первого игрока:
- Если число предметов в куче кратно 3, то уступить ход противнику, иначе начать игру, взяв 1 или 2 предмета так, чтобы осталось количество предметов, кратное 3
- Своим очередным ходом каждый раз дополнять число предметов, взятых соперником, до 3 (число оставшихся предметов должно быть кратно 3)
🎲 Попробуй сам!
Предложите сыграть в эту игру кому-нибудь из своих родных, друзей или знакомых. Действуйте строго в соответствии с приведённым выше алгоритмом. Убедитесь, что алгоритм «работает»!
🤖 Способность исполнителя действовать формально
Исполнитель может не вникать в смысл того, что он делает, и не рассуждать, почему он поступает так, а не иначе, т. е. он может действовать формально.
Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека. Для этого:
- процесс решения задачи представляется в виде последовательности простейших операций
- создаётся машина (автоматическое устройство), способная выполнить эти операции в последовательности, заданной в алгоритме
- человек освобождается от рутинной деятельности, выполнение алгоритма поручается автоматическому устройству
Мир, окружающий современного человека, с каждым днём наполняется всё более совершенными формальными исполнителями (цифровыми устройствами), «берущими» на себя многие рутинные виды деятельности, ранее выполнявшиеся человеком.
Представления об алгоритмах позволяют понять, как работают цифровые устройства, какие ещё работы можно на них переложить, с какими трудностями при этом можно столкнуться.
📌 САМОЕ ГЛАВНОЕ
Ключевые понятия этого параграфа
🤔 Проверь себя
Ответь на вопросы, чтобы проверить, как хорошо ты усвоил материал!
1. Что называют алгоритмом?
Вспомни определение и приведи свой пример алгоритма из повседневной жизни.
2. С помощью поиска в сети Интернет выясните происхождение термина «алгоритм»
Подсказка: это связано с именем великого математика из Средней Азии.
3. Подберите синонимы к слову «предписание»
Какими ещё словами можно назвать инструкцию или команду?
4. Приведите примеры алгоритмов, изучаемых вами в школе
Подумайте об алгоритмах на уроках математики, физики, химии...
5. Кто может быть исполнителем алгоритма?
Перечислите возможные типы исполнителей.
6. Приведите пример формального исполнителя. Приведите пример, когда человек выступает в роли формального исполнителя
Подумайте о ситуациях, когда человек выполняет команды строго по инструкции, не размышляя.
7. От чего зависит круг решаемых задач исполнителя «компьютер»?
Что определяет возможности компьютера?
8. Рассмотрите в качестве исполнителя текстовый процессор, имеющийся на вашем компьютере. Охарактеризуйте круг решаемых этим исполнителем задач и его среду
Какие задачи решает текстовый редактор? В какой среде он работает?
9. Что такое команда, система команд исполнителя? Какие команды должны быть у робота, выполняющего функции: а) кассира в магазине; б) дворника; в) охранника?
Обсудите эти вопросы в группе.
10. Исследуйте один из исполнителей системы программирования КуМир
Охарактеризуйте его назначение, среду, СКИ, возможности ручного и программного управления. Используйте встроенную в систему справочную информацию.
11. Перечислите основные свойства алгоритма
Вспомните все пять свойств.
12. К чему может привести отсутствие какого-либо свойства у алгоритма? Приведите примеры
Что произойдёт, если алгоритм не будет дискретным? Определённым? Результативным?
13. В чём важность возможности формального исполнения алгоритма?
Как это связано с автоматизацией?
14. Последовательность чисел строится по следующему алгоритму...
Первые два числа последовательности принимаются равными 1; каждое следующее число последовательности принимается равным сумме двух предыдущих чисел.
Запишите 10 первых членов этой последовательности. Выясните, как называется эта последовательность.
15. Некоторый алгоритм получает из одной цепочки символов новую цепочку...
Сначала записывается исходная цепочка символов, после неё записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на последнем месте.
Дана цепочка символов «КОМ». Сколько букв «О» будет в цепочке символов, которая получится, если применить алгоритм к данной цепочке, а затем ещё раз применить алгоритм к результату его работы?
16. Найдите в сети Интернет анимацию шагов алгоритма Эратосфена
С помощью алгоритма Эратосфена найдите все простые числа, не превышающие 50.
17. Что будет результатом исполнения Черепахой следующего алгоритма?
Повтори 8 [Направо 45 Вперед 45]
18. Запишите алгоритм для исполнителя Вычислитель, содержащий не более 5 команд
а) получения из числа 3 числа 16;
б) получения из числа 1 числа 25.
19. Система команд исполнителя Конструктор состоит из двух команд...
1. приписать 2
2. разделить на 2
По первой из них к числу приписывается справа 2, по второй число делится на 2.
а) Как будет преобразовано число 8, если исполнитель выполнит алгоритм 22212?
б) Составьте алгоритм в системе команд этого исполнителя, по которому число 1 будет преобразовано в число 16 (в алгоритме должно быть не более 5 команд).
20. В какой клетке (А или В) должен находиться исполнитель Робот...
...чтобы после выполнения алгоритма 3241 (где цифры — это номера команд Робота) в неё же и вернуться?
21. К пятизначному натуральному числу применяется алгоритм...
1. Вычислить сумму первых двух цифр.
2. Вычислить сумму последних трёх цифр.
3. Записать полученные два числа друг за другом в порядке возрастания.
Выясните наименьшее и наибольшее пятизначные числа, в результате применения к которым этого алгоритма получится число 1215.
22. К четырёхзначному натуральному числу применяется алгоритм...
Выясните, какие из приведённых ниже чисел могут получиться в результате работы этого алгоритма: 2118, 1818, 1718, 1214, 123.
23. Все алгоритмы, которые мы рассматривали, можно считать последовательными...
Подумайте сами почему. Вместе с тем в реальной жизни очень много принципиально иных алгоритмов.
Параллельный алгоритм — алгоритм, который может быть реализован по частям на множестве различных исполнителей с последующим объединением полученных результатов.
Приведите 2–3 примера параллельных алгоритмов из окружающего нас мира.
24. Три актёра готовятся к спектаклю...
С ними работают два опытных гримёра. Каждый актёр должен быть накрашен и причёсан. Макияж у каждого актёра продолжается полчаса, а причёсывание — только 10 минут.
Спланируйте работу гримёров так, чтобы актёры как можно быстрее подготовились к выходу на сцену. Сколько для этого потребуется времени?
25. Группа из четырёх туристов должна пройти по мосту в темноте...
Идти по мосту одновременно могут не более двух туристов. При этом они могут пользоваться только одним фонарём.
Как организовать переход, чтобы затратить минимальное время?
