如何使用正則表達式解代數方程組中的丟番圖方程?

我們知道,正則表達式可以巧妙用來判斷一個整數是否是素數,那麼更進一步,我們來看如何通過正則表達式,求解代數方程中一類著名的問題,丟番圖方程,即整數範圍內的整係數方程。

如何使用正則表達式解代數方程組中的丟番圖方程

工具/原料

Chrome

方法/步驟

我們同樣在Chrome瀏覽器中,來執行相應的JS代碼,

來實現使用正則表達式,來求解一些簡單的丟番圖方程,

例如,

小學奧數題中經常出現的雞兔同籠問題。

如何使用正則表達式解代數方程組中的丟番圖方程

1500年前,《孫子算經》中就記載了這個有趣的問題:

今有雉兔同籠,上有三十五頭,下有九十四足,問雉兔各幾何?

雉【zhì】,俗稱“野雞”。這句話意思就是

把雞和兔放在同一個籠子中,數頭有35個頭,數腳有94只腳,

那麼雞和兔分別有多少隻?

我們知道,設雞和兔分別為x和y只,可以這樣列二元一次方程組:

x+y=35

2x+4y=94

並求它的正整數解。

如何使用正則表達式解代數方程組中的丟番圖方程

在正式解方程之前,我們先來看如何使用正則表達式

來解多元一次方程的正整數解。

舉例這個二元一次方程:15x+2y=40

首先,我們在Chrome瀏覽器中,打開Console控制檯

方法是,在任何網頁,按下快捷鍵F12(或者右擊“審查元素”)

如何使用正則表達式解代數方程組中的丟番圖方程

然後點擊“Console”

如何使用正則表達式解代數方程組中的丟番圖方程

我們正式輸入JS代碼(其中用到了正則表達式)

Array(40+1).join(1).replace(/^(.+)\1{14}(.+)\2{1}$/, '$1,$2').replace(/^[^,]+ [^,]+$/g,function(t){return t.length})

然後按下回車鍵,迅速得到方程的正整數解

注意,上述代碼中加粗部分,分別為:

40:即方程等號右邊的數字

14:第一個未知數的係數減去1

1:第二個未知數的係數減去1

如何使用正則表達式解代數方程組中的丟番圖方程

可以驗算一下,(2,5)確實是方程15x+2y=40的一組正整數解。

這裡來詳細解釋一下,上面JS代碼的原理。

Array(40+1) // 構建一個包含(40+1)個元素的空數組

.join(1) // 將數組中元素用字符串1連接起來,

// 變成一個40個1組成的字符串

.replace(/^(.+)\1{14}(.+)\2{1}$/, '$1,$2') // 將40個1的字符串,

// 進行正則表達式匹配,

// 匹配為(14+1)個子字符串,

// 以及(1+1)個子字符串

// 這兩個子字符串合起來,即組成原來的40個1的字符串

// 匹配成功後,在這兩個子字符串之間,插入英文半角逗號

.replace(/^[^,]+ [^,]+$/g,function(t){return t.length})

// 根據逗號分隔標記,分別計算這兩個子字符串的長度,

// 用長度來代替原來的字符串,即可得到方程的解

如何使用正則表達式解代數方程組中的丟番圖方程

當然最後的替換,我們還可以這樣來寫,

.replace(/.+/g,function(t){var s=t.split(',');return 'x='+s[0].length+','+'y='+s[1].length})

// 得到x=2,y=5更加直觀的求解結果。

如何使用正則表達式解代數方程組中的丟番圖方程

接下來,我們正式回到一開始的雞兔同籠問題。

注意,如果直接按照上述思路,來求解,很可能失敗。

舉例,方程組中的第1個方程,x+y=35

因為有很多組解,如果簡單使用上述代碼,會得到這樣的錯誤解

如何使用正則表達式解代數方程組中的丟番圖方程

那麼如何解決這個困難,尤其在有多個方程(二維甚至更多維)的情況下呢?

我們可以嘗試使用for循環,來遍歷未知數所在的正整數範圍,進行求解。

for(var x=1;x<35;x++){

var reg=new RegExp('^('+Array(x+1).join(1)+')\\1{1}('+Array(35-x+1).join(1)+')\\2{3}$');

var t=Array(94+1).join(1).replace(reg, '$1,$2').replace(/^[^,]+ [^,]+$/g,function(t){return t.length});

if(/,/.test(t)){

console.log(x+','+(35-x));

break;

}

}

即可得到正確解;

23,12

如何使用正則表達式解代數方程組中的丟番圖方程

注意事項

儘量先計算一下變量精確的約束範圍,提高正則表達式求解方程的有效性

如果方程係數不為整數,可以先轉化成整係數方程

使用正則表達式求解方程,效率很低,僅作興趣參考研究

相關問題答案