快捷導(dǎo)航

正則表達(dá)式與數(shù)學(xué)（方程式、線性方程）

更新時(shí)間：2011年04月12日 23:39:36 作者：

大清早的打QQ去，收到一位網(wǎng)友的信息。問得是正則表達(dá)式判斷素?cái)?shù)的。去年看到過，沒記錄下來。

正則表達(dá)式如下：

 
^1?$|^(11+?)\1+$ 可以判斷素?cái)?shù)（換成n個(gè)1的形式，n為數(shù)字的大小。比如5轉(zhuǎn)換為11111；3轉(zhuǎn)換為111；2轉(zhuǎn)換為11。） 

什么是素?cái)?shù)？
初中學(xué)的吧。我們老師當(dāng)初教我們的是“質(zhì)數(shù)”。看下概念：
質(zhì)數(shù)又稱素?cái)?shù)。指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。
換句話說，只有兩個(gè)正因數(shù)（1和自己）的自然數(shù)即為素?cái)?shù)。比1大但不是素?cái)?shù)的數(shù)稱為合數(shù)。1和0既非素?cái)?shù)也非合數(shù)。
這個(gè)正則表達(dá)式是什么意思？
【^1?$|^(11+?)\1+$】中間用【|】分開?！緗】在正則語法里，表示“或”，作用于其前后兩個(gè)單元。(還是不明白的看下面，明白的跳過下面這段)

復(fù)制代碼代碼如下:

 
比如【ab|cd】可以匹配“ab”、也可以匹配“cd”，意思是除了“ab”就是“bc”，如果想匹配“abd”、“acd”那【|】的作用域得改下，加個(gè)范圍 
改成【a(b|c)】(匹配結(jié)果分配組)或者【a(?:b|c)d】(匹配結(jié)果不分配組，更高效率)。 

繼續(xù)剛剛的正則，分為兩個(gè)分支，其一為【^1?$】和【^(11+?)\1+$】。其中【^】脫字符在正則語法中，除了在中括號(hào)【[]】中都是代表開頭的意思，在中括號(hào)中的表示非。
第一個(gè)分支【^1?$】匹配的是“1”或者“”(空字符串)。
第二個(gè)分支【^(11+?)\1+$】，先看下括號(hào)內(nèi)的【(11+?)】匹配的是字符“1”后面接著【1+】就是1到無數(shù)個(gè)1。后面的【?】問號(hào)表示非貪婪，就是盡量少的匹配。
接著往后看【\1+】中，【\1】表示引用已匹配的第一個(gè)組的結(jié)果。也就是第一個(gè)【()】括號(hào)匹配的結(jié)果。同理【\2】就是第二個(gè)括號(hào)捕獲的結(jié)果。(小提示：上面提到的【(?:)寫法就是不分配組，這樣引用的話，就引用不到了】)
【+】就是1到無數(shù)個(gè)了。這個(gè)表達(dá)式我們可以這么看。【(11+?)】看成數(shù)學(xué)中的1+n，其中n為大于0的正整數(shù)。外面的【\1+】也就是引用前面這個(gè)組的次數(shù)。理解成m倍，其中m為大于0的正整數(shù)。
那整個(gè)表達(dá)式就是(1+n)*m。因?yàn)閚、m都大于0，那么1+n肯定大于1，最小為2，最大為無窮大；m最小為1，最大為無窮大。
那么，一個(gè)大于2的正整數(shù)的任何大于零的倍數(shù)永遠(yuǎn)都是合數(shù)，也就是非素?cái)?shù)。
再回過頭來看看這個(gè)表達(dá)式。匹配的分別為0個(gè)或1個(gè)字符串“1”，也就是數(shù)字0，數(shù)字1。和其他所有合數(shù)。整個(gè)表達(dá)式，如果成功匹配就是非素?cái)?shù)，如果不匹配就是質(zhì)數(shù)。這就是對(duì)的了。

復(fù)制代碼代碼如下:

 
if (preg_match('/^1?$|^(11+?)\1+$/i', $subject)) { 
#不是素?cái)?shù) 
} else { 
# 是素?cái)?shù) 
} 

小提示：此鑒定是否為素?cái)?shù)方法僅研究學(xué)習(xí)用，不能用到正式程序中，字符串過長，會(huì)造成非常恐懼大的回溯。
英文博客地址：http://blog.stevenlevithan.com/archives/algebra-with-regexes
在上面的博文中，有提到兩個(gè)方程式與正則表達(dá)式，我們一起來研究下。
•二元方程17x + 12y = 51，其表達(dá)式【^(.*)\1{16}(.*)\2{11}$】。很好理解。【(.*)】也就是0到無數(shù)個(gè)【.】點(diǎn)號(hào)。（這里是接著上文說的，其實(shí)，【.】點(diǎn)號(hào)想表示的是字符“1”）
也就是0到無數(shù)個(gè)1,后面【\1】引用一次。后面【{16}】就是16次。作用于前面的【\1】，也就是16次引用。加上開始的【(.*)】一共正好17次。后面一個(gè)就不說了，跟這個(gè)一樣。
正則引擎會(huì)依次嘗試【(.*)】中0到無數(shù)個(gè)字符“1”，0個(gè)字符“1”，1個(gè)字符“1”，2個(gè)字符“1”一直增加的嘗試。直到成功，否則要嘗試完所有字符“1”的最大個(gè)數(shù)(這里是51個(gè)字符“1”)。
•二、三元方程式11x + 2y + 5z = 115，其表達(dá)式為【^(.*)\1{10}(.*)\2{1}(.*)\3{4}$】，理解就跟上面那個(gè)一樣。注意【\2】、【\3】值得是第2，第3個(gè)括號(hào)捕獲的內(nèi)容，別看花眼了。
——————-分割線——————
上面幾個(gè)有意思的數(shù)學(xué)題都是將整數(shù)轉(zhuǎn)換為對(duì)應(yīng)個(gè)數(shù)的字符“1”。下面這個(gè)，是轉(zhuǎn)換為二進(jìn)制數(shù)的。
先吃飯，以后再寫。

您可能感興趣的文章: