Практикум для подготовки к ЕГЭ-2021, задание 5, часть 1. Анализ простых алгоритмов для конкретного исполнителя с фиксированным набором команд (базовый уровень, примерное время решения – 4 минуты)
Исполнители бывают двух видов - формальные и неформальные.
Формальный исполнитель одну и ту же команду всегда выполняет одинаково.
Неформальный исполнитель может выполнять команду каждый раз по-разному.
Например, набранный и сохраненный на компьютере текст всегда будет распечатан в одном и том же виде.
Человек же, даже переписывая готовый текст, может написать его с различиями – например, аккуратно или безобразным почерком, с ошибками или без них.
Как правило, человек выступает в роли неформального исполнителя.
Формальными исполнителями являются преимущественно технические устройства.
Человек в роли неформального исполнителя сам отвечает за свои действия.
За действия формального исполнителя отвечает управляющий им объект.
Каждый исполнитель создается для решения задач определённого класса (круга).
Область, обстановку, условия, в которых действует исполнитель, принято называть средой данного исполнителя.
Предписание о выполнении отдельного законченного действия исполнителя называется командой. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует систему команд этого исполнителя.
Алгоритм – это порядок решения задачи, описанный в ней самой. Линейный алгоритм описывает действия, выполняемые в строгой последовательности друг за другом. Решение задачи по готовому алгоритму требует от исполнителя только строгого следования заданным предписаниям.
Исполнитель не вникает в смысл того, что он делает, и не рассуждает, почему он поступает так, а не иначе — он действует формально.
Так следует поступать и нам при решении задач для формального исполнителя.
Рассмотрим задачи четырех различных типов.
Тип 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, дает нам однозначно верное решение:
При помощи элементарных рассуждений и вычислений получаем (здесь символ V обозначает корень квадратный из числа):
V 49 = 7 + 3 = 10 + 3 = 13 + 3 = 16, V16 = 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
© 2018–2024 Звездина Вера Алексеевна, v_zvezdina@mail.ru
