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

12. Выполнение алгоритмов для исполнителей: Определите количество нулей в строке, получившейся в…

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

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

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

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

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

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

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

Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке $\underbrace{100\ldots00}_{80}$, т.е. к строке, состоящей из единицы, за которой следуют $80$ нулей подряд. В ответе запишите только количество нулей в получившейся строке.

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

Единица в строке всё время ровно одна: обе замены её сохраняют ($10 \to 0001$) либо уничтожают ($1 \to 00$), а появиться новой неоткуда. Поэтому достаточно следить за тем, сколько нулей стоит справа от единицы.

Основная ветка. Пока справа от единицы есть хотя бы один нуль, цепочка $10$ находится, и работает замена $10 \to 0001$. Что она делает: убирает один нуль справа от единицы и дописывает три нуля слева от неё. Единица как бы сдвигается вправо через строку, оставляя за собой по три нуля вместо одного.

Баланс нулей за такой шаг: $-1$ справа и $+3$ слева, то есть общее количество нулей растёт на $2$.

Сколько таких шагов. Справа от единицы изначально $80$ нулей, и каждый шаг съедает ровно один, поэтому замена $10 \to 0001$ сработает $80$ раз. К этому моменту нулей станет $80 + 2 \cdot 80 = 240$, а единица окажется последним символом строки.

Завершающий шаг. Теперь цепочки $10$ нет, но единица есть, поэтому срабатывает ветка ИНАЧЕ: $1 \to 00$, что добавляет ещё $2$ нуля. Единиц в строке не остаётся, условие цикла становится ложным, и программа завершается. Всего цикл отработал $81$ шаг.

Итого нулей: $240 + 2 = 242$ (и это вся длина строки, поскольку единицы в ней больше нет).

Общая формула для $k$ нулей на входе: $3k + 2$. Проверка на малых значениях: при $k = 1$ получается $5$, при $k = 2$ — $8$, при $k = 3$ — $11$; при $k = 80$ имеем $3 \cdot 80 + 2 = 242$.

def run(s):
    while '1' in s:
        if '10' in s:
            s = s.replace('10', '0001', 1)   # только первое вхождение
        else:
            s = s.replace('1', '00', 1)
    return s

print(run('1' + '0' * 80).count('0'))   # 242
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

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