牛B的正则表达式：整除性判定
如何判定一个数能否被3整除? 比如6。
如果你有Python，可以在交互式解释器里面输入：
import re
print re.match("1((10*1)|(01*0))*10*$", "110")!=None
或者直接在你的浏览器地址栏或者Firebug终端输入：
javascript:document.write(/^1((10*1)|(01*0))*10*$/.test("110")); document.close();
其中那个”110″部分为任何正整数的二进制形式。
如果返回/打印出 True，则说明被测试数能被3整除；如果结果是False则是无法被3整除。
看上去很神奇，其实道理很简单。首先我们知道，对于任何一个二进制数总是可以表示为如下形式：
Ac
其中A表示前N个字符，c表示最后一个字符。比如对于12的二进制表示”1100″，A指代的是”110″，c指定”0″
我们知道，2进制中，末尾添0直观地表示原数的两倍，那么末尾添1就是原数的两倍再加一。
基于这个事实，要使得Ac被3整除即 Ac mod 3 == 0，则
存在这么一个函数
f(A, c) =
当c为0时：(A×2) mod 3 = ((A mod 3) × 2) mod 3
当c为1时：(A×2+1) mod 3 = ((A mod 3) × 2 + 1) mod 3
只需要函数f(A, c) == 0就可以了。但是这得求A mod 3，只需要向前递归，把A分解成A’和a’，然后求f(A’, a’)就可以了。现在我们把函数f作为状态转换函数，f的值作为状态，待判断二进制串作为接受串，当然了，终止态必须在0，就有如下自动机：
这样不难得出对应的，判定能否被3整除的正则表达式(^1((10*1)|(01*0))*10*$)
想了解更多正则表达式的在算术上的乐趣，不妨阅读Matrix67同学的文章：http://www.matrix67.com/blog/archives/475
以及http://blog.stevenlevithan.com/archives/algebra-with-regexes
