JavaScript趣題:丟番圖方程

JavaScript趣題:丟番圖方程,在數學中,丟番圖方程是一種多項式方程,通常存在兩個或多個未知數,要求出它們的整數解。

已知如下的丟番圖方程,求它所有的正整數解。

x2 – 4y2 = n

x和y是未知數,n是一個給定的常量。x,y的解集將使用如下的嵌套數組展示:

[[x1, y1], [x2, y2] ….]

下面是一些例子:

sol_equa(90005) –> [[45003, 22501], [9003, 4499], [981, 467], [309, 37]]

sol_equa(90002) –> []

咋們來看看怎麼解決這個問題,先看這個等式的左邊,x2 – 4y2,你第一眼就有種感覺,它可以轉化為(x – 2y) * (x + 2y),當你想到這一步,就邁出瞭第一步。

因為等式右邊的常量N,它有可能是一個很大的數,如果用窮舉法,效率是很低的。

我們可以嘗試分解這個常量,把它因式分解成兩項。

比方說,N=24,分解成兩項有如下的可能:

[1,24] , [2,12] , [3,8] , [4,6]

我們拿這些可能往式子上套:

x – 2y = 1

x + 2y = 24

————–

x – 2y = 2

x + 2y = 12

……

這樣就轉化成瞭求二元一次方程。

最後,我們選取其中的正整數解即可。

 

function solequa(n) {
    var result = [];
    for(var a=1,b=n;a<=b;a++){
        if(n % a == 0){
            b = n / a;
            var x = (a + b) / 2;
            var y = (b - a) / 4;
            if(parseInt(x) == x && parseInt(y) == y && x >=0 && y >= 0){
                result.push([x,y]);
            }
        }
    }
    return result;
}

發佈留言