Потенциал Образовательный журнал
для старшеклассников и учителей

<< К разделам
Информатика
Алгоритмы
Теория информации
Теория программирования
Все статьи
Журнал
Подписка
Интернет-Журнал «Потенциал» External link mark
Авторам
Печатные номера
Полезные сайты
ЗФТШ External link mark
МЦНМО External link mark
Журнал "Квант" External link mark
"Открытый Колледж" External link mark
Союз образовательных сайтов External link mark
Интернет-портал "Абитуриент" External link mark
Другие ссылки...

WOlist.ru - каталог качественных сайтов Рунета Союз образовательных сайтов Rambler's Top100 Портал ВСЕОБУЧ. Все образование Москвы и регионов РФ.

Главная Подписка Архив Авторы Фотоальбом Подготовка в вуз Магазин

Инварианты в задачах по математике и программированию

Королев Д.Н.


Инвариант — это величина, которая остаётся неизменной при тех или иных преобразованиях. В некоторых задачах инвариант — это величина, которая изменяется монотонно, то есть только увеличивается или только уменьшается.

Инварианты в математике

Наш рассказ об инвариантах проще начать с задач по математике.

Инвариант — это величина, которая остаётся неизменной при тех или иных преобразованиях. В некоторых задачах инвариант — это величина, которая изменяется монотонно, то есть только увеличивается или только уменьшается.

Простая задача

Имеется шахматная доска, из которой вырезали два противоположных угловых поля. Можно ли покрыть ее целиком фигурами домино (размером 2 × 1 поля шахматной доски) таким образом, чтобы каждое поле было полностью покрыто одной и только одной фигурой домино?

Часто фразу "можно ли" следует читать как "докажите, что это невозможно". В любом случае, в "можно ли"-задачах имеет смысл попытаться доказать невозможность существования решения — это может помочь найти его, если решение всё-таки существует.

В задачах, где необходимо доказать невозможность достичь чего-либо в результате некоторого процесса (в данном случае — последовательного выкладывания фигур домино), инварианты являются мощным инструментов в руках умелого математика.

Наиболее часто к задаче "о доминошках" приводится такое решение. Шахматная доска состоит из темных и светлых полей. Одна положенная на доску фигура домино покрывает одно тёмное и одно светлое поле. Следовательно, необходимым (но далеко не достаточным) условием возможности замощения некоторой клетчатой фигуры при помощи фигур домино является равное количество темных и светлых полей на исходной доске. Шахматная доска с вырезанными противоположными угловыми полями не удовлетворяет этому условию, так как оба вырезанных поля — одного цвета. Мы пришли к противоречию, таким образом, задача решена.

Безусловно, предыдущий абзац является исчерпывающим решением задачи. И в нём ни разу не встречается слово "инвариант". Тем не менее, инвариант в этом решении присутствует. Переформулируем решение, чтобы его разглядеть.

Что есть "замощение фигурами домино"? Это процесс выкладывания доминошек по одной "до победного", либо не до победного конца. Следуя определению инварианта, назовем выкладывание одной фигуры домино (одну итерацию процесса выкладывания) преобразованием.

Назовём состоянием S некоторый промежуточный результат в замощении доски фигурами домино. Иными словами, состояние — это доска, на которую некоторым образом положены первые N фигур домино после первых N итераций. Число N может быть нулём — пустая доска также является состоянием, которое называется начальным состоянием.

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

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

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

Инвариантом может быть, например, функция I(S) = B-W, где B — число свободных от фигур домино тёмных полей доски, W — светлых. Ясно, что при добавлении новой фигуры домино, как B, так и W уменьшаются на единицу (фигура домино всегда покрывает одно темное и одно светлое поле), следовательно, B-W остаётся константой. В начальном состоянии I(S0) равно двум (или минус двум), в конечном должно быть равно нулю — противоречие, невозможность требуемого замощения доказана.

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

Если найден инвариант, который даёт раличные значения для различных начальных и конечных состояний, такой инвариант тоже полезен — можно отсечь часть потенциальных решений, которые невозможны, и/или часть начальных состояний, из которых решение заведомо недостижимо.

"Хитрое жюри" и операция сложения по модулю два

