12. Сложные исполнители и алгоритмы

Исполнитель "Редактор" (страница 9)

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела 12. Сложные исполнители и алгоритмы:

Это старая версия каталога задач

Нажмите для перехода на новую версию

Решаем задачи
Задание 57 #15094

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

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

2. нашлось (v)

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

Дана программа для исполнителя Панцирь:

НАЧАЛО

ПОКА нашлось\((54)\) ИЛИ нашлось\((27)\)

ЕСЛИ нашлось\((55)\)

ТО заменить\((55, 2)\)

ИНАЧЕ ЕСЛИ нашлось\((22)\)

ТО заменить\((22, 7)\)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось\((44)\)

ТО заменить\((44, 4)\)

ИНАЧЕ ЕСЛИ нашлось\((77)\)

ТО заменить\((77, 7)\)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Сколько цифр 7 получится в строке, полученной в результате применения приведённой выше программы к строке: \(\underbrace{55\dots55}_{60}\underbrace{44\dots44}_{30}\underbrace{22\dots22}_{90} \underbrace{77\dots77}_{120}?\)

Показать решение

Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: \(A_{(B)},\) где A - цифра, которая находится в строке, а B - количество этих цифр.

Изначально была строка \(5_{(60)} 4_{(30)} 2_{(90)} 7_{(120)}.\)

Условно первый блок программы – это исчезновение пятерок с четверками и появление на их месте 30 двоек. Это происходит за счет замены 2 пятерок на одну двойку, т.е. произойдет 30 замен, а также 30 раз 2 четверки заменятся на 1 (29 раз сотрется четверка). Стоит заметить, что последняя четверка не сотрется, вместо нее сотрется первая попавшаяся в строке семерка. В итоге получится следующая строка:

\(2_{(30)} 4_{(1)} 2_{(90)} 7_{(119)}\)

Далее все двойки, стоящие до четверки, заменятся на 7.

\(2_{(30)} 4_{(1)} 2_{(90)} 7_{(119)} \rightarrow 7_{(1)} 2_{(28)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(2)} 2_{(26)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(1)} 2_{(26)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(2)} 2_{(24)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(1)} 2_{(24)} 4_{(1)} 2_{(90)} 7_{(118)} \)

Можно заметить, что в определенный момент программа доходит до уменьшения количества двоек перед четверкой без добавления новых семерок в начале строки или удаления семерок из группы, находящейся в конце. Это будет происходить до полного удаления группы двоек перед четверкой. В результате получим следующую строку:

\(7_{(1)} 4_{(1)} 2_{(90)} 7_{(118)}\)

Похожие действия произойдут с группой двоек после четверки:

\(7_{(1)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(1)} 4_{(1)} 7_{(1)} 2_{(88)} 7_{(117)} \rightarrow 7_{(1)} 4_{(1)} 7_{(2)} 2_{(86)} 7_{(117)} \rightarrow 7_{(1)} 4_{(1)} 7_{(1)} 2_{(86)} 7_{(117)}\)

Как видно, после достижения отметки 28 в количестве двоек программа начинает их уменьшать, не затрагивая семерки. Таким образом после выполнения программы останется следующая строка:

\(7_{(1)} 4_{(1)} 7_{(1)} 7_{(117)}\)

Количество оставшихся семерок равно 119.

Ответ: 119
Задание 58 #15095

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

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

2. нашлось (v)

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

Дана программа для исполнителя Панцирь:

НАЧАЛО

ПОКА нашлось\((54)\) ИЛИ нашлось\((27)\)

ЕСЛИ нашлось\((55)\)

ТО заменить\((55, 2)\)

ИНАЧЕ ЕСЛИ нашлось\((22)\)

ТО заменить\((22, 7)\)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось\((44)\)

ТО заменить\((44, 4)\)

ИНАЧЕ ЕСЛИ нашлось\((77)\)

ТО заменить\((77, 7)\)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Найдите сумму цифр в строке, полученной в результате применения приведённой выше программы к строке: \(\underbrace{55\dots55}_{60}\underbrace{44\dots44}_{30}\underbrace{22\dots22}_{90} \underbrace{77\dots77}_{120}?\)

Показать решение

Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: \(A_{(B)},\) где A - цифра, которая находится в строке, а B - количество этих цифр.

Изначально была строка \(5_{(60)} 4_{(30)} 2_{(90)} 7_{(120)}.\)

Условно первый блок программы – это исчезновение пятерок с четверками и появление на их месте 30 двоек. Это происходит за счет замены 2 пятерок на одну двойку, т.е. произойдет 30 замен, а также 30 раз 2 четверки заменятся на 1 (29 раз сотрется четверка). Стоит заметить, что последняя четверка не сотрется, вместо нее сотрется первая попавшаяся в строке семерка. В итоге получится следующая строка:

