В результате получилась строка 21 какое наименьшее количество единиц могло быть в исходной строке

ЕГЭ по информатике (задача 12 сколько 3 было, если получилась строка, содержащая 31 единицу, 24 двойки и 46 троек)

(№ 3844) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для исполнителя Редактор:

Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 31 единицу, 24 двойки и 46 троек. Сколько троек было в исходной строке?

Решение на Pyton:

Решение через систему уравнений:

По условию задачи при замене могут получиться следующие конечные варианты:

02 -> 31 03 -> 3112 01 -> 311230

03 -> 12 01 -> 1230.

Т.е. 01 при замене даст одну «3», 02 — две «1», одну «2» и две «3», а 03 — одну «1», одну «2» и одну «3». Обозначим количество «1» в исходной строке как a, «2» — как b, «3» — как c, и составим систему уравнений:

ЕГЭ задача 12

Ответ: 17 цифр «3»

Добавить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

ЕГЭ, вопрос 12: Умение анализировать результат исполнения алгоритма

Проверяемые элементы содержания по спецификации (2021): Умение анализировать результат исполнения алгоритма.

Кодификатор 1.6.2/1.1.3. Уровень сложности П, 1 балл.

Время выполнения — 4 минуты.

Для выполнения задания необходимо знание основ программирования: циклов, условных операторов, функций.

Материал изучен полностью. Вопросительные знаки связаны с многолетним мусоленьем Робота. Он может быть заменен.

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

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

Замечание. Задачи этого типа активно используются для олимпиады в 7 классе.

Разбор варианта демоверсии 2017. Исполнитель Редактор
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 69 идущих подряд цифр 8? В ответе запишите полученную строку. Так как речь идет об анализе результатов многократной (разумно) обработки данных, имеет смысл расписать каждую итерацию (прохождения цикла).

Исходные данные.
Обрабатываются «кусочки строки» по 4 цифры, сразу преобразуем ее в смысловой вид: 17 раз по «8888» + «8» (далее 17*»8888″ + «8»).

1. Каждое «8888» заменится на «33». Итог: 17*»33″ + «8» или 8*»3333″+»338″.

2. Каждое «3333» заменится на «88». Итог: 8*»88″ + «338» или 4*»8888″+»338″.

3. Каждое «8888» заменится на «33». Итог: 4*»33″ + «338» или 2*»3333″+»338″.

4. Каждое «3333» заменится на «88». Итог: 2*»88″ + «338» или 1*»8888″+»338″.

5. «8888» заменится на «33». Итог: *»33″ + «338» или «3333»+»8″.

6. «3333» заменится на «88». Итог: «88» + «8» или «888». Так как знаков осталось три, цикл ПОКА и программа завершится

Строка «888» и будет ответом.

Запись можно значительно сократить, например, для первой строки:

Большинство источников предложит вам составить таблицу. Иногда это действительно нужно. Например, для нескольких переменных. Но, прежде чем составлять таблицу, приходится продумывать ее структуру, при ошибке — перечерчивать, а это — время, которого на экзамене нет. В конце-концов, можно начать запись в текстовом варианте, а, когда станет понятна таблица, перенести информацию в нее.

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

Задания

Описания исполнителей из заданий

Исполнитель Редактор.
Получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл выполняется, пока условие истинно. В конструкции выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Исполнитель Чертёжник.
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b — целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x+a; y+b).
Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
Цикл
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Исполнитель Робот.
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды — проверки условия.
Команды-приказы: вверх, вниз, влево, вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.
Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно, снизу свободно, слева свободно, справа свободно.
Цикл
выполняется, пока условие истинно.
В конструкции
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Исполнитель Арифметик.
На этом исполнителе показан пример записи/чтения программы для всех исполнителей аналогичного типа (производящих арифметические действия над числами).
У исполнителя Арифметик две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 3.
Первая из них увеличивает число на экране на 2, вторая утраивает его.
Например, 21211 — это программа которая преобразует число 1 в число 19.
Исполнитель Квадратор.
У исполнителя Квадратор две команды, которым присвоены номера:
1. возведи в квадрат,
2. прибавь 1.
Первая из них возводит число на экране в квадрат, вторая увеличивает его на 1.
Исполнитель Утроитель.
У исполнителя Утроитель две команды, которым присвоены номера:
1. она может отличаться, см. в конкретных заданиях
2. умножь на три
Первая из них. вторая — утраивает число.
Исполнитель Калькулятор. Список команд различается. См. задания. Исполнитель
Исполнитель
—>

