牛B的正则表达式：整除性判定

Post in Brain F**k, Code Different at Nov 28th, 2008, VIEWs: 761

如何判定一个数能否被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

喜欢这篇文章？点下面的按钮分享...

我要发言

署名 • 非商业性使用 • 相同方式共享

无流言，不YD。来，留个流言吧！

有 8 个流言关于 “牛B的正则表达式：整除性判定”

于仁颇黎 Using

Mozilla Firefox 3.0.4 on

Windows XP Says:
November 29th, 2008 at 8:53 pm

主题不错

Reply(回复)

Matrix67: My Blog » Blog Archive » 趣题：用正则表达式判断一个二进制数是否能被3整除 Using

WordPress 2.6 Says:
December 1st, 2008 at 6:27 am

[...] 强大的“反引用”：http://www.sxnsx.com/niubility-regular-and-divisibility-deciding/ Posted in Program Impossible Tags: 趣题, JavaScript, 数论, 代码Trackback: http://www.matrix67.com/blog/archives/1089/trackback 我猜您可能还喜欢：牛B的正则表达式：素数判定与线性方程求解 [...]