\(2_{(30)} 4_{(1)} 2_{(90)} 7_{(119)}\)

Далее все двойки, стоящие до четверки, заменятся на 7.

\(2_{(30)} 4_{(1)} 2_{(90)} 7_{(119)} \rightarrow 7_{(1)} 2_{(28)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(2)} 2_{(26)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(1)} 2_{(26)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(2)} 2_{(24)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(1)} 2_{(24)} 4_{(1)} 2_{(90)} 7_{(118)} \)

Можно заметить, что в определенный момент программа доходит до уменьшения количества двоек перед четверкой без добавления новых семерок в начале строки или удаления семерок из группы, находящейся в конце. Это будет происходить до полного удаления группы двоек перед четверкой. В результате получим следующую строку:

\(7_{(1)} 4_{(1)} 2_{(90)} 7_{(118)}\)

Похожие действия произойдут с группой двоек после четверки:

\(7_{(1)} 4_{(1)} 2_{(90)} 7_{(118)} \rightarrow 7_{(1)} 4_{(1)} 7_{(1)} 2_{(88)} 7_{(117)} \rightarrow 7_{(1)} 4_{(1)} 7_{(2)} 2_{(86)} 7_{(117)} \rightarrow 7_{(1)} 4_{(1)} 7_{(1)} 2_{(86)} 7_{(117)}\)

Как видно, после достижения отметки 28 в количестве двоек программа начинает их уменьшать, не затрагивая семерки. Таким образом после выполнения программы останется следующая строка:

\(7_{(1)} 4_{(1)} 7_{(1)} 7_{(117)}\)

Сумма цифр равна \(7 \cdot 119 + 4 = 837.\)

Ответ: 837
Задание 59 #15096

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

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

2. нашлось (v)

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

Дана программа для исполнителя Панцирь:

НАЧАЛО

ПОКА нашлось\((45)\) ИЛИ нашлось\((72)\)

ЕСЛИ нашлось\((44)\)

ТО заменить\((44, 2)\)

ИНАЧЕ ЕСЛИ нашлось\((77)\)

ТО заменить\((77, 2)\)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось\((55)\)

ТО заменить\((55, 5)\)

ИНАЧЕ ЕСЛИ нашлось\((22)\)

ТО заменить\((22, 2)\)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Сколько цифр 2 получится в строке, полученной в результате применения приведённой выше программы к строке: \(\underbrace{77\dots77}_{40}\underbrace{22\dots22}_{20}\underbrace{44\dots44}_{80} \underbrace{55\dots55}_{40}?\)

Показать решение

Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: \(A_{(B)},\) где A - цифра, которая находится в строке, а B - количество этих цифр.

Изначально была строка \(7_{(40)} 2_{(20)} 4_{(80)} 5_{(40)}.\) Пока все четверки не заменятся количество двоек в два раза меньшее, чем изначальное количество четверок, они не перестанут исчезать. Вместе с ними исчезают и пятерки, не заменяясь ни на что. Стоит заметить, что на последней итерации вместо исчезновения последней пятерки произойдет исчезновение первой встреченной в строке двойки. В результате мы получим следующую строку:

\(7_{(40)} 2_{(19)} 2_{(40)} 5_{(1)}\)

Далее действия, которые происходили с четверками, произойдут и с семерками. В результате за следующие 40 итераций получится следующая строка:

\(2_{(1)} 7_{(38)} 2_{(18)} 2_{(40)} 5_{(1)} \rightarrow 2_{(2)} 7_{(36)} 2_{(18)} 2_{(40)} 5_{(1)} \rightarrow 2_{(1)} 7_{(36)} 2_{(18)} 2_{(40)} 5_{(1)} \rightarrow 2_{(2)} 7_{(34)} 2_{(18)} 2_{(40)} 5_{(1)} \rightarrow 2_{(1)} 7_{(34)} 2_{(18)} 2_{(40)} 5_{(1)}\)

Как можно заметить, в какой-то момент начала уменьшать количество семерок, не затрагивая количество двоек. Так будет происходить до момента исчезновения всех семерок. Остановимся на последних итерациях:

\(2_{(1)} 7_{(2)} 2_{(18)} 2_{(40)} 5_{(1)} \rightarrow 2_{(2)} 2_{(18)} 2_{(40)} 5_{(1)} \rightarrow 2_{(1)} 2_{(18)} 2_{(40)} 5_{(1)}\)

На этом программа остановится. Таким образом, количество оставшихся двоек равно 59.

Ответ: 59
1

...

8

9

Рулетка
Вы можете получить скидку в рулетке!