Непосредственно задания

Демо 2021 ().
Демо 2020 (14). Исполнитель Редактор
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.
Демо 2019 (14). Исполнитель Редактор
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 82 идущих подряд цифр 1? В ответе запишите полученную строку.
Демо 2018 (14). Исполнитель Чертёжник
Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):
В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?
D2018 (14). Исполнитель Редактор
Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке, состоящей из единицы, за которой следуют 80 нулей подряд.
В ответе запишите только количество нулей в получившейся строке.
R2018 (14). Исполнитель Редактор
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из одной единицы и 75 стоящих справа от нее нулей? В ответе запишите сколько нулей будет в конечной строке.
Демо 2017 (14). Исполнитель Редактор
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 69 идущих подряд цифр 8? В ответе запишите полученную строку.
Демо 2016 (14). Исполнитель Редактор
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8?
В ответе запишите полученную строку.
Демо 2016 (6-2). Исполнитель Калькулятор
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5.
Например, программа 2121 — это программа которая преобразует число 1 в число 37.
Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.
Демо 2015 (14). Исполнитель Чертёжник
Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):
Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку.
Демо 2014 (A13). Исполнитель Робот
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка А1)?
1) 14; 2) 18; 3) 20; 4) 22.
Демо 2014 (B1). Исполнитель Квадратор
У исполнителя Квадратор две команды, которым присвоены номера:
1. возведи в квадрат,
2. прибавь 1.
Первая из них возводит число на экране в квадрат, вторая увеличивает его на 1.
Запишите порядок команд в программе, которая преобразует число 1 в число 10 и содержит не более 4 команд.
Демо 2013 (A13). Исполнитель Робот
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка А1)?
1) 8; 2) 12; 3) 17; 4) 21.
Демо 2013 (B1). Исполнитель Арифметик
Запишите порядок команд в программе преобразования числа 3 в число 69, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Демо 2012 (A13). Исполнитель Робот
Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?
1) 1; 2) 3; 3) 5; 4) 7.
Демо 2012 (B2). Исполнитель Утроитель
У исполнителя Утроитель две команды, которым присвоены номера:
1. вычти 2
2. умножь на три
Первая из них уменьшает число на экране на 2, вторая — утраивает его.
Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд, указывая лишь номера команд.
Демо K-2012 (B8). Исполнитель Робот

Copyright © 1993–2022 Мацкявичюс Д.А. Все права защищены.
Никакая часть сайта не может быть воспроизведена никаким способом без письменного разрешения правообладателя и явной ссылки на данный ресурс.

Информатика ЕГЭ 12 задание разбор

12-е задание: «Алгоритмы с циклами и условиями»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 4 минуты.

Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма

Плейлист видеоразборов задания на YouTube:

Исполнитель Редактор и цепочки символов

📹 Учимся по видео (решения разного типа программным способом):

Какая строка получится?

А) заменить ( v , w )
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w .

Б) нашлось ( v )
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 40 идущих подряд цифр 123? В ответе запишите полученную строку.

Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «12» или цепочка «333»;
если в строке есть «12», то тогда эта цепочка заменяется на «3»;
если в строке нет цепочки «12», но есть «333», то цепочка «333» заменяется на «3».
Теперь вернемся к условию нашей задачи. Условие цикла истинно, соответственно выполняем блок ЕСЛИ, т.е. делаем замену: в каждом из 40 чисел ‘123‘, заменяем 12 на 3. Получим 40 + 40 = 80 троек (40 троек было изначально и 40 добавилось);
Так как больше чисел 12 у нас не встречается, то работает блок ИНАЧЕ. Сколько раз можно заменить в 80 подряд идущих тройках три тройки на одну? 80 делим на 3 получаем 26 раз + 2 тройки в остатке. Итого осталось 28 троек;
Теперь из 28 троек сколько раз мы можем заменить три тройки на одну? 28 делим на 3 и получаем 9 раз + 1 тройка в остатке. Итого 10 троек;
Делаем то же самое: 10 делим на 3 получаем 3 раза + 1 тройка в остатке = 4 тройки
Последний раз делим 4 на 3, получаем 1 тройку + 1 = 2 тройки