Рассмотрим теперь несложную задачу по программированию. Она не имеет прямого отношения к инвариантам, однако, с её помощью мы покажем интересные способы выбора функций, которые могут быть инвариантами. Задача известна участникам олимпиад по информатике под названием "Хитрое жюри". Оригинал задачи — Всероссийские учебно-тренировочные сборы по программированию.

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

Задача 1. Хитрое жюри

На вход подается нечётное число N натуральных чисел Ai (N = 1, 2, ..., 108+1). Все эти числа лежат меньше 1018. Известно, что среди этих чисел все встречаются четное число раз, кроме одного, которое встречается только один раз. Найдите это число.

Например, для входных данных 1, 2, 3, 4, 3, 2, 1 ответом будет число 4 (числа 1, 2 и 3 встречаются в этом наборе дважды). Для входа 5, 21, 71, 34, 67, 34, 5, 67, 71 — число 21.

Решение следует найти за одно прочтение входных данных, не запоминая чисел.

Задача «Хитрое жюри» удивительна тем, что при существовании очень простого решения, его непросто найти, не имея соответствующей подготовки. Подойдём к решению издалека. Каждое из чисел содержит максимум 18 цифр. Попробуем подсчитать количество появлений каждой цифры на каждом месте. Для второго примера: в разряде единиц встречаются 5, 1, 1, 4, 7, 4, 5, 7, 1, то есть два раза встречается пятерка, три раза единица, два раза четверка и два раза семерка. Нечётное количество раз встречается только единица, она и будет стоять в ответе в разряде единиц. Аналогично, для разряда десятков — 0 2 7 3 6 3 0 6 7. Здесь мы дополнили числа, меньшие десяти, слева незначащим нулём. Нечётное число раз встречается только двойка.

Для всех остальных разрядов все цифры — нули. Следовательно, ответ равен 21.

Вместо того, чтобы решать задачу с восемнадцатиразрядными числами, мы решили 18 задач с одноразрядными числами. При этом, наше решение даёт ответ за одно прочтение входных данных, что в данной задаче очень важно.

Задача 2. Решите задачу «Хитрое жюри» для случая, когда числа на входе лежат в промежутке от 0 до 9.

В данном случае мы рассматривали число, записанное в десятичной системе счисления. Попробуем рассмотреть все входные числа в более «привычной» компьютеру двоичной системе счисления. В этом случае, числа будут содержать не более 63 двоичных цифр (проверьте это!).

Первый пример — 1, 2, 3, 4, 3, 2, 1 — будет выглядеть так: 0012, 0102, 0112, 1002, 0112, 0102, 0012. Вновь идем по разрядам, уже по двоичным, как и в предыдущий раз от младших к старшим. Младший разряд: 1, 0, 1, 0, 1, 0, 1 — нечётное число раз встречается ноль, следовательно, в младшем разряде искомого числа стоит 0. Рассуждая аналогично для других разрядов, получаем ответ 1002, то есть четверку. Нетрудно заметить, что при таком подходе к решению можно не запоминать для каждого разряда и количество нулей, и количество единиц. Действительно, если единиц нечётное количество, то в ответе в соответствующем разряде ответа будет единица, иначе — ноль.

Мы пришли к операции суммирования без переноса, точнее, к операции поразрядного суммирования по модулю два без учёта переноса в двоичной системе счисления.

Ноль и единицу можно также трактовать как ложь (0) или истину (1). Данная операция настолько часто встречается, что для нее существует специальное название в логике — «Исключающее Или», или XOR (eXclusive O R). Операция XOR двух булевых величин есть истина тогда и только тогда, когда ровно один из операндов является истиной.

Как и любое сложение, XOR подчиняется переместительному (a xor b  = b xor a) и распределительному (a xor(b xor c) = (a xor b) xor c) законам. Кроме того, интересны ещё некоторые свойства операции XOR:

a xor 0 = a

a xor a = 0

a xor b = 0 ⇒ a = b

Доказательство этих утверждений оставим читателю.

Теперь понятно, почему поразрядный XOR всех чисел даёт ответ на задачу.

a xor  b xor c xor d ... xor x ... xor a xor b xor c =

= (a xor a) xor (b xor b) xor ... xor x =

= 0 xor x = x

