Бесплатный интенсив по информатике
3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и
многое другое.
Курс стартует 25 марта.
Подробнее об интенсиве
Задание 12. Выполнение алгоритмов исполнителей с фиксированным набором команд. ЕГЭ 2024 по информатике
Средний процент выполнения: 59.9%
Ответом к заданию 12 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды. В обеих командах v и w обозначают цепочки цифр.
A) заменить(v,w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Например, выполнение команды заменить(111,27) преобразует строку 051111105 в строку 05271105. Если в строке нет вхождений цепочки v, то выполнение команды заменить(v,w) не меняет эту строку.
Б) нашлось(v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА
условие последовательность команд
КОНЕЦ ПОКА
означает, что последовательность команд выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 38 идущих подряд цифр 5? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (555) ИЛИ нашлось (333)
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
ИНАЧЕ заменить (333, 5)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
1) Приоритет в замене пятёрок, значит сначала заменятся все пятёрки на тройки:
из 38 пятёрок получится 12 троек и 2 пятёрки
2) Далее обработав подстроку из 9 троек понимаем, что она сокращается до одной тройки, значит алгоритм сокращает по 8 троек. 12 / 8 = 1,... то есть из 12 троек одна группа из 8 троек будет сокращена и останется 4 тройки и те две пятёрки из первого пункта
3) Получили строку 333355. Алгоритм заменит три тройки на пятёрку и прекратит своё выполнение, поскольку условие цикла далее не выполянется
Результат: 5355
Решение при помощи программы на С++:
#include <iostream>
#include <string>
using namespace std;
const size_t np = string::npos;
int main() {
string text = "";
for (int i = 0; i < 38; ++i)
text += "5";
while (text.find("555") != np || text.find("333") != np){
if (text.find("555") != np)
text.replace(text.find("555"), 3, "3");
else if (text.find("333") != np)
text.replace(text.find("333"), 3, "5");
}
cout << text;
return 0;
}
Задача 2
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x +a, y +b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные — уменьшается. Например, если Чертёжник находится в точке с координатами (2, 3), то команда Сместиться на (-5,2) переместит Чертёжника в точку (−3, 5).
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и величины смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
Сместиться на (-11,32)
ПОВТОРИ ... РАЗ
Сместиться на (15,-12)
Сместиться на (... , ...)
КОНЕЦ ПОВТОРИ
Сместиться на (-19,38)
КОНЕЦ
В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ ... РАЗ»?.
Решение
Пусть первоначально Чертёжник находился в точке с координатами (x, y). Обозначим через n число повторений цикла, через a и b смещения по оси x и y в команде Сместиться на (... , ...). Тогда после выполнения заданного алгоритма Чертёжник переместится в точку с координатами (x − 11 + n(15 + a) − 19, y + 32 + n(−12 + b) + 38) = (x − 30 + n(15 + a), y + 70 + n(b − 12)).
После выполнения программы Чертёжник возвратится в исходную точку, из которой он начал движение, то есть в точку с координатами (x, y). Следовательно, должны выполняться условия
$\{\table\x − 30 + n(15 + a) = x; \y + 70 + n(b − 12) = y;$
Отсюда
$\{\table\n(15 + a) = 30; \n(b − 12) = −70;$
Наибольшее возможное n является наибольшим общим делителем чисел 30 и −70. Следовательно, n = 10.
Задача 3
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды. В обеих командах v и w обозначают цепочки цифр.
A) заменить (v,w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (222,58)
преобразует строку 45222222234 в строку 4558222234.
Если в строке нет вхождений цепочки v, то выполнение команды
заменить (v,w)
не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
означает, что последовательность команд выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 80 идущих подряд цифр 1? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (2121) ИЛИ нашлось (111)
ЕСЛИ нашлось (2121)
ТО заменить (2121, 2)
ИНАЧЕ заменить (111, 12)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
Выпишем первые несколько строк, которые будут являться результатом работы исполнителя, после входа в цикл ПОКА.
| Шаг | Входная строка | нашлось(2121) | заменить(2121,2) | заменить(111,12) |
| 1 |  | нет | – |  |
| 2 |  | нет | – |  |
| 3 |  | да |  | - |
| 4 |  | нет | – |  |
| 5 |  | да |  | - |
| 6 |  | нет | – |  |
| 7 |  | да |  | - |
| ... |
Заметим, что, начиная со второго шага цикла ПОКА, на каждом втором шаге входная строка имеет одинаковое строение. Например, рассмотрим значения входных строк на 2, 4, 6, 8, . . .шагах.
На шаге 2 строка имеет вид 
Всего 79 цифр. На каждом из шагов: 4, 6, 8, . . . входная строка также имеет вид 12 
, при этом в каждой из перечисленных строк количество цифр уменьшается на 4. Так на шаге 4 в строке 75(= 79 − 4) цифры. На шаге 6 в строке 71(= 75 − 4) цифр.
Количество цифр исходной строки на каждом втором шаге цикла уменьшается на 4. Если мы разделим количество цифр в входной последовательности на втором шаге на 2, то целая честь результата деления, умноженная на 4, будет номером шага, на котором входная строка будет иметь вид 12.
79/4 = 19, 75; 19 · 2 = 38.
Учитывая первую строку получаем, что на 39 шаге цикла входная строка будет иметь вид 12. При этом в строке будет 79 − 4·19 = 3 цифры. То есть входная строка будет иметь вид 121.
Так как для числа 121 условие нашлось (2121) ИЛИ нашлось (111), входящее в цикл ПОКА, ложно, то на этом цикл оканчивает свою работу. В результате будет получена строка 121.
Задача 4
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные—уменьшается.
Например, если Чертёжник находится в точке (2, 3), то команда Сместиться на (-5,2) переместит Чертёжника в точку (−3, 5).
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):
НАЧАЛО
Сместиться на (6,12)
ПОВТОРИ n РАЗ
Сместиться на (a, b)
Сместиться на (–22,-8)
Сместиться на (25,16)
КОНЕЦ ПОВТОРИ
Сместиться на (12,-21)
КОНЕЦ
Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку, из которой он начал движение.
Решение
Задача 5
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x +a, y +b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные—уменьшается. Например, если Чертёжник находится в точке с координатами (2, 3), то команда Сместиться на (-5,2) переместит Чертёжника в точку (−3, 5).
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и величины смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
Сместиться на (52,-26)
ПОВТОРИ ... РАЗ
Сместиться на (-35,-10)
Сместиться на (... , ...)
КОНЕЦ ПОВТОРИ
Сместиться на (-7,-34)
КОНЕЦ
В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ ... РАЗ»?
Решение
Задача 6
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды. В обеих командах v и w обозначают цепочки цифр.
A) заменить(v,w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Например, выполнение команды
заменить(111,27)
преобразует строку 051111105 в строку 05271105.
Если в строке нет вхождений цепочки v, то выполнение команды
заменить(v,w)
не меняет эту строку.
Б) нашлось(v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».
Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
означает, что последовательность команд выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 45 идущих подряд цифр 9? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (999) ИЛИ нашлось (111)
ЕСЛИ нашлось (999)
ТО заменить (999, 1)
ИНАЧЕ заменить (111, 9)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
Задача 7
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды. В обеих командах v и w обозначают цепочки цифр.
A) заменить(v,w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить(222,58)
преобразует строку 45222222234 в строку 4558222234.
Если в строке нет вхождений цепочки v, то выполнение команды
заменить(v,w)
не меняет эту строку.
Б) нашлось(v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».
Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
означает, что последовательность команд выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 108 идущих подряд цифр 3? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (444) ИЛИ нашлось (333)
ЕСЛИ нашлось (444)
ТО заменить (444, 3)
ИНАЧЕ заменить (333, 4)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение
Задача 8
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x +a, y +b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные — уменьшается.
Например, если Чертёжник находится в точке с координатами (2, 3), то команда Сместиться на (-5,2) переместит Чертёжника в точку (−3, 5).
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):
НАЧАЛО
ПОВТОРИ n РАЗ
Сместиться на (-24, -7)
Сместиться на (a, b)
Сместиться на (15, 23)
КОНЕЦ ПОВТОРИ
Сместиться на (9, 16)
КОНЕЦ
Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что Чертёжник, начав выполнение программы из точки с координатами (-18,14), после выполнения алгоритма окажется в точке (12, 15).
Решение
Задача 9
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a,b) (где a, b — целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные — уменьшается. Например, если Чертёжник находится в точке с координатами (2, 3), то команда Сместиться на (-5,2) переместит Чертёжника в точку (−3, 5).
Цикл
ПОВТОРИ число
РАЗ последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):
НАЧАЛО
ПОВТОРИ n РАЗ
Сместиться на (-24, -7)
Сместиться на (a, b)
Сместиться на (15, 23)
КОНЕЦ ПОВТОРИ
Сместиться на (19, 16)
КОНЕЦ
Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что Чертёжник, начав выполнение программы из точки с координатами (-18,14), после выполнения алгоритма окажется в точке (13, 16).
