регулярное выражение для сопоставления неприводимых дробей

Question

Как мне сопоставить неприводимые дроби с регулярным выражением?

Например, 23/25, 3/4, 5/2, 100/101 и т. Д.

Прежде всего, я понятия не имею о реализации алгоритма gcd в регулярных выражениях.

Обновление для всех, кто отвечает как "Вы используете неправильный инструмент":

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

Обновлено 2: Идея состоит в том, чтобы найти регулярное выражение, которое может быть полезным в такой ситуации, как:

$> echo "1/2" | grep -P regex
1/2
$> echo "2/4" | grep -P regex

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

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

$> echo "11/1111" | grep -P '^1/1+$|(11+)+\1+/\1+$'
11/1111

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

Answer 1

ОБНОВЛЕНИЕ

Поскольку автор запроса запросил одно регулярное выражение, совпадающее со строками типа "36/270", но говорит, что не имеет значения, насколько оно разборчиво, это регулярное выражение:

my $reducible_rx = qr{^(\d+)/(\d+)$(?(?{(1x$1."/".1x$2)=~m{^(?|1+/(1)|(11+)\1*/\1+)$}})|^)};

Но, если вы, как и я, считаете, что неразборчивое регулярное выражение абсолютно недопустимо, вы напишете это более разборчиво, как:

my $reducible_rx = qr{
  # first match a fraction:
    ^ ( \d+ ) / ( \d+ ) $
  # now for the hard part:
    (?(?{ ( 1 x $1 . "/" . 1 x $2 ) =~ m{
                ^
                (?|    1+      / (1)  # trivial case: GCD=1
                  |  (11+) \1* / \1+  # find the GCD
                )
                 $
            }x
        })
          # more portable version of (*PASS)
     | ^  # more portable version of (*FAIL)
     )
}x;

Вы можете улучшить удобство обслуживания, выделив версию, соответствующую унарной версии.от той, которая соответствует десятичной версии, как это:

# this one assumes unary notation
my $unary_rx = qr{
    ^ 
    (?|   1+       / (1)
      | (11+)  \1* / \1+ 
    ) 
    $
}x;

# this one assumes decimal notation and converts internally
my $decimal_rx = qr{
  # first match a fraction:
    ^ ( \d+ ) / ( \d+ ) $ 
  # now for the hard part:
    (?(?{( 1 x $1 . "/" . 1 x $2 ) =~ $unary_rx})
          # more portable version of (*PASS)
     | ^  # more portable version of (*FAIL) 
     )
}x;

Разве это не намного проще, разделив его на два именованных регулярных выражения?Это теперь сделало бы $reducible_rx таким же, как $decimal_rx, но унарная версия - это его собственная вещь.Я бы так и сделал, но первоначальный плакат требовал одного регулярного выражения, поэтому вам придется интерполировать вложенное для этого, как я впервые представил выше.

В любом случае, вы можете подключиться к тестовому жгуту.ниже с использованием:

    if ($frac =~ $reducible_rx) {
        cmp_ok($frac, "ne", reduce($i, $j), "$i/$j is $test");
    } else {
        cmp_ok($frac, "eq", reduce($i, $j), "$i/$j is $test");
    }

И вы увидите, что это правильное регулярное выражение, которое проходит все тесты и, кроме того, делает это с использованием одного регулярного выражения, поэтому теперь, пройдя все требования исходного вопроса, я объявляю Qᴜᴏᴅᴅᴇᴍᴏɴ ᴅᴇᴍᴏɴsᴛʀᴀɴᴅᴜᴍ: «Выйти, хватит делать». 101

И добро пожаловать.

---

Ответ состоит в том, чтобы сопоставить регулярное выражение ^(?|1+/(1)|(11+)\1*/\1+)$ с дробью после того, как оно было преобразовано из десятичной в унарную запись, и в этот момент самый большой общий коэффициент будет найден в $1 в совпадении;в противном случае они взаимные.Если вы используете Perl 5.14 или выше, вы даже можете сделать это за один шаг:

use 5.014;
my $reg  = qr{^(?|1+/(1)|(11+)\1*/\1+)$};
my $frac = "36/270";  # for example
if ($frac =~ s/(\d+)/1 x $1/reg =~ /$reg/) { 
    say "$frac can be reduced by ", length $1;
} else {
    say "$frac is irreducible";
}

, который правильно сообщит, что:

36/270 can be reduced by 18

(И, конечно, сокращение на 1означает, что знаменателя больше нет.)

Если вы хотите немного повеселиться с читателями, вы могли бы даже сделать это так:

use 5.014;
my $regex = qr{^(?|1+/(1)|(11+)\1*/\1+)$};
my $frac  = "36/270";  # for example
if ($frac =~ s/(\d+)/"1 x $1"/regex =~ /$regex/) {
    say "$frac can be reduced by ", length $1;
} else {
    say "$frac is irreducible";
}

