Информатика

Практика анализа алгоритмов

3.5.2022

3628

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

Почему Шерлок Холмс смог бы стать хорошим программистом?
Как заставить одну программу анализировать другую?
Как понять, с чем работал алгоритм?

Пройти из точки А в точку В по строгому алгоритму — одно дело. Но что, если мы повернем время вспять и попробуем угадать начальную точку, зная только конечную? Возможно ли это — узнаем в статье.

Анализ алгоритмов

В предыдущих выпусках мы с вами научились создавать:

сами алгоритмы — в статье «Основы алгоритмов»;
код на языке Python в статьях «Основы программирования. Часть 1», «Основы программирования. Часть 2».

Для полного понимания материала этой статьи нам понадобятся некоторые навыки составления алгоритмов, работы с циклами while и for, с условной конструкцией if. Если вы не уверены, что полностью изучили предыдущие темы, советуем «обновить» знания в статьях по ссылкам выше.

Почему Шерлок Холмс смог бы стать хорошим программистом?

Одного лишь навыка написания алгоритмов может быть недостаточно. Имея на руках готовый алгоритм, иногда нам может потребоваться не выполнить его, а наоборот — по результату его работы найти исходные данные. Этим занимался и Шерлок Холмс — по картине места преступления восстанавливал изначальную ситуацию.

Сегодня мы разберем, как именно это делается — как анализируется алгоритм. За пример возьмем нашего старого знакомого — исполнителя Робота из статьи «Основы алгоритмов». Напомним: Робот умеет двигаться в 4 направлениях (вверх, вправо, вниз или влево) и может проверить, находится ли рядом с ним стена, в которую он не должен врезаться.

Допустим, мы знаем, что робот двигался согласно следующему алгоритму:

ПОКА снизу свободно ИЛИ справа свободно
   ПОКА справа свободно
       вправо
   КОНЕЦ ПОКА
   ЕСЛИ снизу свободно
   ТО
        вниз
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

По этому полю:

И по итогу Робот остановился в ячейке F1.

Наша задача: определить, из каких ячеек Робот мог начинать движение, чтобы по выполнении этого алгоритма он остановился именно в F1.

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

В первую очередь Робот будет перемещаться вправо до тех пор, пока не упрется в стену. Если справа уже есть стена, он просто ничего не сделает.
Далее Робот опустится на 1 ячейку вниз, если снизу нет стены. Если стена есть, ничего не произойдет.
Шаги 1 и 2 будут повторяться до тех пор, пока стена не окажется и справа, и снизу.

Чтобы решить эту задачу, выберем несколько начальных позиций, из которых мы выполним данный алгоритм. Если по выполнении алгоритма Робот остановится в нужной ячейке — начальная позиция была подходящая.

Начнем двигаться из А6. После первого шага цикла Робот попадет в ячейку D5, сдвинувшись максимально вправо до ячейки D6 и сделав 1 шаг вниз в D5.

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

Выполнив те же действия — максимально продвинувшись вправо и сделав 1 шаг вниз — Робот оказывается в ячейке F4.

Условие остановки цикла еще не выполнилось, продолжаем двигать Робота.

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

И вот мы знаем, что как минимум А6 подходит под ответ — оттуда можно попасть в F6.

Теперь попробуем начать движение из другой ячейки, например, из А5.

История будет максимально короткая: продвинувшись до конца вправо и сделав шаг вниз, мы попадем в угол. Дальше двигаться не сможем, так как цикл остановится — и справа, и снизу появилась стена.

Так что ячейка А5 нам точно не подходит.

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

Если мы дойдем до самой правой стены, мы спокойно спустимся вниз в нужную ячейку.
Мы можем начать движение сразу из F1, тогда наш алгоритм моментально будет выполнен, и цель достигнута.
Нам нельзя попадать в ячейку С4, из нее дальше дороги не будет.

И уже чисто логически, а при необходимости проверив еще пару ячеек, мы можем найти все ячейки, из которых Робот мог начать свою работу:

Задания на анализ алгоритма часто встречаются в номерах 15 ОГЭ и 12 ЕГЭ по информатике.

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

Сколько клеток лабиринта соответствуют требованию: выполнив предложенную программу, Робот уцелеет и окажется в клетке F6?

ПОКА снизу свободно ИЛИ справа свободно
        ПОКА справа свободно
                    вправо
        КОНЕЦ ПОКА
        ЕСЛИ снизу свободно ТО
                    вниз
        КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

