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

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

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

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

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

Решаем задачи
Задание 29 #15455

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

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

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

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

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

НАЧАЛО

ПОКА нашлось(*7) или нашлось(*8)

ЕСЛИ нашлось(*78)

ТО заменить(*78, 4*)

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

ТО заменить(*7, 0*)

КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось(*8)

ТО заменить(*8, 8*)

КОНЕЦ ПОКА

КОНЕЦ

На вход приведённой программе поступает строка, начинающаяся с символа <<*>>, после него в строке находится 7 восьмерок и неизвестное количество семерок. Расположение цифр может быть любым. Определите наименьшее количество семерок, которые могли содержаться в изначальной строке, если сумма цифр строки, полученной в результате выполнения программы равна 40.

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

Программа заменяет семерки, за которыми находится восьмерка на четверки. Если же за семеркой находится другая семерка, то левая семерка заменяется нулем. Свободные восьмерки не затрагиваются действиями программы.

Чтобы минимизировать количество семерок определим следующее: в числе 40 содержится 5 восьмерок, однако программа не позволяет взять 5 восьмерок и не использовать остальные.

Очевидно, что восьмерки, перед которыми находится семерка, уменьшаются программой в два раза, значит можно подбором найти такое количество \(k\) и \(n,\) при котором \(8 \cdot k + 4 \cdot n = 40.\) Эти \(k\) и \(n\) равны 3 и 4 соответственно. Следовательно, чтобы получить число 40, нужно задействовать 4 семерки и поставить их перед восьмерками.

Ответ: 4
Задание 30 #15456

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

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

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

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

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

НАЧАЛО

ПОКА нашлось(*7) или нашлось(*8)

ЕСЛИ нашлось(*78)

ТО заменить(*78, 4*)

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

ТО заменить(*7, 0*)

КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось(*8)

ТО заменить(*8, 8*)

КОНЕЦ ПОКА

КОНЕЦ

На вход приведённой программе поступает строка, начинающаяся с символа <<*>>, после него в строке находится 4 восьмерок и неизвестное количество семерок. Расположение цифр может быть любым. Определите наименьшее количество семерок, которые могли содержаться в изначальной строке, если сумма цифр строки, полученной в результате выполнения программы равна 24.

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

Программа заменяет семерки, за которыми находится восьмерка, на четверки. Если же за семеркой находится другая семерка, то левая семерка заменяется нулем. Свободные восьмерки не затрагиваются действиями программы.

Чтобы минимизировать количество семерок, определим следующее: в числе 24 содержится 3 восьмерки, однако программа не позволяет взять 3 восьмерки и не использовать остальные.

Очевидно, что восьмерки, перед которыми находится семерка, уменьшаются программой в два раза, значит можно подбором найти такое количество \(k\) и \(n,\) при котором \(8 \cdot k + 4 \cdot n = 24.\) Эти \(k\) и \(n\) равны 2 и 2 соответственно. Следовательно, чтобы получить число 24, нужно задействовать 2 семерки и поставить их перед восьмерками.

Ответ: 2
Задание 31 #15082

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

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

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

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

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

НАЧАЛО

ПОКА нашлось\((4)\) ИЛИ нашлось\((66)\) ИЛИ нашлось\((000)\)

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

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

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

ТО заменить\((66, 6)\)

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

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

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какое число получится в результате применения приведенной выше программы к строке \(\underbrace{44\dots44}_{763}\underbrace{66\dots66}_{153}\underbrace{00\dots00}_{690}?\) Ответ дайте в двоичной системе счисления.

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

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

Изначально была строка \(4_{(763)} 6_{(153)} 0_{(690)}.\) Самое приоритетное действие в цикле ПОКА – это замена 4 на 66. На протяжении всей работы программы оно будет выполняться до тех пор, пока четверок не останется вообще. Для текущей же строки все четверки заменятся парами шестерок, которых будет в 2 раза больше, чем изначальное количество четверок, т.е. 1526.

\(4_{(763)} 6_{(153)} 0_{(690)} \rightarrow 6_{(1679)} 0_{(690)}\)

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

\(6_{(1679)} 0_{(690)} \rightarrow 6_{(1)} 0_{(690)}\)

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

\(6_{(1)} 0_{(690)} \rightarrow 6_{(1)} 4_{(1)} 0_{(687)} \rightarrow 6_{(3)} 0_{(687)} \rightarrow 6_{(2)} 0_{(687)} \rightarrow 6_{(1)} 0_{(687)}\)

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

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

\(6_{(1)} 0_{(690)} \rightarrow 6_{(1)} 0_{(3)}\)

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

\(6_{(1)} 0_{(3)} \rightarrow 6_{(1)} 4_{(1)} \rightarrow 6_{(3)} \rightarrow 6_{(2)} \rightarrow 6_{(1)} \)

Переведем 6 в двоичную систему счисления: \(6_{10} = 110_{2}\)

Ответ: 110
Задание 32 #12784

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

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

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

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

Цикл

ПОКА условие

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

КОНЕЦ ПОКА

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

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

ЕСЛИ условие

команда1

КОНЕЦ ЕСЛИ

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

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

ЕСЛИ условие

команда1

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

КОНЕЦ ЕСЛИ

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

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

НАЧАЛО

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

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

ТО заменить \((333, 9)\)

ИНАЧЕ

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

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

КОНЕЦ ПОКА

КОНЕЦ

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

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

Если в строке достаточно число девяток, то после того как тело цикла будет выполнено три раза, первые девять девяток заменятся на три тройки. При следующем выполнении цикла после первой команды эти три тройки заменятся на одну девятку, после чего процесс будет продолжаться: девять девяток заменятся на три тройки, а три тройки – на одну девятку. Становится ясно, что цикл преобразует девять девяток в одну девятку. После того как цикл повторяется 9 раз, у нас станет \(81/9=9\) девяток, которые затем преобразуются в 9/9=1 девятку и оставшиеся \(92-81=11\) девяток, в общей сумме \(11+1=12\) девяток. Две девятки заменятся на две тройки, получится строка \(33999999\) останется еще шесть девяток, затем три девятки заменятся на одну тройку, получится строка \(333999\). Так как в этой строке нет шести девяток, условие цикла не выполнится, а выполнение программы на этом завершится.

Ответ: 333999
Задание 33 #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
Задание 34 #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
Задание 35 #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
1

...

4

5

6

...

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