Задача к ЕГЭ по информатике на тему «исполнитель «редактор»

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

А) заменить (v, w).

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

Например, выполнение команды заменить(111, 27) преобразует строку 05111150 в строку 0527150.

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

Б) нашлось (w).

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

Цикл

ПОКА *условие*

*последовательность команд*

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ *условие*

ТО *команда 1*

ИНАЧЕ *команда 2*

КОНЕЦ ЕСЛИ

выполняется команда 1 (если условие истинно) или команда 2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО

ПОКА нашлось (>0) ИЛИ нашлось (>1) ИЛИ нашлось (>2)

ЕСЛИ нашлось (>0)

ТО заменить (>0, 22>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>1)

ТО заменить (>1, 2>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>2)

ТО заменить (>2, 1>)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход приведённой выше програмы поступает строка, начинающаяся с символа «>», а затем содержащая 15 цифр 0, n цифр 1 и 15 цифр 2, расположенных в произвольном порядке. Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым числом.

Решение 1

Рассмотрим переходы цифр:

$0 → 22$
$1 → 2$
$2 → 1$

Получаем, что каждый ноль это $+4$ в сумму, каждая единица $+2$ , каждая двойка $+ 1$ . Посчитаем пока что, какая будет сумма после обработки двоек и нулей. $S = 15⋅4 + 1⋅15 = 75$ , ближайшее простое число это $79$ , нам не хватает $4$ до такой суммы. Каждая единица это $+ 2$ , значит, чтобы получить $+ 4$ нам нужно две единицы.

Решение 2

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1

for n in range(0, 100):
    s = ’>’ + ’0’ * 15 + ’1’ * n + ’2’ * 15
    while ’>0’ in s or ’>1’ in s or ’>2’ in s:
        if ’>0’ in s:
            s = s.replace(’>0’, ’22>’)
        if ’>1’ in s:
            s = s.replace(’>1’, ’2>’)
        if ’>2’ in s:
            s = s.replace(’>2’, ’1>’)
    summa = 0
    for i in s[0:-1]:
        summa += int(i)
    if is_prime(summa):
        print(n)
        break

Ответ: 2

Задача к ЕГЭ по информатике на тему «исполнитель «редактор» – прочие прототипы» №1