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

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

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

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

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

Решаем задачи
Задание 15 #15075

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

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

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

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

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

НАЧАЛО

ПОКА нашлось\((7)\) ИЛИ нашлось\((33)\) ИЛИ нашлось\((888)\)

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

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

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

ТО заменить\((33, 3)\)

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке \(\underbrace{77\dots77}_{16}\underbrace{33\dots33}_{1600}\underbrace{88\dots88}_{8}?\)

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

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

Изначально была строка \(7_{(16)} 3_{(1600)} 8_{(8)}.\) Самое приоритетное действие в цикле ПОКА – это замена 7 на 33. На протяжении всей работы программы оно будет выполняться до тех пор, пока семерок не останется вообще. Для текущей же строки все семерки заменятся парами троек, которых будет в 2 раза больше, чем изначальное количество семерок, т.е. 32.

\(7_{(16)} 3_{(1600)} 8_{(8)} \rightarrow 3_{(1632)} 8_{(8)}\)

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

\(3_{(1632)} 8_{(8)} \rightarrow 3_{(1)} 8_{(8)}\)

Прогоним вручную по шагам программы полученную строку.

\(3_{(1)} 8_{(8)} \rightarrow 3_{(1)} 7_{(1)} 8_{(5)} \rightarrow 3_{(3)} 8_{(5)} \rightarrow 3_{(2)} 8_{(5)} \rightarrow 3_{(1)} 8_{(5)}\)

\(3_{(1)} 8_{(5)} \rightarrow 3_{(1)} 7_{(1)} 8_{(2)} \rightarrow 3_{(3)} 8_{(2)} \rightarrow 3_{(2)} 8_{(2)} \rightarrow 3_{(1)} 8_{(2)}\)

Таким образом, в конце выполнения программы будет выведено 388.

Ответ: 388
Задание 16 #15074

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

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

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

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

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

НАЧАЛО

ПОКА нашлось\((5)\) ИЛИ нашлось\((77)\) ИЛИ нашлось\((222)\)

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

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

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Найдите число, которое будет получено в результате перемножения всех цифр строки, напечатанной после применения приведённой выше программы к строке \(\underbrace{55\dots55}_{37}\underbrace{77\dots77}_{56}\underbrace{22\dots22}_{5}.\)

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

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

Изначально была строка \(5_{(37)} 7_{(56)} 2_{(5)}.\) Самое приоритетное действие в цикле ПОКА – это замена 5 на 77. На протяжении всей работы программы оно будет выполняться до тех пор, пока пятерок не останется вообще. Для текущей же строки все пятерки заменятся парами семерок, которых будет в 2 раза больше, чем изначальное количество пятерок, т.е. 74.

\(5_{(37)} 7_{(56)} 2_{(5)} \rightarrow 7_{(130)} 2_{(5)}\)

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

\(7_{(130)} 2_{(5)} \rightarrow 7_{(1)} 2_{(5)}\)

Теперь можно просчитать вручную, т.к. программа близка к завершению:

\(7_{(1)} 2_{(5)} \rightarrow 7_{(1)} 5_{(1)} 2_{(2)} \rightarrow 7_{(3)} 2_{(2)}\rightarrow 7_{(2)} 2_{(2)} \rightarrow 7_{(1)} 2_{(2)}\)

Перемножим эти цифры: \(7 \cdot 2 \cdot 2 = 28\)

Ответ: 28
Задание 17 #15073

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

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

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

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

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

НАЧАЛО

ПОКА нашлось\((5)\) ИЛИ нашлось\((77)\) ИЛИ нашлось\((222)\)

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

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

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке \(\underbrace{55\dots55}_{37}\underbrace{77\dots77}_{56}\underbrace{22\dots22}_{5}?\)

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

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

Изначально была строка \(5_{(37)} 7_{(56)} 2_{(5)}.\) Самое приоритетное действие в цикле ПОКА – это замена 5 на 77. На протяжении всей работы программы оно будет выполняться до тех пор, пока пятерок не останется вообще. Для текущей же строки все пятерки заменятся парами семерок, которых будет в 2 раза больше, чем изначальное количество пятерок, т.е. 74.

\(5_{(37)} 7_{(56)} 2_{(5)} \rightarrow 7_{(130)} 2_{(5)}\)

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

\(7_{(130)} 2_{(5)} \rightarrow 7_{(1)} 2_{(5)}\)