В несколько ином виде эту задачу можно найти на сайте http://acm.mipt.ru/judge, задача «27. Лишнее число». Автор рекомендует читателям написать решение этой задачи и протестировать его в системе автоматической проверки.

Игра Ним

Теперь мы можем перейти к другой задаче, имеющей непосредственное отношение к инвариантам. Речь пойдёт об игре Ним.

Игра Ним — это игра двух игроков, основанная на поочередном взятии камешков из одной или нескольких кучек. В свой ход игрок может взять любое ненулевое количество камешков из любой кучки, но только из одной. Игрок, которому не осталось камешков, проигрывает.

Задача 3. Поиграйте в игру Ним для случая

а) две кучи по два камня — {2, 2};

б) {3, 1};

в) {3, 2, 1}

г) {2, 2, 2}.

Существует множество игр, подобных игре Ним, отличающихся правилами взятия камней и условиями выигрыша. Но «исходная» игра Ним является ключевой, так как другие игры, в определённом смысле, к ней сводятся.

Выигрышную стратегию в игре Ним можно найти с помощью одного нехитрого инварианта.

Но, прежде чем к нему перейти, рассмотрим игру попроще.

Задача 4 На столе лежат сто спичек. Играют двое, ходят по очереди. За один ход игрок может взять одну, две или три спички. Забравший последнюю спичку выигрывает. Кто выиграет при правильной игре — первый или второй игрок?

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

Для доказательства этого утверждения обратимся к инвариантам. В нашем случае инвариант — это остаток при делении на 4.

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

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

Вернёмся к игре Ним. Ясно, что если кучка с камнями всего одна, то выигрывает первый игрок, забирая из неё все камни. Если кучек две и в них одинаковое число камней, то выигрывает второй, постоянно симметрично повторяя ходы первого. Если же в двух кучках различное число камней, то первый игрок выиграет, если первым ходом уровняет число камней в двух кучках. Еще можно заметить, что если число кучек чётно, и кучки разбиваются на пары одинаковых (например, {3, 3, 5, 2, 2, 5}), то снова выигрывает второй игрок. Дальнейший анализ данной задачи далеко не так прост.

Перед нами настоящая задача по информатике. На входе — некоторая игровая ситуация, или состояние: число n и набор натуральных чисел A1, A2, ..., An. Попробуйте придумать алгоритм, который отвечает на вопрос «кто выиграет при оптимальной игре для данного состояния?» Например, кто выиграет для начального состояния {1, 2, 3, 5, 10}? Если выигрывает первый игрок, укажите ход, ведущий к выигрышу. Конечно, алгоритм должен быть эффективным, а не представлять собой полный перебор всех возможных ситуаций до победного конца.

Инвариантом в данной задаче является поразрядный XOR всех Ai (как и в задаче «Хитрое жюри»). Если этот инвариант не ноль, то у первого игрка есть выигрышная стратегия. Иначе (если инвариант равен нулю) выигрышная стратегия есть у второго.

Докажем вышеприведённый инвариант. Пусть X = A1xor A2 xor ...xor An. Найдем такое i, для которого Ai > X xor Ai.

Задача 5 Докажите, что такое i всегда найдётся.

Именно из этой кучи Ai и нужно взять несколько камней, оставив там X xor Ai камней. После этого новое значение инварианта, будет X' = X xor X = 0, так как ровно один элемент в XOR-сумме A1xor A2 xor ...xor An дополнительно про-XOR-или с X, поэтому конечный результат будет равен предыдущему, про-XOR-енному с X. Таким образом, если XOR всех размеров кучек не равен нулю, то за один ход его можно обратить в ноль.

Покажем теперь, что если XOR равен нулю, то любой ход делает его не равным нулю. Действительно, когда мы берём сколько-то камней из одной кучки, то двоичная запись числа камней в этой куче меняется по крайней мере в одном разряде. Значения этого разряда в других числах остаются прежними, значит, значение XOR-суммы поменялось в этом разряде. Изначально все разряды в XOR-сумме были равны нулю. Значит, после любого хода по крайней мере один разряд будет единичным. Это также следует из того, что A xor B = A ⇔ B = 0, а по условию игрок должен взять число камней, большее нуля.

