JavaScript趣題：丟番圖方程

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

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

x² - 4y² = n

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

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

下面是一些例子：

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

 

sol_equa(90002) -- []

先看這個等式的左邊，x² - 4y²，你第一眼就有種感覺，它可以轉化為(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;  
}

以上就是 JavaScript趣題：丟番圖方程式的內容，更多相關內容請關注PHP中文網（www.php.cn）！