牛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 :