Результат: 33

✎ Решение 2. Программное:
Pascalabc.net:

begin var s := ‘123’ * 40; while (’12’ in s) or (‘333′ in s) do begin if ’12’ in s then s := s.Replace(’12’, ‘3’, 1) else s := s.Replace(‘333’, ‘3’, 1); end; print(s); end.

begin var s := ‘123’*40; var p1 := Pos(’12’,s); var p2 := Pos(‘333’,s); while (p1 > 0) or (p2 > 0) do begin if p1 > 0 then begin Delete( s, p1, 2 ); Insert( ‘3’, s, p1 ); end else begin Delete( s, p2, 3 ); Insert( ‘3’, s, p2 ); end; p1 := Pos(’12’,s); p2 := Pos(‘333’,s); end; write(s); end.

s = 40*’123′ while "12" in s or "333" in s: if "12" in s: s = s.replace( "12", "3", 1 ) else: s = s.replace( "333", "3", 1 ) print(s)

А) заменить ( v , w )
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w .

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 71 идущих подряд четверок цифр 1122? В ответе запишите полученную строку.

Ответ: 22

Для удобства решения сначала сократим исходную цепочку до одной группы цифр:
Условие цикла истинно (ПОКА нашлось (12)), и условие в цикле истинно (ЕСЛИ нашлось (12)), значит, делаем замену: в первой группе цифр «1122«, заменяем 12 на 2:
Затем опять возвращаемся к условию цикла: условие цикла истинно (ПОКА нашлось (12)), и условие в цикле истинно (ЕСЛИ нашлось (12)), делаем опять замену: в первой группе цифр «122«, заменяем 12 на 2:
Таким образом, получаем, что за две итерации цикла (2 шага), одна группа цифр превращается в две двойки.
Поскольку по условию имеем 71 группу цифр, то, чтобы узнать сколько двоек мы получим в результате выполнения условия ЕСЛИ нашлось (12), нам необходимо 71 умножить на 2 (кол-во двоек, получаемых из одной группы цифр):
То есть в итоге работы цикла и условия ЕСЛИ нашлось (12) мы получили всего 142 двоек.
Теперь работает условие ИНАЧЕ заменить (222, 2). Из 142 двоек каждые три заменяем на одну. Чтобы рассчитать итоговое количество двоек, необходимо 142 разделить на 3 (т.е. сколько раз можно заменять тройки двоек на одну двойку). Делить необходимо до тех пор, пока работает условие ИНАЧЕ заменить (222, 2):
В итоге осталось 2 двойки.

✎ Решение 2. Программное:
Pascalabc.net:

begin var s := ‘1122’ * 71; while (’12’ in s) or (‘222′ in s) do begin if ’12’ in s then s := s.Replace(’12’, ‘2’, 1) else s := s.Replace(‘222’, ‘2’, 1); end; print(s); end.

begin var s := ‘1122’*71; var p1 := Pos(’12’,s); var p2 := Pos(‘222’,s); while (p1 > 0) or (p2 > 0) do begin if p1 > 0 then begin Delete( s, p1, 2 ); Insert( ‘2’, s, p1 ); end else begin Delete( s, p2, 3 ); Insert( ‘2’, s, p2 ); end; p1 := Pos(’12’,s); p2 := Pos(‘222’,s); end; write(s); end.

s = 71*’1122′ while "12" in s or "222" in s: if "12" in s: s = s.replace( "12", "2", 1 ) else: s = s.replace( "222", "2", 1 ) print(s)

