多语言展示
当前在线:640今日阅读:138今日分享:34

如何使用正则表达式解代数方程组中的丢番图方程

我们知道,正则表达式可以巧妙用来判断一个整数是否是素数,那么更进一步,我们来看如何通过正则表达式,求解代数方程中一类著名的问题,丢番图方程,即整数范围内的整系数方程。
工具/原料

Chrome

方法/步骤
1

我们同样在Chrome浏览器中,来执行相应的JS代码,来实现使用正则表达式,来求解一些简单的丢番图方程,例如,小学奥数题中经常出现的鸡兔同笼问题。

2

1500年前,《孙子算经》中就记载了这个有趣的问题:今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?雉【zhì】,俗称“野鸡”。这句话意思就是把鸡和兔放在同一个笼子中,数头有35个头,数脚有94只脚,那么鸡和兔分别有多少只?我们知道,设鸡和兔分别为x和y只,可以这样列二元一次方程组:x+y=352x+4y=94并求它的正整数解。

3

在正式解方程之前,我们先来看如何使用正则表达式来解多元一次方程的正整数解。举例这个二元一次方程:15x+2y=40首先,我们在Chrome浏览器中,打开Console控制台方法是,在任何网页,按下快捷键F12(或者右击“审查元素”)

4

然后点击“Console”

5

我们正式输入JS代码(其中用到了正则表达式)Array(40+1).join(1).replace(/^(.+)\1{14}(.+)\2{1}$/, '$1,$2').replace(/^[^,]+|[^,]+$/g,function(t){return t.length})然后按下回车键,迅速得到方程的正整数解注意,上述代码中加粗部分,分别为:40:即方程等号右边的数字14:第一个未知数的系数减去11:第二个未知数的系数减去1

6

可以验算一下,(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}) // 根据逗号分隔标记,分别计算这两个子字符串的长度, // 用长度来代替原来的字符串,即可得到方程的解

7

当然最后的替换,我们还可以这样来写,.replace(/.+/g,function(t){var s=t.split(',');return 'x='+s[0].length+','+'y='+s[1].length}) // 得到x=2,y=5更加直观的求解结果。

8

接下来,我们正式回到一开始的鸡兔同笼问题。注意,如果直接按照上述思路,来求解,很可能失败。举例,方程组中的第1个方程,x+y=35因为有很多组解,如果简单使用上述代码,会得到这样的错误解

9

那么如何解决这个困难,尤其在有多个方程(二维甚至更多维)的情况下呢?我们可以尝试使用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

注意事项
1

尽量先计算一下变量精确的约束范围,提高正则表达式求解方程的有效性

2

如果方程系数不为整数,可以先转化成整系数方程

3

使用正则表达式求解方程,效率很低,仅作兴趣参考研究

推荐信息