Основы алгоритмов
На этой странице вы узнаете
- Чем хорош процесс приготовления супчика?
- Какие есть виды алгоритмов?
- В чем отличие Робота от Чертёжника?
Что вы сделаете в первую очередь: выйдете из квартиры или проверите, не забыли ли ключи? А станете ли вы кидать макарошки в воду до того, как она закипит?
Мы сами не замечаем, но вся наша жизнь — это набор определенных алгоритмов. Пора хорошенько в них разобраться.
Понятие алгоритма
Алгоритм — это строгий набор определенных команд, предназначенный для выполнения каких-либо действий с целью достичь определенного результата.
В информатике алгоритм обладает некоторыми обязательными свойствами:
- Алгоритм – это структура, состоящая из набора законченных действий, расположенных в строгом порядке.
- Каждый шаг алгоритма строго определен и должен пониматься однозначно.
- У алгоритма должна быть цель – в конце его выполнения должен быть конкретный результат.
Хороший пример такого алгоритма – процесс приготовления супчика.
Чем хорош процесс приготовления супчика? Процесс приготовления супчика соответствует всем вышеописанным требованиям: ● Каждый шаг важен, причем важен именно на своем месте – нет смысла ждать, пока мы еще даже не порезали овощи. ● Каждый шаг алгоритма – четкая команда, которая понимается однозначно и не оставляет неясности. ● Итоговый результат есть, и он прекрасен. |
Мы рассмотрели пример линейного алгоритма, когда каждая команда выполняется сразу после предыдущей. Но так можно описать далеко не любой процесс, поэтому нам на помощь приходят следующие понятия:
Условный алгоритм или алгоритм с ветвлением добавляет в структуру какое-то условие, в зависимости от которого будет выполнена какая-то конкретная команда или набор команд.
Теперь у нас появился вариант поперчить суп, но эта команда выполнится, только если на условие будет утвердительный ответ. Если условие не выполнится — мы не придем к этой команде, пропустим ее и пойдем дальше по алгоритму.
В том числе в ветке условия НЕТ могла бы быть какая-то другая команда, например, ПОСОЛИТЕ, которая выполнилась бы, только если бы ответ на условие был соответствующим.
Циклический алгоритм — это команда или набор команд, которые совершаются неоднократно: либо определенное количество раз, либо пока не выполнится какое-то условие.
Здесь мы сразу не знаем, сколько фрикаделек мы хотим, поэтому будем крутить по одной и смотреть, хватит ли. Если нет, мы будем идти назад по алгоритму, чтобы вернуться к предыдущему шагу. Когда фрикаделек будет достаточно – перейдем дальше.
В том числе вместо данного условия могло бы быть конкретное количество, например, «ФРИКАДЕЛЕК РОВНО 20?» Тогда цикл бы выполнился конкретное количество раз.
Какие есть виды алгоритмов? Подведем итог: ● Линейный алгоритм — алгоритм, в котором все команды выполняются один раз и друг за другом. ● Условный алгоритм или алгоритм с ветвлением подразумевает наличие условия, вариативности, когда при различных вариантах будут выполняться различные конкретные команды или наборы команд. ● Циклический алгоритм подразумевает многократное выполнение какой-то команды или набора команд определенное количество раз или до выполнения определенного условия. |
Исполнитель «Робот» и «Чертёжник»
Более подробно разобраться с пониманием алгоритма нам помогут два классических примера исполнителей алгоритмов – Робот и Чертёжник. Рассмотрим их подробнее по отдельности.
Исполнитель «Робот»
- Его смысл жизни — передвигаться по полю с квадратными клетками (как шахматная доска) вверх, вниз, вправо или влево соответствующими командами. При этом он должен не разбиться об стены, которые могут быть расположены между клетками.
- Также у него есть условия: «сверху свободно», «снизу свободно», «справа свободно», «слева свободно» и «сверху стена», «снизу стена», «справа стена», «слева стена», которые дают нам ДА или НЕТ в зависимости от выполнения этого условия.
Например:
Робот находится в ячейке С4. Он может спокойно выполнить команду «вверх», «вниз» или «влево», что сдвинет его на 1 клетку в соответствующем направлении.
При применении команды «вправо» он разобьется об стену, которая стоит как раз справа от него. Этого можно избежать, если выполнить проверку:
С таким алгоритмом команда «вправо» будет выполнена только в том случае, если справа свободно, иначе не произойдет ничего.
А если нужно отойти к какой-то стене?
Тогда будем использовать цикл, так как шагов у нас будет больше одного:
Тогда Робот будет выполнять команду «влево» до тех пор, пока слева свободно, то есть мы остановимся только у ближайшей стены, которая возникнет перед нами слева.
Разобравшись с его функциями, заставим Робота что-нибудь сделать.
Например, придумаем такую задачу:
- Посадим его в нижний левый угол комнаты неизвестного размера.
- Где-то посреди комнаты поставим огромную стену, в которой будет всего одно окошко.
- Заставим его пройти в правый верхний угол этой комнаты.
Это лишь пример комнаты. По условию ширина комнаты, высота, положение стены и окошка в ней могут быть абсолютно любыми и заранее неизвестными.
Алгоритм решения предлагаем следующий:
- Движемся вправо, пока не упремся в стену.
- Будем двигаться вдоль стены вверх, проверяя, свободен ли путь сверху (чтобы не удариться) и не появилось ли окно справа.
- Как только нашли окно (справа стало свободно), двигаемся вправо до стены.
- Двигаемся вверх, пока перед нами не появится стена.
По этому алгоритму Робот проделает следующий путь:
А записан бы алгоритм был следующим образом:
Исполнитель «Чертёжник»
В чем отличие Робота от Чертёжника? Отличие в том, что поле Чертёжника – вся координатная плоскость. Он может перемещаться по ней куда угодно с помощью команды «Сместиться на (a, b)», которая сдвинет него на a по оси х и на b по оси у. |
У Чертёжника нет никаких стен, а единственная его цель – просто двигаться по полю, следуя алгоритму.
Так, изначально находясь в точке (0, 0), выполнив серию команд:
- сместиться на (2, 4);
- сместиться на (-6, -3);
- сместиться на (2, -3);
Чертёжник остановится в точке (-2, -2).
Отрицательные значения означают смещение вниз или налево, в то время как положительные — вверх или вправо.
В том числе Чертёжник умеет выполнять и циклический алгоритм.
- Так, запись:
7 раз подвинет Чертёжника по оси х на 2 и по оси у на 3.
- А выполнив следующий алгоритм из точки (0, 0):
Чертёжник нарисует следующий рисунок:
Практика
А сейчас потренируемся решать номера 15 ОГЭ и 12 ЕГЭ по данной теме на примере задачи:
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b).
Чертёжнику был дан для исполнения следующий алгоритм:
Сместиться на (-2, 20)
ПОВТОРИ N РАЗ
Сместиться на (4, 5)
Сместиться на (a, b)
КОНЕЦ
Сместиться на (–6, 10)
Сколько существует натуральных чисел N, для которых найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку?
Решение.
1. Будем считать, что исполнитель Чертёжник находится в начале координат, то есть в точке (0, 0).
2. После выполнения команды «Сместиться на (-2, 20)» исполнитель окажется в точке с координатами (-2, 20).
3. При выполнении цикла «Повтори N раз» Чертёжник переместится на: (N · 4 + N · a, N · 5 + N · b).
4. После выполняется команда «Сместиться на (-6, 10)». Мы знаем, что чертёжник вернулся в начало координат, то есть его итоговые координаты после всех перемещений — (0, 0).
5. Составим систему уравнений:
6. Преобразуем уравнения:
-2+N · (4+a)-6=0 -8+N · (4+a) = 0 N=8 /(a+4) | 20+N · (5+b)+10=0 30+N · (5+b)=0 N=-30 / (b+5) |
Получим новую систему:
7. Переменные a, b должны быть целыми, N должно быть натуральным значением. Тогда 8 делится на N и -30 делится на N.
Делители 8: 1, 2, 4, 8.
Делители -30: 1, 2, 3, 5, 6, 10, 15, 30.
N может принимать значения 1 и 2 — всего 2 разных значения.
Ответ: 2
Алгоритм — краеугольное понятие для всего программирования в принципе, потому что любая программа представляет собой реализацию некоторого алгоритма. В том или ином виде алгоритмы нужны в большей части заданий ОГЭ и ЕГЭ. В следующей статье «Основы программирования на языке Python. Часть 1» мы разберемся, как создавать такие программы — реализации алгоритмов.
Термины
Натуральные числа — это числа, употребляемые при счете. Например: 1, 2, 3, 4 и т.д.
Координатная плоскость — плоскость, на которой отмечены прямые — оси координат.
Фактчек
- Алгоритм — это определенный набор команд, направленный на достижение какой-либо цели.
- У алгоритма есть определенный набор правил, которым он должен соответствовать, чтобы его работа была однозначной и полной.
- Различают линейные алгоритмы, условные алгоритмы и циклические алгоритмы.
- Исполнитель «Робот» умеет сдвигаться на 1 клетку в любом из 4 направлений и проверять, нет ли в этих направлениях рядом с ним стены. Его цель — пройти по полю из квадратных клеток в определенную и не врезаться в стену.
- Исполнитель «Чертёжник» может без ограничений передвигаться по координатной плоскости в любом направлении. Его цель — прийти в какую-то конкретную точку из какой-то начальной позиции.
Проверь себя
Задание 1.
Что подразумевает алгоритм с ветвлением?
- Строго последовательное выполнение команд.
- Наличие команды или набора команд, которые будут выполняться неоднократно.
- Наличие условия, в зависимости от выполнения которого будет выполнена та или иная команда, или набор команд.
Задание 2.
Выберите верные утверждения:
- Алгоритму не обязательно иметь конечный результат работы.
- В алгоритме важен порядок операций.
- В алгоритме невозможно многократное выполнение команды.
- При выполнении условия «ДА» в условном алгоритме не будет выполнена команда из линии условия «НЕТ».
Задание 3.
Исполнитель Робот не может:
- Пройти сквозь стену.
- Проверить наличие стены рядом с ним.
- Обойти стену.
- Сдвинуться вверх.
- Сдвинуться по диагонали.
Задание 4.
Исполнитель Чертёжник может:
- Сдвинуться четко вниз.
- Вернуться в исходное положение после нескольких шагов.
- Выполнять циклические алгоритмы.
- Все вышеперечисленное.
Ответы: 1. — 3; 2. — 2, 4; 3. — 1,5; 4. — 4.