Решение.

Шаг 1. Как работает этот алгоритм? Если справа свободно, то Робот будет двигаться вправо, пока не упрется в стену. Если справа стена, то Робот будет проверять свободно ли снизу и будет двигаться вниз. Отсюда можно сделать вывод, что алгоритм будет работать, пока справа и снизу от Робота не окажутся стены.

Шаг 2. В каких клетках наш алгоритм закончится, не достигнув итоговой ячейки F6? Это клетки с координатами D4, E4, D5, E5. Здесь Робот «окажется в ловушке»: он упрется в стены, двигаясь или вниз, или вправо. Алгоритм будет завершен (так как есть стены справа и снизу), но Робот не достигнет точки F6.

Шаг 3. Что еще нужно учесть?
— В строках 1, 2, 3 Робот сначала будет идти вправо до стены. Затем, уперевшись в стену, он будет двигаться вниз до ячейки F6. Все клетки в столбце F имеют справа стену, а снизу свободны до F6, следовательно, они нам подходят.
— Из любой клетки в строке 6 Робот попадет в клетку F6, двигаясь направо.
— Ячейки А4, В4, С4 и А5, В5, С5 также нам подходят. Из этих клеток Робот будет двигаться направо до ближайшей стены, а далее пойдет вниз. Оказавшись на 6 строчке, Робот дойдет до точки F6.
Итого нам подходят 32 клетки из 36-ти возможных.

Ответ: 32

Анализ программного кода

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

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

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

s = int(input())
n = 0
while s + n <= 400:
s = s — 7
n = n + 11
print(n)

Способ 1. Анализ кода

Давайте сразу переведем алгоритм в более понятный вид:

Нам дано два числа — n и s.
Пока их сумма не станет больше 400, s будет уменьшаться на 7, а n увеличиваться на 11.
В конце программы на экран будет выведено значение n.

Отсюда можем уже увидеть интересный момент:

n из 0 стала равна 77;
за 1 раз к переменной n прибавлялось 11;
значит, тело цикла while повторилось ровно 7 раз.

Так как здесь происходят циклические операции над числами, весь процесс можно обернуть в математическое выражение. Изменения обеих переменных происходили ровно 7 раз, а так как после этого цикл завершил работу, сумма их значений стала больше 400:

\(s-(7 * 7)+n+(11 * 7)>400\).

Решив это неравенство и подставив изначальное n = 0, находим, что s > 372:

\(s-49+0+77>400\)
\(s > 372\).

То есть s может принимать значения 373, 374… Но какое наибольшее?

Давайте составим еще одно неравенство. Цикл должен выполниться ровно 7 раз. Значит, если он выполнится 6 раз, цикл еще не остановится. Тогда сумма переменных s и n будет меньше или равна 400:

\(s-(7 * 6)+n+(11 * 6) ≤ 400\).

Отсюда получим \(s ≤ 376\):

\(s-42+0+66 ≤ 400\)
\(s ≤ 376\).

Итого: s лежит в диапазоне \(372 < s ≤ 376\).

Значит, наибольшее значение, которое может принять s — это 376.

Способ 2. Анализ с помощью программы

Как заставить одну программу анализировать другую?

Используя метод решения программированием, мы можем не делать практически никакого анализа. Напишем программу, которая сама будет перебирать различные входящие значения, прогонять их по исходному алгоритму и, если начальное значение подошло, выводить его на экран.

Главный вопрос: какой диапазон начальных значений мы будем перебирать? Без анализа сложно быстро представить, каким примерно окажется правильный ответ.

Есть два, казалось бы, очевидных, но не таких простых варианта:

Если ничего не мешает, перебираем по какому-нибудь максимально большому диапазону (чтобы он точно включал числа для полного решения задачи).
Если что-то мешает, выбираем диапазон, в котором ничего не будет мешать.

Что именно нам может помешать, мы рассмотрим чуть позже. В данной задаче никаких помех у нас нет, так что пока не думаем об этом.

Что нам понадобится для реализации новой программы?

Цикл for, который и будет перебирать различные начальные значения.
Тело цикла, в котором будет реализован алгоритм из условия задачи.
Условная конструкция if, которая проверит итоговое значение необходимой переменной.

В диапазоне цикла for, раз нам ничто не мешает, просто ставим достаточно большой диапазон, например, от -1000 до 1000.

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

Наша программа будет выглядеть так:

