https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=419194&view=findpost&p=3834720 Mon, 20 Jul 2020 08:40:19 +0000 https://forum.sources.ru/index.php?showtopic=419194&view=findpost&p=3834720 Алгоритмы для формальных исполнителей, команды замены цепочек символов
Часть 1, № 14
Задание взято с сайта
http://kotolis.ru/realegeinf_2020

Условие.
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
заменить (v, w)
нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (49) ИЛИ нашлось (97) ИЛИ нашлось (47)
ЕСЛИ нашлось (47)
ТО заменить (47, 74)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (97)
ТО заменить (97, 79)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (49)
ТО заменить (49, 94)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой ниже программе поступает строка, содержащая 40 цифр 7,40 цифр 9 и 50 цифр 4, расположенных в произвольном порядке. Запишите без разделителей символы, которые имеют порядковые номера 25, 71 и 105 в получившейся строке.

Задачу нужно было формулировать так:
... поступает строка, содержащая блок из 40 цифр 7, блок из 40 цифр 9 и блок из 50 цифр 4, блоки расположены в произвольном порядке.

Решение.
Утверждение.
Пусть у нас имеется команда переписывания ba -> ab и два блока b...b и a...a, блоки имеют произвольную длину.
В результате многократного применения этой команды к блокам b...ba...a блоки поменяются местами:
b...ba...a -> a...ab...b.
Это утверждение легко доказать индукцией по длине одного из блоков.

Теперь найдём такое расположение блоков, при котором ни одна команда переписывания не выполняется.
Зафиксируем один блок, например, блок 7. Блок 4 можно поставить только после этого блока: 74.
Блок 9 нельзя поставить перед 7 и нельзя поставить после 4.
Значит блок 9 единственным образом ставится после 7 и перед 4: 794.
Номер 25 имеет 7, номер 71 имеет 9 и номер 105 имеет 4.

Ответ: 794 .]]> swf ПОМОЩЬ ШКОЛЬНИКАМ