Действительно, из позиции с ненулевой XOR-суммой всегда существует ход в позицию с нулевой XOR-суммой, а из позиции с нулевой XOR-суммой второй игрок сможет сходить только в позиции с ненулевой XOR-суммой.

В конце игры, когда ни в одной кучке не осталось камней, XOR-сумма равна нулю. Поэтому выигрывает тот игрок, который может сделать ход, ведущий в позицию с XOR-суммой равной нулю. Соответственно, если вначале XOR-сумма не равна нулю, то выигрывает первый игрок, если равна — второй.

    xor00012
00112
01002
10102
------
11002

Для набора кучек с размерами {1, 3, 4, 10} инвариант I(S) равен 11002=23+22 = 8+4 =12 (см. операцию XOR столбиком справа).

По сути, здесь в каждом столбце считается чётность числа единичек. Инвариант X=I(S) = 12 не равен нулю. Найдём кучку, у которой такой же старшый разряд, как и у X. Это куча A4 = 10102 = 10. В ней нужно оставить A4' камней, где A4' = (A4 xor X) = (10 xor 12) = (10102 xor 11002) = 01102=6. Таким образом, для выигрыша из четвёртой кучи нужно взять 4 камня, и инвариант новой ситуации будет равен 0.

Задача «100. Игра Ним» есть на сайте http://acm.mipt.ru/judge, где и вы можете попытаться её сдать.

В завершение разговора о математике приведём задачу, в которой важную роль играет инвариант.

Задача 6. Даны три числа: A = 3, B = √2 и C = 1 + 2 * √2. За один ход разрешается добавить к любому из них разность двух других, умноженную на любое рациональное число. Можно ли после нескольких таких операций получить {A, B, C} = {3, 2 * √2,  1 + 3 * √2 }? (Санкт-Петербургская олимпиада по математике)

Инварианты в программировании

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

Повторяющиеся операции

Рассмотрим простейший пример — вывод массива на экран (примеры в этой статье приводятся на языке программирования С++, однако они настолько просты, что не требуют практически никаких знаний этого языка).

for(i = 0; i < N; i++)

cout << X[i] << ' ';

Данный фрагмент кода выводит нa экран элементы массива X с нулевого по (N-1)-й, разделяя их пробелами. Сформулируем таким образом: после выполнения цикла элементы массива с нулевого по N-1 оказываются выведенными на экран через пробел. Такая формулировка точнее с той точки зрения, что она явно подчеркивает повторяемую операцию, в то время как фраза «вывести массив на экран» это только подразумевает.

Итак, элементы массива должны быть выведены на экран, и для этого необходимо использовать цикл. Каким же будет инвариант этого цикла? Очень простым — после выполнения i-й итерации цикла (итерации нумеруются по переменной цикла, то есть, начиная с нулевой) элементы массива с нулевого по i-й включительно будут выведены на экран[1]. Данный пример слишком прост для того, чтобы продемонстрировать полезность инвариантов. Перейдём к следующему по сложности примеру.

Задача: найти максимальное число среди элементов [0 .. N-1] массива X, записать его в переменную M.

M = X[0];

for(i = 1; i < N; i++)

if(X[i] > M)

M = X[i];

В данном случае цикл уже содержит условный оператор. Инвариант формулируется следующим образом: после выполнения итерации цикла со значением переменной цикла i=I, M равно максимальному элементу из первых I элементов массива[2].

Наиболее частой ошибкой при написании циклов являются ошибки в граничных условиях. Автор рекомендует читателям всегда перед тем, как писать нетривиальный цикл, четко уяснить для себя, что именно происходит на очередной его итерации и как именно выглядит инвариант в виде точной формулы, а не на уровне «интуитивного понимания».

Инварианты и оптимальные решения

Виртуозное владение инвариантами особенно полезно при решении задач по информатике, основанных на методе динамического программирования. Метод динамического программирования заключается в сведении задачи к аналогичным, но более простым. При этом алгоритм заключается в хранении «архива» решений простых задач и последовательном расширении этого архива, пока в него не попадёт нужная нам задача. Алгоритмы, основанные на динамическом программировании, активно используют память.

