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;  
}

위 내용은 자바스크립트 재미있는 질문: 디오판틴 방정식의 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!