Регулярные выражения делимости чисел

info@vsetut.pro

Стать автором

Вернуться

13.03.2025 15:29:04 | Хабр

Хабы: Регулярные выражения, Ненормальное программирование, Программирование

Меня с детства привлекала тема признаков делимости числа. Особенно удивительно было узнать про признаки делимости на 3 и на 9, когда путем простого сложения всех чисел и проверки результата можно было узнать делится ли изначальное число на эту цифру. Кроме того было интересно узнать, что существует регулярное выражение определяющее простоту числа. Но основной фокус там в том, что число записывается в унарном виде.

И вот пару лет назад я встретил еще одну интересную задачу по написанию регулярного выражения для определения делится ли искомое число на 7. Само число при этом написано в двоичном виде. Признаки делимости на 7 существуют и для двоичной и для десятичной записи, но как правило они требуют производить операции умножения, сложения и рекурсивно проверять делимость уже получившегося в итоге этих действий меньшего числа, что не очень подходит для написания регулярного выражения. Я предполагал, что каким то образом могут помочь сложные операторы: условное сопоставление (позиционные проверки), обратные ссылки итд, но не разобрался как их использовать конкретно для данной задачи. Гораздо больше я думал в сторону более простой регулярки с использованием только оператора ИЛИ, квантификаторов и скобок. Остановился на построении графа остатков от деления следуя, по которому можно получить остаток заданного числа, но уперся в то, что всякое выражение с использованием скобок, но без ссылок - это в итоге дерево и поэтому произвольный граф туда не ложится. Это как пытаться хранить произвольный граф в JSON или XML - можно, но нужно будет вводить идентификаторы узлов и поля ссылок, а в то же время хранение простого дерева этого не потребует.

Подробнее