Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

12. Выполнение алгоритмов для исполнителей: На вход приведённой ниже программе поступает строка…

Задание #298290
Решено верно
Решено неверно
Сообщить о проблеме

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

А) заменить ($v$, $w$).
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды заменить ($111$, $27$) преобразует строку $05111150$ в строку $0527150$. Если в строке нет вхождений цепочки $v$, то выполнение команды заменить ($v$, $w$) не меняет эту строку.

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

Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).

В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

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

НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
    ЕСЛИ нашлось (>1)
      ТО заменить (>1, 22>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>2)
      ТО заменить (>2, 2>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>3)
      ТО заменить (>3, 1>)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Ключ к задаче — понять роль символа «$>$». Во всех трёх заменах он стоит слева от цифры, а в результате оказывается справа от неё. Значит «$>$» работает как каретка, которая ползёт по строке слева направо и обрабатывает очередную цифру, а всё уже обработанное остаётся позади и больше не меняется.

Что происходит с каждой цифрой при проходе каретки:

  • цифра $1$ превращается в $22$;
  • цифра $2$ остаётся цифрой $2$;
  • цифра $3$ превращается в $1$.

Цикл завершается, когда каретка дойдёт до конца строки — тогда справа от «$>$» ничего нет и ни одно из условий не выполняется.

Отсюда видно, что порядок цифр в исходной строке вообще не важен: каждая цифра обрабатывается независимо, и суммарный вклад определяется только количествами. Считаем сумму по типам цифр.

Каждая из $11$ единиц даёт $22$, то есть вклад $2 + 2 = 4$: всего $11 \cdot 4 = 44$.

Каждая из $12$ двоек даёт $2$: всего $12 \cdot 2 = 24$.

Каждая из $30$ троек даёт $1$: всего $30 \cdot 1 = 30$.

Итоговая сумма равна $44 + 24 + 30 = 98$.

import random

def run(s):
    while '>1' in s or '>2' in s or '>3' in s:
        if '>1' in s:
            s = s.replace('>1', '22>', 1)    # только первое вхождение
        if '>2' in s:
            s = s.replace('>2', '2>', 1)
        if '>3' in s:
            s = s.replace('>3', '1>', 1)
    return s

d = list('1'*11 + '2'*12 + '3'*30)
random.shuffle(d)                            # порядок произвольный
r = run('>' + ''.join(d))
print(sum(int(c) for c in r if c.isdigit()))   # 98

При разных перемешиваниях исходной строки программа всегда даёт $98$, что подтверждает независимость результата от порядка цифр.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение