牛B的正则表达式：素数判定与线性方程求解

    今天又学到一个牛B东西。你相信吗？正则表达式竟然可以用来判定素数，甚至可以用来解方程！下面这段正则表达式可以用来判断，一个字符串的长度是否为合数（假设这个字符串里全是字符'1'）：
^1?$|^(11+?)1+$
    不信的话，把下面这段代码复制到你浏览器的地址栏里运行一下，True表示这个数为合数，False表示这个数为素数：

javascript:var st="1";for(var i=2;i<100;i++)document.write(i," ",/^1?$|^(11+?)1+$/.test(st=st+"1"),"<br/>");document.close();

    其实，它的原理很简单。加号表示匹配一次或多次（加上一个问号表示非贪婪模式），1表示引用括号里的内容，头尾的^和$则避免了部分匹配的情况。这样，^(11+?)相当于枚举除数大小，而1+$则用于检验整个字符串是否能按此大小恰好分完。如果除得尽，则匹配成功，字符串长度为合数。另外，前面的^1?$只是为了处理n=0或n=1时的特殊情况，而符号|则表示“或者”的意思。

    采用同样的方法，我们还可以想出正则表达式其它一些类似的用途。比如，我们可以用这个正则表达式检查方程11x + 2y + 5z = 115是否有自然数解：
^(.*)1{10}(.*)2{1}(.*)3{4}$
    正则表达式中，{x}表示和前面的内容匹配x次。只要用这个表达式去检测一个有115个字符的字符串，匹配成功则表示有自然数解。它的原理和上面的基本一样，我就不再重复了。

参考资料：http://blog.stevenlevithan.com/archives/algebra-with-regexes

24 条评论

发表评论




Enter Captcha Here :