Решения для простейших случаев тривиальны и сразу попадают в наш архив. А решения для сложных входных данных получают при помощи индукции, выполняя последовательно шаги индукции и записывая новые решения «подзадач» в память.

Рассмотрим задачу по информатике на динамическое программирование:

Задача 7. («Покупка билетов»)[3]

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

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

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

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

Идея решения — объединить некоторых ожидающих в группы по два или три человека. Вопрос — как это сделать максимально эффективно, желательно, один раз прочитав входные данные и не перебирая варианты. На помощь приходят инварианты.

Пусть Z[i] — минимальная стоимость покупки билетов для первых i человек в очереди (в порядке «от кассы»). Понятно, что Z[0] = 0, Z[N] — ответ. Давайте научимся эффективно строить массив Z по мере просмотра людей в очереди.

Человек может купить билет только себе, себе и следующему человеку, либо себе и двум следующим. Таким образом, Z[i] зависит только от Z[i-1], Z[i-2], Z[i-3]. Несложно видеть, что Z[i] = min(Z[i-1]+A[i-1],   Z[i-2]+B[i-2],   Z[i-3]+C[i-3]).

В переводе на русский язык, приведённая формула выглядит так: «Для того, чтобы оптимально купить билеты первым i людям в очереди, билет i-му человеку либо покупает он сам (при этом предыдущие (i-1) человек уже купили билеты оптимальным способом), либо билет ему берёт (i-1)-й человек (и люди с 1-го по (i-2)-го ушли с билетами довольными), либо (i-3)-й человек берёт сразу три билета».

В нашем случае, мы разделили большую задачу «найти оптимальный способ купить билеты на N человек (Z[N])» на подзадачи «построить Z[i] на основе предыдущих значений Z». Утверждение Z[0] = 0 является тривиальным решением. А написанная формула представляет собой формулу динамического программирования. Фактически она представляет собой инвариант оптимального решения задачи. Придумать эту формулу — значит, решить задачу. А для того, чтобы написать решение в виде программы, необходимо всего лишь реализовать её в виде программы, чаще всего, в виде одного или нескольких вложенных циклов. Решение сложной задачи выглядит поразительно просто:

#include
using namespace std;

int N;
int X[5001][4], Z[5001];

int main() {
    int i, j;
    cin >> N;

    // X[i][1] == A[i]
    // X[i][2] == B[i]
    // X[i][3] == C[i]

    for(i = 0; i < N; i++)
        cin >> X[i][1] >> X[i][2] >> X[i][3];

    // Идём ``по очереди'', отдалясь от кассы.

    // Инвариант: после итерации цикла i=I,
    // часть массива Z от нуля до I заполнена
    // оптимальными временами

    for(i = 0; i < N; i++)
        for(j = 1; j <= 3 && i+j <= N; j++)
            if(!Z[i+j] || Z[i+j] > Z[i] + X[i][j])
                Z[i+j] = Z[i] + X[i][j];
       // ответ содержится в Z[N]

    cout<< Z[N];
    return 0;
}

Инварианты и регулярные выражения

В заключение статьи приведём ещё одну задачу на динамическое программирование. Эта задача уже может быть отнесена к категории сложных, придумать способ её решения гораздо труднее, чем в предыдущих задачах.

Для понимания следующей задачи необходимо ввести специальный термин. Регулярным выражением называется строка-шаблон, составленная по определенным правилам. Любую другую строку можно проверить на соответствие данному регулярному выражению. Основные правила построения шаблонов и проверки соответствия таковы:

  • Если в шаблоне встречается символ, он же должен встретиться в рассматриваемой строке.
  • Если в шаблоне встречается запись вида A | B, то в строке должно встретиться A или B. A и B не обязаны быть буквами алфавита, они, в свою очередь также могут быть регулярными выражениями.
  • В шаблоне разрешается использовать круглые скобки, например, A | (AB)
  • Если в шаблоне встречается [A], то в рассматриваемой строке A может как встретиться, так и нет. Как и в предыдущем правиле, A может быть другим шаблоном.
  • Если в шаблоне встречается A+, значит, терм A может встретиться в строке любое число раз подряд, либо вообще не встретиться.
  • Принято, что если в регулярное выражение необходимо вставить специальный символ, то перед ним ставится обратный слеш \

