Виртуозное владение инвариантами особенно полезно при решении задач по информатике, основанных на методе динамического программирования. Метод динамического программирования заключается в сведении задачи к аналогичным, но более простым. При этом алгоритм заключается в хранении «архива» решений простых задач и последовательном расширении этого архива, пока в него не попадёт нужная нам задача. Алгоритмы, основанные на динамическом программировании, активно используют память. (см. практическая часть, задача 1.).
Инварианты и регулярные выражения
Эта задача уже может быть отнесена к категории сложных, придумать способ её решения гораздо труднее, чем в предыдущих задачах. (см. практическая часть, задача 2.).
Для понимания следующей задачи необходимо ввести специальный термин. Регулярным выражением называется строка-шаблон, составленная по определенным правилам. Любую другую строку можно проверить на соответствие данному регулярному выражению. Основные правила построения шаблонов и проверки соответствия таковы:
Если в шаблоне встречается символ, он же должен встретиться в рассматриваемой строке.
Если в шаблоне встречается запись вида 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, и не подходят никакие другие.