А) заменить ( v , w )
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w .

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 200 идущих подряд цифр 7? В ответе запишите полученную строку.

Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «99» или цепочка «777»;
если в строке есть «777», то тогда эта цепочка заменяется на «9»;
если в строке нет цепочки «777», но есть «99», то цепочка «99» заменяется на «7».
Теперь вернемся к условию нашей задачи. Условие цикла истинно, условие ЕСЛИ нашлось 777 тоже истинно, делаем замену:
сколько раз можно заменить в 200 семерках три семерки на одну девятку? 200 делим на 3 получаем 66 замен, т.е. 66 цифр «9» + 2 семерки в остатке;
После выполнения этих преобразований условие ЕСЛИ нашлось 777 ложно. Значит, выполняется блок ИНАЧЕ: Заменить 99 на 7:
[66 цифр «9»] + «77» -> «7» + [64 цифры «9»] + «77»:
«7» + [64 цифры «9»] + «77» -> «7» + «7» + [62 цифры «9»] + «77»:
«77» + [62 цифры «9»] + «77» -> «7» + «77» + [60 цифр «9»] + «77»:
Затем условие ЕСЛИ нашлось 777 опять становится истинным. Выполняется команда Заменить 777 на 9:
Вернулись к той же «картине», что и после первого пункта. За эти шаги произошли преобразования, заменившие 66 девяток на 61 девятку, т.е. количество цифр «9» уменьшилось на 5 раз, а две цифры «77» так и остались в конце общей цепочки.
Чтобы рассчитать итоговое количество цифр «9», необходимо понять, сколько раз можно вычитать из 61 по 5 девяток:
Таким образом, после выполнения алгоритма, остается одна цифра «9» (в остатке) и в конце так и останутся две семерки: 977 .

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить ( v , w )
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w .

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 90 идущих подряд цифр 3 и в конце одной цифры 1? В ответе запишите полученную строку.

✎ Решение 1. Программное:

Pascalabc.net:

begin var s := ‘3’ * 90 + ‘1’; while (‘331’ in s) or (‘166’ in s) do begin if ‘331’ in s then s := s.Replace(‘331′, ’16’, 1) else s := s.Replace(‘166′, ’31’, 1); end; print(s); end.

begin var s := ‘3’*90 + ‘1’; var p1 := Pos(‘331’,s); var p2 := Pos(‘166′,s); while (p1 > 0) or (p2 > 0) do begin if p1 > 0 then begin Delete( s, p1, 3 ); Insert( ’16’, s, p1 ); end else begin Delete( s, p2, 3 ); Insert( ’31’, s, p2 ); end; p1 := Pos(‘331’,s); p2 := Pos(‘166’,s); end; write(s); end.

s = 90*’3’+’1′ while "331" in s or "166" in s: if "331" in s: s = s.replace( "331", "16", 1 ) else: s = s.replace( "166", "31", 1 ) print(s)

Сколько удалено?

А) заменить ( v , w )
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w .

Б) нашлось ( v )
Дана программа для исполнителя Редактор:

Дана строка, состоящая из 500 цифр 5. Сколько пятёрок было удалено за время обработки строки по этой программе?

Ответ: 561

Выполним несколько итераций цикла ПОКА. Когда мы получим ту же самую последовательность цифр пять, за исключением их количества — остановимся:
Остановились, так как мы пришли к исходной последовательности цифр пять. Проанализируем действия программы за этот фрагмент выполнения: было удалено 9 пятерок и одна пятерка добавилась. Ключевой вывод: было удалено 9 пятерок.
Всего за выполнение этого фрагмента программы «ушло» 8 пятерок: 500 — 492 = 8 . Посчитаем, сколько раз можно выполнить данный фрагмент:
Т.е. 62 раза выполняется данный фрагмент и 4 цифр 5 еще остается (остаток = 4). Поскольку за одно выполнение фрагмента было удалено 9 цифр 5, посчитаем, сколько удалится за 62 выполнения:
558 цифр 5 было удалено. Посмотрим выполнение программы над оставшимися 4 цифрами 5:
Итого получаем удаленных цифр 5:

✎ Решение 2. Программное:
Pascalabc.net:

begin var s := ‘5’ * 500; var k := 0; while (‘555’ in s) or (‘333’ in s) do begin if ‘333’ in s then s := s.Replace(‘333’, ‘5’, 1) else begin s := s.Replace(‘555’, ‘3’, 1); k += 3; end; end; print(k); end.

begin var k:= 0; var s := ‘5’*500 ; var p1 := Pos(‘555’,s); var p2 := Pos(‘333’,s); while (p1 > 0) or (p2 > 0) do begin if p2 > 0 then begin Delete( s, p2, 3 ); Insert( ‘5’, s, p2 ); end else begin Delete( s, p1, 3 ); Insert( ‘3’, s, p1 ); inc(k,3); end; p1 := Pos(‘555’,s); p2 := Pos(‘333’,s); end; write(k); end.