Идеи реализации

Идея из главы 32. «Поиск простых чисел с помощью регулярных выражений» сработает и на этот раз, но на этот раз не для проверки делимости одного числа на другое, а для решения линейного диофантова уравнения. Нужно сопоставить специально подготовленную строку из одинаковых символов (хотя бы тех же самых букв Q) со специально подготовленным регулярным выражением.

Длина специально подготовленной строки — это число в правой части уравнения (последний параметр командной строки).

А теперь перейдём к регулярному выражению.

Разрешимость уравнения — это возможность разбить строку из b символов на группы, длины которых в символах равны слагаемым из левой части уравнения: l i = a i x i . Если такое разбиение возможно, значения неизвестных легко найти: x i = l i a i .

Проиллюстрируем сказанное на примере уравнения 5 x + 11 y = 37 :

◄─────────────────37────────────────► QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ ◄──────15─────►◄─────────22─────────►

Всё, что требуется от двух символьных групп в этом примере — это чтобы их длины были бы кратными соответственно 5 и 11. Эти группы соответствуют регулярным выражениям (Q*)\1{4} и (Q*)\1{10}. Вся же строка, составленная из 37 букв, должна соответствовать, от начала до конца, шаблону ^(Q*)\1{4}(Q*)\2{10}$. Этот шаблон начинается и заканчивается значками привязки к началу и концу строки, а между ними расположены однотипные фрагменты вида (Q*)\i{ai1}, где i = 1 n .

До сих пор нам приходилось пользоваться неизменными, заранее записанными в тексте программы шаблонами регулярных выражений. Теперь понадобились шаблоны, не определённые заранее. Можно ли нужный шаблон составить во время выполнения программы, а не на этапе её написания? Можно. Поскольку в шаблоне могут использоваться переменные, нужно заранее, до осуществления поиска, сформировать строку с шаблоном, а затем поместить её в оператор поиска.

Итак, успешность сопоставления с регулярным выражением означает наличие целого неотрицательного решения у уравнения, а неудача при сопоставлении — отсутствие таких решений. А как же найти само решение? Числа x 1 x 2 x 3 окажутся равными соответственно длинам (в символах) переменных $1, $2, $3, … Значения этих переменных, напомним, содержат части строки, захваченные группами захвата в регулярном выражении. Нам потребуется перебор в цикле этих переменных, и это представляет некоторую проблему. В следующем разделе мы разберёмся с этой трудностью.

Информатика-54© А. Н. Швец