Например, шаблонами являются AB, A[B], A(B)+. Строка AB подходит под все три шаблона, A — под второй и третий, ABB — только под третий. Под шаблон A[B[C]D] подходят строки A, ABD, ABCD, и не подходят никакие другие (проверьте!).

Задача 8. («Регулярное выражение»)

Дано регулярное выражение — слово из латинских букв, в котором используются квадратные скобочки. То, что заключено в квадратные скобочки, может присутствовать в слове или нет. Таким образом, регулярное выражение задает множество слов, которые можно из него получить, различными способами раскрывая присутствующие в нём квадратные скобочки. Про такие слова говорят, что они удовлетворяют регулярному выражению. Например, регулярному выражению

a[b[c]d]e
удовлетворяют следующие слова:

ae, abde, abcde

и не удовлетворяют слова

abcd, abe, acde

Регулярное выражение имеет следующий рекуррентно-определенный синтаксис:

regexp ::= ( lexem | '[' regexp ']' ) +
Это определение регулярного выражения (regexp) записанное в формате EBNF. Вертикальная палочка в этой записи означает союз 'или'. А комбинация ( X )+ означает несколько (больше нуля) объектов X идущих друг за другом. Поэтому наше определение расшифровывается так: регулярное выражение — это либо лексема (lexem), либо какое-то другое регулярное выражение, заключённое в квадратные скобки. Пример регулярного выражения:

abc[de[f]g][h]i[j].

Дать ответ, удовлетворяет ли данная строка S данному регулярному выражению R. Максимальная длина строки и регулярного выражения — 1000 символов. Регулярное выражение всегда задано корректно.

Например, под шаблон, приведённый в условии задачи, подходят строки «abcdefgi» и «achij», и не подходит строка «abcdefg».

Воспользуемся инвариантами и динамическим программированием для решения этой задачи. Чтобы перейти к инвариантам, надо научиться разбивать задачу на подзадачи так, чтобы из решения простых подзадач вытекало решение общей задачи.

Пусть, к примеру, первая половина строки подходит под первую половину шаблона, а вторая половина строки — под вторую половину шаблона. Тогда вся строка целиком подходит под шаблон. Идея решения заключается в том, чтобы понимать, какая часть строки подходит под какую часть шаблона.

Пойдём по шаблону слева направо, и, рассматривая начало шаблона R[0..i], будем помнить, для каких значений j часть строки S[0..j] подходит под это начало[4]. Покажем, что возможно оуществить переход от части шаблона R[0..i] к R[0..(i+1)]. Для этого введём следующие правила:

  • Если на месте i в шаблоне стоит символ (не квадратная скобка), то часть строки, которая раньше подходила под часть шаблона, будет подходить под него дальше тогда и только тогда, когда в строке следующим идет тот же самый символ. Пример: под шаблон «ab[c[d]]m» подходила строка «abcm», для того, чтобы строка подошла под продолжение шаблона «ab[c[d]]mn» необходимо, чтобы её следующим символом был символ «n».
  • Если в шаблоне встретилась открывающая квадратная скобка, то возможных вариантов два. Либо можно полностью пропустить часть шаблона в квадратных скобках, либо попытаться подставить некоторую часть строки, либо всю строку под часть шаблона, заключённую в квадратных скобках.
  • Если же в шаблоне встретилась закрывающая квадратная скобка, то её можно смело пропускать, потому что раз уж мы добрались до неё, значит, часть шаблона, которая заключалась между этой закрывающей и соответствующей открывающей скобками успешно пройдена.

После формулирования этих условий можно определить метод вычисления таблицы D. Элемент D[i][j] будет равен истине тогда и только тогда, когда начало строки S[0..j] подходит под начало шаблона R[0..i]. Начальные условия: в левом верхнем углу таблицы стоит "истина" (D[0][0] = true), переходы осуществяются по сформулированным выше правилам, а ответ будет содержаться в правом нижнем углу таблицы — в ячейке таблицы D[LengthR][LengthS].

Далее приведена одна из возможных реализаций описанного алгоритма на языке С++.