Теперь можно просчитать вручную, т.к. программа близка к завершению:

\(7_{(1)} 2_{(5)} \rightarrow 7_{(1)} 5_{(1)} 2_{(2)} \rightarrow 7_{(3)} 2_{(2)}\rightarrow 7_{(2)} 2_{(2)} \rightarrow 7_{(1)} 2_{(2)}\)

Таким образом, в конце выполнения программа будет выведено 722.

Ответ: 722
Задание 18 #15072

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

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

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

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

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

НАЧАЛО

ПОКА нашлось\((5)\) ИЛИ нашлось\((77)\) ИЛИ нашлось\((222)\)

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

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

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

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

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

Изначально была строка \(5_{(10)} 7_{(30)} 2_{(30)}.\) Самое приоритетное действие в цикле ПОКА – это замена 5 на 77. На протяжении всей работы программы оно будет выполняться до тех пор, пока пятерок не останется вообще. Для текущей же строки все пятерки заменятся парами семерок, которых будет в 2 раза больше, чем изначальное количество пятерок, т.е. 20.

\(5_{(10)} 7_{(30)} 2_{(50)} \rightarrow 7_{(50)} 2_{(50)}\)

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

\(7_{(50)} 2_{(50)} \rightarrow 7_{(1)} 2_{(50)}\)

Далее, необходимо прогонять получаемые строки по алгоритму до тех пор, пока мы не получим конструкцию из одной семерки и какого-то количества двоек, большего или равного 3. Если мы получим идентичную конструкцию, но с другим количеством цифр, то это значит, что выполнение определенного набора действий будет зациклено до тех пор, пока условие наличия одной пятерки, двух семерок или трех двоек не будет нарушено.

\(7_{(1)} 2_{(50)} \rightarrow 7_{(1)} 5_{(1)} 2_{(47)} \rightarrow 7_{(3)} 2_{(47)} \rightarrow 7_{(2)} 2_{(47)} \rightarrow 7_{(1)} 2_{(47)}\)

Итак, из \(7_{(1)} 2_{(50)}\) мы получили \(7_{(1)} 2_{(47)},\) значит выполнять те же действия большое количество раз не нужно, мы можем сразу снижать количество двоек.

За один шаг количество уменьшилось на 3, значит нужно вычесть из 50 ближайшее к этому числу значение, кратное 3, т.е. 45.

\(7_{(1)} 2_{(50)} \rightarrow 7_{(1)} 2_{(5)}\)

Теперь снова вручную прогоним полученную строку.

\(7_{(1)} 2_{(5)} \rightarrow 7_{(1)} 5_{(1)} 2_{(2)} \rightarrow 7_{(3)} 2_{(2)} \rightarrow 7_{(2)} 2_{(2)} \rightarrow 7_{(1)} 2_{(2)}\)

Сумма цифр равна \(7 + 2 + 2 = 11\)

Ответ: 11
Задание 19 #15071

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

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

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

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

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

НАЧАЛО

ПОКА нашлось\((5)\) ИЛИ нашлось\((77)\) ИЛИ нашлось\((222)\)

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

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

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

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

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке \(\underbrace{55\dots55}_{10}\underbrace{77\dots77}_{30}\underbrace{22\dots22}_{50}?\)

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

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

Изначально была строка \(5_{(10)} 7_{(30)} 2_{(30)}.\) Самое приоритетное действие в цикле ПОКА – это замена 5 на 77. На протяжении всей работы программы оно будет выполняться до тех пор, пока пятерок не останется вообще. Для текущей же строки все пятерки заменятся парами семерок, которых будет в 2 раза больше, чем изначальное количество пятерок, т.е. 20.

\(5_{(10)} 7_{(30)} 2_{(50)} \rightarrow 7_{(50)} 2_{(50)}\)

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

\(7_{(50)} 2_{(50)} \rightarrow 7_{(1)} 2_{(50)}\)

Далее, необходимо прогонять получаемые строки по алгоритму до тех пор, пока мы не получим конструкцию из одной семерки и какого-то количества двоек, большего или равного 3. Если мы получим идентичную конструкцию, но с другим количеством цифр, то это значит, что выполнение определенного набора действий будет зациклено до тех пор, пока условие наличия одной пятерки, двух семерок или трех двоек не будет нарушено.