Вот код, который демонстрирует, как это сделать.Кроме того, он создает набор тестов, который проверяет свой алгоритм, используя все (положительные) числители и знаменатели вплоть до аргумента или 30 по умолчанию.Чтобы запустить его под тестовым комплектом, поместите его в файл с именем coprimes и сделайте так:

$ perl -MTest::Harness -e 'runtests("coprimes")'
coprimes .. ok       
All tests successful.
Files=1, Tests=900,  1 wallclock secs ( 0.13 usr  0.02 sys +  0.33 cusr  0.02 csys =  0.50 CPU)
Result: PASS

Вот пример его вывода при запуске без тестового комплекта:

$ perl coprimes 10
1..100
ok 1 - 1/1 is 1
ok 2 - 1/2 is 1/2
ok 3 - 1/3 is 1/3
ok 4 - 1/4 is 1/4
ok 5 - 1/5 is 1/5
ok 6 - 1/6 is 1/6
ok 7 - 1/7 is 1/7
ok 8 - 1/8 is 1/8
ok 9 - 1/9 is 1/9
ok 10 - 1/10 is 1/10
ok 11 - 2/1 is 2
ok 12 - 2/2 is 1
ok 13 - 2/3 is 2/3
ok 14 - 2/4 is 1/2
ok 15 - 2/5 is 2/5
ok 16 - 2/6 is 1/3
ok 17 - 2/7 is 2/7
ok 18 - 2/8 is 1/4
ok 19 - 2/9 is 2/9
ok 20 - 2/10 is 1/5
ok 21 - 3/1 is 3
ok 22 - 3/2 is 3/2
ok 23 - 3/3 is 1
ok 24 - 3/4 is 3/4
ok 25 - 3/5 is 3/5
ok 26 - 3/6 is 1/2
ok 27 - 3/7 is 3/7
ok 28 - 3/8 is 3/8
ok 29 - 3/9 is 1/3
ok 30 - 3/10 is 3/10
ok 31 - 4/1 is 4
ok 32 - 4/2 is 2
ok 33 - 4/3 is 4/3
ok 34 - 4/4 is 1
ok 35 - 4/5 is 4/5
ok 36 - 4/6 is 2/3
ok 37 - 4/7 is 4/7
ok 38 - 4/8 is 1/2
ok 39 - 4/9 is 4/9
ok 40 - 4/10 is 2/5
ok 41 - 5/1 is 5
ok 42 - 5/2 is 5/2
ok 43 - 5/3 is 5/3
ok 44 - 5/4 is 5/4
ok 45 - 5/5 is 1
ok 46 - 5/6 is 5/6
ok 47 - 5/7 is 5/7
ok 48 - 5/8 is 5/8
ok 49 - 5/9 is 5/9
ok 50 - 5/10 is 1/2
ok 51 - 6/1 is 6
ok 52 - 6/2 is 3
ok 53 - 6/3 is 2
ok 54 - 6/4 is 3/2
ok 55 - 6/5 is 6/5
ok 56 - 6/6 is 1
ok 57 - 6/7 is 6/7
ok 58 - 6/8 is 3/4
ok 59 - 6/9 is 2/3
ok 60 - 6/10 is 3/5
ok 61 - 7/1 is 7
ok 62 - 7/2 is 7/2
ok 63 - 7/3 is 7/3
ok 64 - 7/4 is 7/4
ok 65 - 7/5 is 7/5
ok 66 - 7/6 is 7/6
ok 67 - 7/7 is 1
ok 68 - 7/8 is 7/8
ok 69 - 7/9 is 7/9
ok 70 - 7/10 is 7/10
ok 71 - 8/1 is 8
ok 72 - 8/2 is 4
ok 73 - 8/3 is 8/3
ok 74 - 8/4 is 2
ok 75 - 8/5 is 8/5
ok 76 - 8/6 is 4/3
ok 77 - 8/7 is 8/7
ok 78 - 8/8 is 1
ok 79 - 8/9 is 8/9
ok 80 - 8/10 is 4/5
ok 81 - 9/1 is 9
ok 82 - 9/2 is 9/2
ok 83 - 9/3 is 3
ok 84 - 9/4 is 9/4
ok 85 - 9/5 is 9/5
ok 86 - 9/6 is 3/2
ok 87 - 9/7 is 9/7
ok 88 - 9/8 is 9/8
ok 89 - 9/9 is 1
ok 90 - 9/10 is 9/10
ok 91 - 10/1 is 10
ok 92 - 10/2 is 5
ok 93 - 10/3 is 10/3
ok 94 - 10/4 is 5/2
ok 95 - 10/5 is 2
ok 96 - 10/6 is 5/3
ok 97 - 10/7 is 10/7
ok 98 - 10/8 is 5/4
ok 99 - 10/9 is 10/9
ok 100 - 10/10 is 1

А вот и программа:

#!/usr/bin/env perl
#
# coprimes - test suite to use unary coprimality algorithm
# 
# Tom Christiansen <tchrist@perl.com>
# Sun Apr 17 12:18:19 MDT 2011

use strict;
use warnings;

my $DEFAULT = 2*3*5;
my $max = @ARGV ? shift : $DEFAULT;

use Test::More;
plan tests => $max ** 2;

my $rx = qr{
    ^
    (?|   1+       / (1)
      | (11+)  \1* / \1+
    )
    $
}x;

for my $i ( 1 .. $max ) {
    for my $j ( 1 .. $max ) {
        my $test;
        if (((1 x $i) . "/" . (1 x $j)) =~ /$rx/) {
            my $cf = length($1);
            $test = $i / $cf;
            $test .= "/" . $j/$cf unless $j/$cf == 1;
        } else {
            $test = "$i/$j";
        }
        cmp_ok($test, "eq", reduce($i, $j), "$i/$j is $test");
    }
}

sub reduce {
    my ($a, $b) = @_;
    use Math::BigRat;
    my $f = new Math::BigRat "$a/$b";
    return "$f";
}

Answer 2

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

Переписав это, мы получим:

Пусть L будет языком {"a / b" | где a и b - натуральные числа, закодированные в радиксе r, а a и b - взаимно простые} . L регулярно?

Предположим, что такой язык является регулярным. Тогда существует DFA, который может принять решение о членстве в L. Пусть N будет числом состояний такого DFA. Существует бесконечное число простых чисел. Поскольку число простых чисел бесконечно, число произвольных чисел больше, чем наибольшее число, кодируемое в N цифрах в основании r. (Примечание: наибольшее число явно r возведено в степень N. Я использую эту странную формулировку, чтобы показать, как приспособить унарный.) Выберите N+1 простых чисел, которые больше этого числа. Все эти числа кодируются с использованием не менее N+1 цифр (в основании r). Перечислите эти простые числа от p₀ до pₙ. Пусть sᵢ будет состоянием, в котором pᵢ находится сразу после чтения /. По принципу голубиной дыры существует N состояний и N+1 sᵢ состояний, поэтому существует хотя бы одна пара индексов (j,k), такая что sⱼ = sₖ. Таким образом, начиная с исходного состояния DFA, входы pₖ/ и pⱼ/ приводят к одному и тому же состоянию sⱼ (или sₖ), а pⱼ и pₖ являются различными простыми числами.

L должен принимать все пары различных простых чисел p/q, поскольку они взаимно просты, и отвергать все простые числа, разделенные друг на друга p/p, поскольку p не является взаимно простым для p. Теперь язык принимает pⱼ = pₖ, поэтому существует последовательность состояний от sⱼ с использованием строки pₖ до принимающего состояния, назовите эту последовательность β. Пусть α будет последовательностью состояний, читающей pₖ, начиная с исходного состояния. Последовательность состояний для DFA, начинающаяся с начального состояния для строки pₖ/pₖ , должна быть такой же, как α, за которой следует β. Эта последовательность начинается в исходном состоянии, переходит к sₖ (при чтении ввода pₖ) и достигает состояния принятия при чтении pₖ. DFA принимает pₖ/pₖ и pₖ/pₖ в L. pₖ не взаимно прост с pₖ, и поэтому pₖ/pₖ не находится в L. Противоречие. Поэтому язык L нерегулярен или регулярного выражения не существует.

Answer 3

Если вы пишете числа в одинарном формате и используете ":" в качестве знака деления, я думаю, что это соответствует приводимым дробям:

/^1+:1$|^(11+):\1$|^(11+?)\2+:\2\2+$/

Затем вы можете использовать! ~, Чтобы найти строки, которые не соответствуют.

На основании этого: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

Answer 4

Вы можете знать, что число, заканчивающееся на (0,5), делится на (5), или заканчивающееся на (2,4,6,8,0), делится на 2.

Для 3,4,6,7,8,9 в качестве делителей я бы не ожидал такой возможности, и не для произвольных делителей тоже.

Полагаю, вы знаете метод, позволяющий решить делимость на 3 - построить рекурсивную перекрестную сумму, которая должна делиться на 3, чтобы сделать число делимым. Таким образом, вы можете исключить все 3, 6 и 9 из числа, а также 0. Для произвольного числа вы должны действовать следующим образом:

• удалять каждые 0369
• изменить 47 на 1 (потому что 4% 3 и 7% 3 = 1)
• изменить 58 на 2, причину см. Выше
• меняется каждые 2 на 11
• изменить каждую группу из 111 на ничто.

Если результат пустой, число делится на 3:

echo ${RANDOM}${RANDOM}${RANDOM} | sed 's/[0369]//g;s/[47]/1/g;s/[58]/2/g;s/2/11/g;s/1\{3\}//g'

Подобный подход может работать для 9, где у вас есть похожее правило. Но общий подход для произвольных делителей?