// ElJudge 062. "Регулярное выражение"
#include
#include
using namespace std;
string R, S;
int LengthR, LengthS;
bool D[1001][1001];
// Если D[i][j] == true, то первые i символов
// шаблона R  могут соответствать первым
// j символам строки S.
int main() {
    int i, j, OpenBrace[1001], Match[1001];
    cin >> R » S;    LengthR = R.length();
    LengthS = S.length();
    for(i = 0, j = 0; i < LengthR; i++) {
        if(R[i] == '[')
            OpenBrace[j++] = i;
        else if(R[i] == ']')
            Match[OpenBrace[--j]] = i;
    }
    // Теперь если R[i] == '[', то  R[Match[i]] == ']'
    //  – соответствующая закрывающая скобка.
    D[0][0] = true;
    for(i = 0; i < LengthR; i++)
        for(j = 0; j <= LengthS; j++)
            if(D[i][j]) {
                // переходим от допустимых D[i][j]
                // к новым D[i2 > i][j2 >= j]
                // закрывающая скобка - пропускаем
                if(R[i] == ']') {
                    D[i+1][j] = true;
                }  else if(R[i] == '[') {  // открывающая скобка
                    D[i+1][j] = true;      // можно как "зайти внутрь"
                    D[Match[i]][j] = true; // так и "пропустить"
                } else {                   // просто буква
                    if(R[i] == S[j])       // только если совпадает
                        D[i+1][j+1] = true;
                }
            }
    // ответ находится в D[LengthR][LengthS]
    if(D[LengthR][LengthS])
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Заключение

Приведём список задач по программированию, для решения которых нужно придумать различные инварианты, а в некоторых задачах — реализовать динамическое программирование. Все задачи находятся на сайте http://acm.mipt.ru/judge.

  • 101: Игра «Камешки»
  • 102: Игра «Камешки II»
  • 103: Игра «Ним в поддавки»
  • 104: Игра «Ромашка»

Для успешного решения различных задач по математике и программированию необходимо уметь пользоваться инвариантами при решении задач. Найти инвариант в сложной задаче непросто, однако это очень мощный, а часто и наиболее быстрый способ получить решение. В программировании владение инвариантами открывает дорогу в мир динамического программирования, одного из наиболее интересных и эффективных методов решения задач.

Сноски.

[1]Строго говоря, инвариант должен быть сформулирован в виде функции, значение которой остается неизменным. Поэтому, инвариант приведённого цикла звучит так: «разность между значением переменной цикла i и количеством выведенных на экран чисел есть ноль». Но в программировании такие «формальные» логические переходы можно пропускать.

[2]Утверждение доказывается методом математической индукции, если заметить, что перед выполнением цикла переменной M присваивается X[0], что есть ни что иное, как максимум в массиве X из элементов [0 ...0].

[3]Задача с Московской городской олимпиады по программированию 2003/2004 г.,http://acm.mipt.ru/judge, задача номер 065.

[4]Символы в строках в языках C и C++ нумеруются, начиная с нуля.


Show attachmentsHide attachments
Topic attachments
I Attachment Action Size Date Who Comment
pngpng 011.png manage 0.8 K 29 Sep 2006 - 17:01 OlgaButygina  
pngpng 1_1.png manage 261.5 K 29 Sep 2006 - 14:04 OlgaButygina  
pngpng 1_2.png manage 275.8 K 29 Sep 2006 - 14:05 OlgaButygina  
pngpng 1_3.png manage 220.5 K 29 Sep 2006 - 16:55 OlgaButygina  
pngpng 1_4.png manage 248.1 K 29 Sep 2006 - 16:55 OlgaButygina  
pngpng 1_5.png manage 272.1 K 29 Sep 2006 - 16:55 OlgaButygina  
pngpng 1_6.png manage 417.3 K 29 Sep 2006 - 17:00 OlgaButygina  
pngpng 1_7.png manage 223.2 K 29 Sep 2006 - 17:00 OlgaButygina  
pngpng 1_8.png manage 278.0 K 29 Sep 2006 - 17:01 OlgaButygina  

© Журнал "Потенциал", 2005-2017. Все права защищены. Воспроизведение материалов сайта и журнала "Потенциал" в любом виде, полностью или частично, допускается только с письменного разрешения редакции.
Отзывы и пожелания шлите почтой.
Подготовка к ЕГЭ
ЕГЭ по математике
login