Умскул учебник стремится стать лучше! Если вы наткнулись на ошибку или неточность в нашем материале - просто сообщите нам, мы будем благодарны!
Информатика

Основы алгоритмов

1.5.2022
7558

На этой странице вы узнаете

  • Чем хорош процесс приготовления супчика?
  • Какие есть виды алгоритмов?
  • В чем отличие Робота от Чертёжника?

Что вы сделаете в первую очередь: выйдете из квартиры или проверите, не забыли ли ключи? А станете ли вы кидать макарошки в воду до того, как она закипит?

Мы сами не замечаем, но вся наша жизнь — это набор определенных алгоритмов. Пора хорошенько в них разобраться.

Понятие алгоритма

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

В информатике алгоритм обладает некоторыми обязательными свойствами:

  • Алгоритм – это структура, состоящая из набора законченных действий, расположенных в строгом порядке.
  • Каждый шаг алгоритма строго определен и должен пониматься однозначно.
  • У алгоритма должна быть цель – в конце его выполнения должен быть конкретный результат.

Хороший пример такого алгоритма – процесс приготовления супчика.

Чем хорош процесс приготовления супчика?

Процесс приготовления супчика соответствует всем вышеописанным требованиям:
● Каждый шаг важен, причем важен именно на своем месте – нет смысла ждать, пока мы еще даже не порезали овощи.
● Каждый шаг алгоритма – четкая команда, которая понимается однозначно и не оставляет неясности.
● Итоговый результат есть, и он прекрасен.

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

Условный алгоритм или алгоритм с ветвлением добавляет в структуру какое-то условие, в зависимости от которого будет выполнена какая-то конкретная команда или набор команд.

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

В том числе в ветке условия НЕТ могла бы быть какая-то другая команда, например, ПОСОЛИТЕ, которая выполнилась бы, только если бы ответ на условие был соответствующим.

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

Здесь мы сразу не знаем, сколько фрикаделек мы хотим, поэтому будем крутить по одной и смотреть, хватит ли. Если нет, мы будем идти назад по алгоритму, чтобы вернуться к предыдущему шагу. Когда фрикаделек будет достаточно – перейдем дальше.

В том числе вместо данного условия могло бы быть конкретное количество, например, «ФРИКАДЕЛЕК РОВНО 20?» Тогда цикл бы выполнился конкретное количество раз.

Какие есть виды алгоритмов?

Подведем итог:

Линейный алгоритм — алгоритм, в котором все команды выполняются один раз и друг за другом.
Условный алгоритм или алгоритм с ветвлением подразумевает наличие условия, вариативности, когда при различных вариантах будут выполняться различные конкретные команды или наборы команд.
Циклический алгоритм подразумевает многократное выполнение какой-то команды или набора команд определенное количество раз или до выполнения определенного условия.

Исполнитель «Робот» и «Чертёжник»

Более подробно разобраться с пониманием алгоритма нам помогут два классических примера исполнителей алгоритмов – Робот и Чертёжник. Рассмотрим их подробнее по отдельности.

Исполнитель «Робот»

  • Его смысл жизни — передвигаться по полю с квадратными клетками (как шахматная доска) вверх, вниз, вправо или влево соответствующими командами. При этом он должен не разбиться об стены, которые могут быть расположены между клетками.
  • Также у него есть условия: «сверху свободно», «снизу свободно», «справа свободно», «слева свободно» и «сверху стена», «снизу стена», «справа стена», «слева стена», которые дают нам ДА или НЕТ в зависимости от выполнения этого условия.

Например:

Робот находится в ячейке С4. Он может спокойно выполнить команду «вверх», «вниз» или «влево», что сдвинет его на 1 клетку в соответствующем направлении. 

При применении команды «вправо» он разобьется об стену, которая стоит как раз справа от него. Этого можно избежать, если выполнить проверку:

С таким алгоритмом команда «вправо» будет выполнена только в том случае, если справа свободно, иначе не произойдет ничего.

А если нужно отойти к какой-то стене? 
Тогда будем использовать цикл, так как шагов у нас будет больше одного:

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

Разобравшись с его функциями, заставим Робота что-нибудь сделать.
Например, придумаем такую задачу: 

  1. Посадим его в нижний левый угол комнаты неизвестного размера.
  2. Где-то посреди комнаты поставим огромную стену, в которой будет всего одно окошко.
  3. Заставим его пройти в правый верхний угол этой комнаты.

Это лишь пример комнаты. По условию ширина комнаты, высота, положение стены и окошка в ней могут быть абсолютно любыми и заранее неизвестными.

Алгоритм решения предлагаем следующий:

  1. Движемся вправо, пока не упремся в стену.
  2. Будем двигаться вдоль стены вверх, проверяя, свободен ли путь сверху (чтобы не удариться) и не появилось ли окно справа.
  3. Как только нашли окно (справа стало свободно), двигаемся вправо до стены.
  4. Двигаемся вверх, пока перед нами не появится стена.

По этому алгоритму Робот проделает следующий путь:

А записан бы алгоритм был следующим образом:

Исполнитель «Чертёжник»

В чем отличие Робота от Чертёжника?

Отличие в том, что поле Чертёжника – вся координатная плоскость. Он может перемещаться по ней куда угодно с помощью команды «Сместиться на (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.
Что подразумевает алгоритм с ветвлением? 

  1. Строго последовательное выполнение команд.
  2. Наличие команды или набора команд, которые будут выполняться неоднократно.
  3. Наличие условия, в зависимости от выполнения которого будет выполнена та или иная команда, или набор команд.

Задание 2.
Выберите верные утверждения:

  1. Алгоритму не обязательно иметь конечный результат работы.
  2. В алгоритме важен порядок операций.
  3. В алгоритме невозможно многократное выполнение команды.
  4. При выполнении условия «ДА» в условном алгоритме не будет выполнена команда из линии условия «НЕТ».

Задание 3.
Исполнитель Робот не может:

  1. Пройти сквозь стену.
  2. Проверить наличие стены рядом с ним.
  3. Обойти стену.
  4. Сдвинуться вверх.
  5. Сдвинуться по диагонали.

Задание 4.
Исполнитель Чертёжник может:

  1. Сдвинуться четко вниз.
  2. Вернуться в исходное положение после нескольких шагов.
  3. Выполнять циклические алгоритмы.
  4. Все вышеперечисленное.

Ответы: 1. —  3; 2. — 2, 4; 3. — 1,5; 4. — 4.

Понравилась статья? Оцени:
Читайте также:

Читать статьи — хорошо, а готовиться к экзаменам
в самой крупной онлайн-школе — еще эффективнее.

50 000
Количество
учеников
1510
Количество
стобальников
>15000
Сдали на 90+
баллов