ЕГЭ-2021, задание 5, часть 1. Анализ простых алгоритмов для конкретного исполнителя с фиксированным набором команд

Задание 5, часть 1. Анализ простых алгоритмов для конкретного исполнителя с фиксированным набором команд

Исполнители бывают двух видов - формальные и неформальные.

Формальный исполнитель одну и ту же команду всегда выполняет одинаково.

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

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

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

Как правило, человек выступает в роли неформального исполнителя.

Формальными исполнителями являются преимущественно технические устройства.

Человек в роли неформального исполнителя сам отвечает за свои действия.

За действия формального исполнителя отвечает управляющий им объект.

Каждый исполнитель создается для решения задач определённого класса (круга).

Область, обстановку, условия, в которых действует исполнитель, принято называть средой данного исполнителя.

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

Алгоритм – это порядок решения задачи, описанный в ней самой. Линейный алгоритм описывает действия, выполняемые в строгой последовательности друг за другом. Решение задачи по готовому алгоритму требует от исполнителя только строгого следования заданным предписаниям

Исполнитель не вникает в смысл того, что он делает, и не рассуждает, почему он поступает так, а не иначе — он действует формально.

Так следует поступать и нам при решении задач для формального исполнителя.

Рассмотрим задачи четырех различных типов.

Тип 1. Задан исполнитель с конкретными командами. Требуется составить алгоритм получения из заданного исходного числа требуемого результата, при этом количество используемых команд в программе ограничено.

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

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

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

Пример 1. 1.

У исполнителя Делитель две команды, которым присвоены номера:

1. раздели на 2

2. прибавь 1

Первая из них уменьшает число на экране в 2 раза, вторая увеличивает его на 1. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 23 числа 4, содержащий не более 5 команд. В ответе запишите только номера команд.(Например, 11222 — это алгоритм: раздели на 2, раздели на 2, прибавь 1, прибавь 1, прибавь 1, который преобразует число 36 в 12.) Если таких алгоритмов более одного, то запишите любой из них.

Решение.

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

При помощи элементарных рассуждений и вычислений получаем:

23 + 1 = 24 / 2 = 12 / 2 = 6 / 2 = 3 + 1 = 4

Ответ: 12221

Пример 1.2.

У исполнителя Квадратор две команды, которым присвоены номера:

1. возведи в квадрат

2. вычти 3

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

Составьте алгоритм получения из числа 4 числа 49, содержащий не более 5 команд. В ответе запишите только номера команд. (Например, 12221 — это алгоритм возведи в квадрат, вычти 3, вычти 3, вычти 3, возведи в квадрат, который преобразует число 4 в 49.) Если таких алгоритмов более одного, то запишите любой из них.

Решение.

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

При помощи элементарных рассуждений и вычислений получаем:

= 7 + 3 = 10 + 3 = 13 + 3 = 16, = 4

Тогда ответ пишем в обратную сторону заданными командами

Ответ: 12221

Тип 2. Задан алгоритм для исполнителя с конкретным количеством команд, при этом одна из команд содержит неизвестное значение. Требуется найти значение неизвестного.

Пример 2.1.

У исполнителя Альфа две команды, которым присвоены номера:

1. прибавь 2;

2. умножь на b

(b — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Бета увеличивает число на экране на 2, а выполняя вторую, умножает это число на b. Программа для исполнителя Альфа — это последовательность номеров команд. Известно, что программа 12111 переводит число 7 в число 51. Определите значение b.

Решение.

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

В результате выполнения команды 1 получаем

7+2 = 9.

Затем запишем дальнейшие действия в виде уравнения и решим его:

9 * b +3*2 = 51

Тогда 9*b = 45, то есть b=5.

Ответ: 5

Пример 2.2.

У исполнителя Сигма две команды, которым присвоены номера:

1. прибавь 1;

2. раздели на b

(b — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Сигма увеличивает число на экране на 1, а выполняя вторую, делит это число на b. Программа для исполнителя Сигма — это последовательность номеров команд. Известно, что программа 11211 переводит число 50 в число 22. Определите значение b.

Решение.

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

В результате выполнения команды 1 получаем

50+2*2 = 54

Затем запишем дальнейшие действия в виде уравнения и решим его:

54/b +2*2 = 22

Тогда 54/b=18, то есть b = 3.

Ответ: 3

Тип 3. Задан алгоритм для исполнителя Чертежник с фиксированным набором команд, определяющий перемещение исполнителя на плоскости. Требуется ответить на поставленный в задаче вопрос.

Исполнитель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плоскости, остав­ляя след в виде линии. Чертёжник может вы­пол­нять команду  Сместиться на (a, b) (где a, b — целые числа), пе­ре­ме­ща­ю­щую Чертёжника из точки с координатами (x, у) в точку с ко­ор­ди­на­та­ми (x + а, у + b). Если числа a, b положительные, зна­че­ние соответствующей ко­ор­ди­на­ты увеличивается; если отрицательные, уменьшается.

Например, если Чертёжник на­хо­дит­ся в точке с координатами (4, 2), то ко­ман­да Сместиться на (2, −3) пе­ре­ме­стит Чертёжника в точку (6, −1).

Запись

Повтори k раз

Команда1 Команда2 Ко­ман­даЗ

Конец

означает, что по­сле­до­ва­тель­ность команд Команда1 Команда2 КомандаЗ по­вто­рит­ся k раз.

Пример 3. 1.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 2 раз

Команда1

Сместиться на (3, 2)

Сместиться на (2, 1)

Конец

Сместиться на (−6, −4)

После выполнения этого алгоритма Чертёжник вернулся в исходную точку. Какую команду надо поставить вместо команды Команда1?
1)Сместиться на (−2, −1)
2)Сместиться на (1, 1)
3)Сместиться на (−4, −2)
4)Сместиться на (2, 1)

