방정식을 만족하는 정수 x에 x와 y가 존재하는지 확인하는 방법

Question

시험을 준비하는 동안 방금 시험 문제를 접했고 그 위에 붙어 있습니다. 질문 :

디자인 양의 정수의 X 일련의 주어진 결정 알고리즘 경우 식 X ⁵ + XY - Y ² = Y ³ 두 X 및 Y를 가진 용액을 보유 X에 속함

프로그래밍과 관련된 알고리즘 설계는 없습니다. 누구든지 아이디어를 공유 할 수 있었습니까?

result = false 
foreach (x in X) { 
    foreach (y in X) { 
     if (x^5 + x*y - y^2 == y^3) result = true 
    } 
} 

이 예상보다 더 정교한 뭔가 :

브 루트 포스는

Answer 1

의사 코드 허용되지 않습니다? 그렇다면, 하나는이 같은 상위 용어 x^5을 활용할 수 있습니다에 대한

Sort X as a list from least to greatest. 
result = false 
foreach (y in X) { 
    v = y*y*(y+1) 
    foreach (x in X) { 
     x2 = x*x 
     u = x2*x2 + x*y - v 
     if (u == 0) { 
      result = true 
      goto [DONE] 
     } 
     if (u > 0) goto [NEXT] 
    } 
    [NEXT] 
} 
[DONE] 

Answer 2

큰 입력을하면 수 (정말!) :

1. 정렬 목록;
2. formula을 사용하여 각 숫자에 대한 3 차 방정식을 푸십시오. 여기서 각 숫자가 x이라고 가정하면 수식은 y에 대한 입방식이되므로 수식이 적용됩니다. 그러나이 수식은 실제로 오래 걸릴 수 있으며 가능한 정밀도 문제를 피하기 위해 응답을 확인하기 위해 연결합니다. 그런 다음 정렬 된 목록 (O (logn))에서 이진 검색을 수행하십시오.

이것은 점근 적으로 O (nlogn)를 취할 것이지만, 상수 요소는 큰 오, 멋지게 (어쨌든 질문을 대답 할 때, 프로그램을 코딩하지 않으면) 무섭다. 물론 해싱이 허용되는 경우 (일반적으로 인터뷰의 경우이지만 시험이 반드시 필요한 경우는 아님) O (n) 일 수 있습니다.

Answer 3

X의 함수로 Y 풀기 : http://www.wolframalpha.com/input/?i=x%5E5%2B+xy+-+y%5E2+-+y%5E3는

y(x) := INSERT_EQUATION_HERE 
any((y in setX) for y in y(x) for x in setX) 

이 걸리는 O (| X |), 즉 선형 시간. 당신이 any 기능 또는 목록 조작과 언어를 사용하지 않는 경우

또는, 당신의 솔루션은 좀 더 자세한 수 있습니다

for x in setX: 
    possibleYs = solveForY(x) 
    for y in possibleYs: 
     if y in setX: 
      return SOLUTION:(x,y) 
return NO_SOLUTION 

당신은 실제로 2D를 해결할 필요가 없습니다 내가 위에 보여준 것과 같은 다항식. 대신, 집합의 각 x를 고려할 수 있습니다. 이것은 x를 고치고 y에 다항식을줍니다. 그런 다음 일정 시간 내에 다항식을 풀 수 있습니다. 예를 들어 x = 0이면 y^2 == y^3에 대한 3 개의 해를 찾을 수 있습니다. 만약 x = 1이라면 2-y^2 == y^3에 대한 3 개의 해를 구할 수 있습니다. x = -0.52라면 해답은 http://en.wikipedia.org/wiki/Cubic_function#General_formula_of_roots

더 일반적인 문제 :

임의의 다항식을 고려하는 경우이 방법은 min (max_x_degree, max_y_degree) < 5 경우에만 O (1) 효율을 제공 할 수 있습니다.이는 Galois theory에서 입증 된 것처럼 특정 폐쇄 형 솔루션을 사용하는 유일한 다항식은 차수가 4 이하인 유일한 다항식입니다. 그리고이 문제에서 가장 높은 차수의 변수를 상수로 바꿀 수 있습니다.

이는 O (1) 효율이 수를 늘리면 분 (max_x_degree, max_y_degree) < 5.

것 또한 더 흥미로운 얻을 경우, 다른 방법으로 얻을 수없는 말은 아니다 변수의.

Answer 4

집합 X가 너무 크지 않은 경우 2D 무한 력 알고리즘은 2D 행렬을 구성하여 작동 할 수 있습니다.