for i in range(-1000, 1000):
            s = i
            n = 0
            while s + n <= 400:
                    s = s — 7
                    n = n + 11
            if n == 77:
                    print(i)

Вывод:
373
374
375
376

Цикл for перебирает переданные ему значения и подставляет их к переменной s, после чего срабатывает код из условия задачи. Если по его выполнении значение переменной n стало равно 77, мы выводим изначальное значение переменной s на экран.

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

И снова мы получили ответ — 376.

А теперь пара слов о том, что может испортить нам жизнь.

Как мы упомянули выше, при таком решении не нужен практически никакой анализ. Небольшие вычисления произвести все-таки придется, чтобы правильно выставить диапазон перебора.

Например, при том же условии (на экран выведено число 77, найти наибольшее возможное исходное значение s), но другом исходном коде наше решение уже не сработает:

s = int(input())
n = 0
while s <= 400:
s = s * 2
n = n + 11
print(n)

При использовании в решении того же диапазона начальных значений (от -1000 до 1000) начальных значений s мы попадаем в бесконечный цикл.

Почему это происходит? Мы берем начальное значение s отрицательным или равным 0 и умножаем его в цикле while на 2. Математика подсказывает нам, что значение операции никогда не станет больше 400. Оно даже выше 0 не поднимется, так как при умножении отрицательных чисел на положительные, получаются отрицательные числа (которые всегда меньше положительных). Также и с числом 0: любое число, умноженное на ноль, всегда будет меньше положительного.

Поэтому при решении этой задачи пользуемся тем же подходом, но не берем в качестве начальных значений отрицательные числа и 0:

for i in range(1, 1000):
                s = i
                n = 0
                while s <= 400:
                        s = s * 2
                        n = n + 11
                if n == 77:
                        print(i)

Вывод:
4
5
6

Ответом будет 6.

Задания на анализ кода, аналогичные разобранному выше, могут встретиться вам в номере 6 ОГЭ. Каким способом его решать — вручную (математическими вычислениями) или с помощью другой программы зависит от сложности самого алгоритма. При выборе способа решения мы советуем вам обратить внимание на структуры программы, если там присутствует большое количество ветвлений и циклов, то лучше поручить анализ другой программе.

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

Как понять, с чем работал алгоритм?

По готовому алгоритму и результатам его работы можно определить, с чем именно работал алгоритм. Для этого у нас есть три варианта действий:
1. Записать исходную программу и, подставив в нее числа, посмотреть, как именно алгоритм их преобразует.
2. Написать дополнительную программу, с помощью которой алгоритм сам введет значения и выведет нам результат работы программы.
3. Посмотреть закономерности при вводе различных значений в наш алгоритм.

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

Термины

Бесконечный цикл — ситуация, когда цикл while сам по себе никогда не сможет завершить свою работу, то есть значение его условия никогда не перестанет быть равным True.

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

Переменная — представляет собой ячейку в памяти компьютера, которая хранит имя и определенное значение.

Цикл (циклическая операция) — это многократное повторение определенной команды или набора команд. Для выделения тела цикла используется табуляция.

Фактчек

При анализе алгоритма и поиске начальных значений по конечному имеет смысл представить сам алгоритм в более понятной формулировке.
Мы можем проверить несколько начальных значений, взятых наугад, чтобы найти внутренние неочевидные закономерности. Так мы поймем принцип работы алгоритма и сможем найти начальные значения, пользуясь логикой.
Один из способов найти исходные данные — записать действия алгоритма в виде математического выражения (если это возможно).
Можно написать программу, которая сама будет подставлять начальные значения в исходный код и выбирать подходящие.

Проверь себя

Задание 1.
Сколько клеток лабиринта соответствуют требованию: выполнив предложенную программу, Робот уцелеет и окажется в клетке F6?

ПОКА снизу свободно ИЛИ справа свободно
ПОКА справа свободно
вправо
КОНЕЦ ПОКА
ЕСЛИ снизу свободно ТО
вниз
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

Задание 2.
В качестве ответа запишите наименьшее введенное значение s, при котором программа выведет число 1024 в результате своего выполнения.

s = int(input())
n = 1
while s < 75:
s = s + 6
n = n * 2
print(n)

Задание 3.
В качестве ответа запишите наибольшее введенное значение s, при котором программа выведет число 256 в результате своего выполнения.

s = int(input())
n = 1
while s < 10000:
s = s * 3
n = n * 2
print(n)

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

Информатика практика анализа алгоритмов

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