Решение.

В задаче сказано, что Чертежник вернулся в исходную точку, то есть нужно найти такое значение Команда1, которое сведет значение всех ходов Чертежника к нулю. Для решения данной задачи подсчитаем пройденное расстояние по осям абсцисс и ординат, чтобы определить, на сколько Чертежник отошел от исходной точки. Для этого складываем координаты в заданных командах с учетом цикла:

По оси абсцисс: 2 * (3 + 2) – 6 = 4

По оси ординат: 2 * (2 + 1) – 4 = 2

С учетом того, что Команда1 также выполнялась 2 раза, то делим полученный результат (4, 2) на 2 и берем его с обратным знаком, тогда получаем значение

Команда1 = (4, 2) * (-1) / 2 = (-2, -1)

Ответ: 1

Пример 3. 2.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 7 paз

Сместиться на (−1, 2)

Сместиться на (−2, 2)

Сместиться на (4, −4)

Конец

Каковы координаты точки, с которой Чертёжник начинал движение, если в конце он оказался в точке с координатами (0, 0)?

1) (7, 0)
2) (−7, 0)
3) (0, −7)
4) (0, 7)

Решение.

В задаче сказано, что Чертежник вернулся в начало координат, значит, нужно подсчитать пройденное им расстояние и взять его с обратным знаком. Для этого складываем координаты в заданных командах с учетом цикла:

По оси абсцисс: 7 * ( –1 – 2 + 4 ) = 7

По оси ординат: 7 * (2 + 2 – 4) = 0

Для обнуления результата (7, 0) берем его с обратным знаком и получаем (-7, 0).

Ответ: 2

Пример 3. 3.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 7 paз

Сместиться на (−1, 2)

Сместиться на (−2, 2)

Сместиться на (4, −5)

Конец

Каковы координаты точки, с которой Чертёжник начинал движение, если в конце он оказался в точке с координатами (1, 1)?
1) (6, 8)
2) (−6, 8)
3) (8, −6)
4) (8, 6)

Решение.

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

По оси абсцисс: 7 * ( –1 – 2 + 4 ) = 7 - 1= 6

По оси ординат: 7 * (2 + 2 – 5) – 1 = -8

Тогда координаты начальной точки будут (6, -8) * (-1) = (-6, 8)

Ответ: 2

Пример 3. 4.

Чертёжнику был дан для исполнения следующий алгоритм:

Повтори 5 paз

Сместиться на (0, 1)

Сместиться на (−2, 3)

Сместиться на (4, −5)

Конец

Координаты точки, с которой Чертёжник начинал движение, (3, 1). Каковы координаты точки, в которой он оказался?
1) (15, −6)
2) (14, −5)
3) (13, −4)
4) (12, −3)

Решение.

Так как требуется найти координаты конечной точки, то нужно посчитать все расстояние, пройденное Чертежником, и прибавить к нему координаты конечной точки. С учетом цикла получаем:

по оси абсцисс: 5 * ( 0 – 2 + 4 ) + 3 = 13

по оси ординат: 5 * (1 + 3 – 5) + 1 = - 4

Тогда координаты конечной точки (13, -4)

Ответ: 3

Пример 3. 5.

Чертёжнику был дан для исполнения следующий алгоритм:

Сместиться на (−1,1)

Повтори 4 раз

Сместиться на (3,1)

Сместиться на (0, 2)

Сместиться на (−1, 4)

Конец