\(7_{(1)} 2_{(50)} \rightarrow 7_{(1)} 5_{(1)} 2_{(47)} \rightarrow 7_{(3)} 2_{(47)} \rightarrow 7_{(2)} 2_{(47)} \rightarrow 7_{(1)} 2_{(47)}\)

Итак, из \(7_{(1)} 2_{(50)}\) мы получили \(7_{(1)} 2_{(47)},\) значит выполнять те же действия большое количество раз не нужно, мы можем сразу снижать количество двоек.

За один шаг количество уменьшилось на 3, значит нужно вычесть из 50 ближайшее к этому числу значение, кратное 3, т.е. 45.

\(7_{(1)} 2_{(50)} \rightarrow 7_{(1)} 2_{(5)}\)

Теперь снова вручную прогоним полученную строку.

\(7_{(1)} 2_{(5)} \rightarrow 7_{(1)} 5_{(1)} 2_{(2)} \rightarrow 7_{(3)} 2_{(2)} \rightarrow 7_{(2)} 2_{(2)} \rightarrow 7_{(1)} 2_{(2)}\)

Таким образом, в конце выполнения программа будет выведено 722.

Ответ: 722
Задание 20 #12786

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

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

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

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

Цикл

ПОКА условие

\(\qquad\)Последовательность команд

КОНЕЦ ПОКА

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

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

ЕСЛИ условие

команда1

КОНЕЦ ЕСЛИ

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

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

ЕСЛИ условие

команда1

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

КОНЕЦ ЕСЛИ

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 141 идущей подряд цифры 4?

НАЧАЛО

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

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

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

ИНАЧЕ

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

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

КОНЕЦ ПОКА

КОНЕЦ

В ответе запишите полученную строку.

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

Если в строке достаточно число двоек или четверок, то после того как тело цикла будет выполнено четыре раза, первые шестнадцать четверок заменятся на четыре двойки. При следующем выполнении цикла после первой команды эти четыре двойки заменятся на одну четверку, после чего процесс будет продолжаться: шестнадцать четверок заменятся на четыре двойки, а четыре двойки – на одну четверку. Становится ясно, что цикл преобразует шестнадцать четверок в одну четверку. После того как цикл повторяется 8 раз, у нас станет \(128/16=8\) четверок и оставшиеся \(141-128=13\) четверок, в общей сумме \(13+8=21\) четверка. Шестнадцать из них заменятся на четыре двойки, затем эти четыре двойки заменятся на одну четверку получится строка \(444444\), затем четыре четверки заменятся на двойку, получится строка 244 Так как в этой строке нет трех четверок и нет трех двоек условие цикла не выполнится, а выполнение программы на этом завершится.

Ответ: 244
Задание 21 #12785

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

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

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

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

Цикл

ПОКА условие

\(\qquad\)Последовательность команд

КОНЕЦ ПОКА

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

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

ЕСЛИ условие

команда1

КОНЕЦ ЕСЛИ

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

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

ЕСЛИ условие

команда1

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

КОНЕЦ ЕСЛИ

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 150 идущих подряд цифр 4?

НАЧАЛО

Пока нашлось \((44444)\)

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

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

ИНАЧЕ

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

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

КОНЕЦ ПОКА

КОНЕЦ

В ответе запишите полученную строку.

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

Если в строке достаточно число четверок, то после того как тело цикла будет выполнено восемь раз, первые 32 четверки заменятся на шестнадцать двоек. При следующем выполнении цикла после первой команды эти шестнадцать двоек заменятся на четыре двойки, а четыре двойки заменятся на одну двойку после чего процесс будет продолжаться: 32 четверки заменятся на шестнадцать двоек, шестнадцать двоек на четыре двойки, затем четыре двойки заменятся на одну двойку. Становится ясно, что цикл преобразует тридцать две четверки в одну двойку. После того как цикл повторяется 4 раза, у нас станет \(128/32=4\) двойки, которые заменятся на одну двойку \(4/4=1\) и оставшиеся \(150-128=22\) четверки, затем шестнадцать четверок заменятся на восемь двоек, станет \(8+1=9\) двоек и \(22-16=6\) четверок, затем 8 двоек, преобразуются в две двойки, получится строка 222444444, после этого четыре четверки преобразуются в две двойки и получится строка 2222244. Так как в этой строке нет пяти четверок, условие цикла не выполнится, а выполнение программы на этом завершится.

Ответ: 2222244
12

3

4

...

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