Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек). Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Опишите это слово, используя формулу, которая называется регулярным выражением. Такое выражение строится с помощью описываемых ниже операций "итерация", "умножение", "сложение".
Так для повторения блока из нескольких букв используйте операцию «звездочка» (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, …}. Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой приписыванием второго операнда вслед за первым, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т.д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac,..., aaa...acb...b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.
Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так, обозначение (a+b)*c+d(ac*+) описывает множество всех последовательностей из букв a и b (обозначается (a+b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово — это d)."
Слева приведены примеры слов, которые удовлетворяют нашему условию, справа примеры слов, которые не удовлетворяют ему. Благодаря подсветке вы можете видеть, какие из этих примеров и контрпримеров удовлетворяют построенному вами выражению, а какие — нет.
В качестве начального решения вы можете видеть выражение, которому удовлетворяет слово Р и пустое слово.
Первое слагаемое- все такие слова, которые начинаются на Р и заканчиваются на Р, так как сначала идет Р, затем снова Р идти не может, трех Л подряд также быть не может, значит далее Л или ЛЛ, а затем снова Р и т.д. Второе слагаемое- все такие слова, которые начинаются на Л и заканчиваются на Р, т.к. сначала идет Л, затем обязательно Р, затем Р идти не может и ЛЛЛ идти не может, значит Л или ЛЛ и т.д. В конце должно быть Р. Третье слагаемое- все такие слова, которые начинаются на Р и заканчиваются на Л, т.к. предпоследняя буква Л не может быть, значит мы просто убираем последнюю Л и получаем первый случай. Последнее слагаемое- все такие слова, которые начинаются на Л и заканчиваются на Л, т.к. вторая буква обязательно Р, далее снова Р не может идти, ЛЛЛ также не может идти, значит Л или ЛЛ, далее мы повторяем рассуждения, но в конце, чтобы не было две Л, мы добавляем РЛ,