ДМИ*_*КОВ 22 regex math grep fractions
如何使用正则表达式匹配不可缩减的部分？
例如,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
所以事情是在正则表达式中从十进制转换为一元数系统,但我不知道如何.
tch*_*ist 32
由于海报要求单个正则表达式与"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ᴛʀᴀɴᴅᴜᴍ:"退出,已经完成了."
而且你很受欢迎.
答案是在将正则表达式^(?|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";
}
Tim*_*Tim 13
不,它不能做.像一个优秀的计算机科学家一样,我会忽略工具正则表达式的细节,并假设你在询问是否有正则表达式.我对正则表达式的功能知之甚少,以确保它仅限于正则表达式.抛开那个警告.
据此,我们得到:
让我们
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?处于状态.由鸽子洞原则上,有状态和状态,以便存在至少一对索引使得.因此,从DFA的初始状态开始,输入并导致相同的状态(或),并且是不同的素数.p?/NN+1 s?(j,k)s? = s?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不规则,或者不存在正则表达式.