На какую команду можно заменить этот алгоритм?
1)Сместиться на (8, 28)
2)Сместиться на (7, 29)
3)Сместиться на (−8, −28)
4)Сместиться на (−7, −29)

Решение.

Для ответа на вопрос достаточно найти сумму координат по обеим осям. С учетом цикла получаем:

по оси абсцисс: -1 + 4 * ( 3 + 0 - 1 ) = 7

по оси ординат: 1 + 4 * (1 + 2 + 4) = 29

Тогда требуемой командой будет: Сместиться на (7, 29)

Ответ: 2

Тип 4. Задан алгоритм для исполнителя Черепашка с фиксированным набором команд, задающий перемещение исполнителя на плоскости. Требуется ответить на поставленный в задаче вопрос.

Исполнитель Че­ре­паш­ка пе­ре­ме­ща­ет­ся на экра­не компьютера, остав­ляя след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его движения.

У ис­пол­ни­те­ля су­ще­ству­ет две команды: 

Вперёд n (где n — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Че­ре­паш­ки на n шагов в на­прав­ле­нии движения; 

Направо m (где m — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрелке.

За­пись Повтори k [Команда1 Команда2 КомандаЗ] означает, что по­сле­до­ва­тель­ность ко­манд в скоб­ках по­вто­рит­ся k раз.

Поскольку в данных алгоритмах в цикле выполняются одинаковые команды, то в результате работы Черепашки на экране могут появиться:

• правильная геометрическая фигура, если количество шагов (циклов) Черепашки достаточно для рисования всех сторон фигуры с учетом заданных углов;

• незамкнутая ломаная линия – если шагов не достаточно.

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

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

Команда Вперед n вопросов при выполнении не вызывает.

При выполнении команды Направо m нужно помнить, что Черепашка только поворачивается на нужный угол вправо, не смещаясь с заданной точки. При этом внутренний угол фигуры вычисляется по формуле 180 – m, а количество вершин многоугольника – по формуле 360/(180 – m).

Пример 4. 1.

Черепашке был дан для ис­пол­не­ния сле­ду­ю­щий алгоритм: 

Повтори 9 [Вперёд 50 На­пра­во 60].

Какая фи­гу­ра по­явит­ся на экране?

1) правильный шестиугольник

2) правильный треугольник

3) незамкнутая ло­ма­ная линия

4) правильный девятиугольник

Решение.

Внутренний угол фигуры будет равен 180 – 60 = 120 градусов, а количество вершин равно 360/(180 – 120) = 6. Количество циклов превышает количество углов, то в результате работы Черепашки получаем правильный шестиугольник.

Ответ: 1

Пример 4.2.

Черепашке был дан для ис­пол­не­ния сле­ду­ю­щий алгоритм: 

 Повтори 5 [Вперёд 80 На­пра­во 90].

Какая фи­гу­ра по­явит­ся на экране?

1) незамкнутая ло­ма­ная линия

2) правильный девятиугольник

3) правильный пятиугольник

4) правильный четырёхугольник

Решение.

Внутренний угол фигуры будет равен 180 – 90 = 90 градусов, а количество циклов больше 4, то в результате работы Черепашки получаем квадрат (правильный четырехугольник).

Ответ: 4

Пример 4.3.

Черепашке был дан для ис­пол­не­ния сле­ду­ю­щий алгоритм: 

 Повтори 6 [Вперёд 5 На­пра­во 30]

Какая фи­гу­ра по­явит­ся на экране?

1) не­за­мкну­тая ло­ма­ная линия

2) пра­виль­ный тре­уголь­ник

3) пра­виль­ный пятиугольник

4) пра­виль­ный шестиугольник

Решение.

Внутренний угол фигуры будет равен 180 – 30 = 150 градусов, а количество вершин равно 360/(180 – 150) = 12. Так как количество циклов меньше количества вершин, то в результате работы Черепашки получаем незамкнутую ломаную линию.

Ответ: 1

Пример 4.4.

При выполнении какого из перечисленных ниже алгоритмов на экране появился правильный треугольник?
1) Повтори 3 [Вперёд 50 Направо 20 Направо 25]
2) Повтори 3 [Вперёд 50 Направо 100 Направо 20]
3) Повтори 6 [Вперёд 50 Направо 10 Направо 20]
4) Повтори 6 [Вперёд 50 Направо 20 Направо 40]

Решение.

Внутренний угол равностороннего треугольника равен 60 градусов, то ищем среди указанных вариантов тот, в котором сумма углов поворота равна 180-60 = 120 градусов. Это будет вариант Повтори 3 [Вперёд 50 Направо 100 Направо 20].

Ответ: 2