Тип задач #12: Алгоритмы для Исполнителя

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

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

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

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (42) ИЛИ нашлось (822) ИЛИ нашлось (222)
  ЕСЛИ нашлось (42)
    ТО заменить (42, 2)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (822)
    ТО заменить (822, 24)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (222)
    ТО заменить (222, 8)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «4», а затем содержащая n цифр «2» (3 < n < 10 000). Определите наибольшее возможное значение суммы цифр в строке, которая может быть получена в результате выполнения программы.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя А(a0, a1, …), включая специальный пустой символ.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q (q0, q1, …). В начальный момент времени головка находится в начальном состоянии q0.
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.

      a0      a1    ...
q0  команда команда ...
q1  команда команда ...
...  ...    ...     ...

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды. Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.

Выполните задание.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя:

        λ       1       0
q0    λ,L,q1    -       -
q1    λ,S,q1  0,S,q1  1,L,q1

После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А - заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б - нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (15) ИЛИ нашлось (599) ИЛИ нашлось (999)
  ЕСЛИ нашлось (15)
    ТО заменить (15, 9)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (599)
    ТО заменить (599, 5)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (999)
    ТО заменить (999, 19)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая n цифр «9» (3 < n < 10 000).

Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 30.

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

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

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

Дана программа для Редактора:

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

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая n цифр «2» (3 < n < 4 000).

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

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

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

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

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (78) ИЛИ нашлось (688) ИЛИ нашлось (8888)
  ЕСЛИ нашлось (78)
    ТО заменить (78, 8)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (688)
    ТО заменить (688, 87)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (8888)
    ТО заменить (8888, 6)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «7», а затем содержащая n цифр «8» (3 < n < 10 000).

Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 61.

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А- заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б- нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (19) ИЛИ нашлось (399) ИЛИ нашлось (999)
  ЕСЛИ нашлось (19)
    ТО заменить (19, 9)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (399)
    ТО заменить (399, 91)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (999)
    ТО заменить (999, 3)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая n цифр «9» (3 < n < 10 000).
Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 33.

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

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

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

Дана программа для Редактора:

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

На вход приведённой выше программе поступает строка, начинающаяся с цифры «3», а затем содержащая n цифр «1» (3 < n < 10 000).

Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 15.