Jak ustalić, czy x i y istnieją w zbiorze liczb całkowitych X spełniających równanie

Question

Po prostu trafiłem na pytanie egzaminacyjne przygotowując się do egzaminu i utknąłem na nim. pytanie brzmi:

zaprojektować algorytm który, biorąc pod uwagę zestaw dodatnich liczb całkowitych X ustala, czy jako x + XY - Y = Y zawiera roztwór z X i Y należące do X.

Nie wymaga żadnego programowania, tylko projekt algorytmu. Czy ktoś mógłby podzielić się swoimi pomysłami?

brute force jest nie do przyjęcia

Answer 1

Pseudokod:

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

Czy coś bardziej wyrafinowane niż to oczekiwano? Jeśli tak, to można skorzystać z terminu wyższego rzędu x^5 tak:

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

dla dużych wejście, można (naprawdę!):

1. Sortuj lista;
2. Rozwiąż równanie sześcienne dla każdego numeru, używając formula. Zakładając, że każda liczba to x, więc równanie staje się sześcienne dla y, wtedy formuła ma zastosowanie. Jednak ta formuła może trwać naprawdę długo, a aby uniknąć ewentualnego problemu z precyzją, można podłączyć odpowiedź, aby to sprawdzić. Następnie wykonaj wyszukiwanie binarne na posortowanej liście (O (logn)).

To zajmie asymptotycznie O (nlogn), ale stały czynnik jest przerażający i ukryty przez wielkiego Oh ładnie (dobrze, jeśli odpowiadasz na pytanie, nie kodując programu). Oczywiście, jeśli mieszanie jest dozwolone (co zwykle ma miejsce w przypadku rozmowy kwalifikacyjnej, ale niekoniecznie w przypadku egzaminów), może to być O (n).

Answer 3

rozwiązać dla Y w funkcji X: 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) 

Ma to O (| X |), czyli liniowy, czas.

Ewentualnie, jeśli nie jest używany język z any funkcji lub listy manipulacji, to rozwiązanie musi być nieco bardziej gadatliwy:

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

rzeczywistości nie mają rozwiązać 2D wielomian, jak pokazałem powyżej. Zamiast tego można rozważyć każde x w zestawie; to naprawia x i daje wielomian w y. Następnie rozwiązujesz ten wielomian w stałym czasie. Na przykład, jeśli x = 0, znajdziemy 3 rozwiązania dla y^2 == y^3; jeśli x = 1, znaleźlibyśmy 3 rozwiązania 2-y^2 == y^3, jeśli x = -0,52, chcielibyśmy. Rozwiązanie: http://en.wikipedia.org/wiki/Cubic_function#General_formula_of_roots

Bardziej ogólna wersja problemu:

Jeśli wziąć pod uwagę arbitralny wielomian, należy pamiętać, że ta metoda może zapewnić tylko wydajność O (1) w następującym przypadku: min (max_x_degree, max_y_degree) < 5.Jest tak, ponieważ, jak udowodniono w Galois theory, jedynymi wielomianami z pewnymi rozwiązaniami o zamkniętej formie są te o stopniu 4 lub mniejszym. W tym problemie możemy po prostu zmienić zmienną w najwyższym stopniu w stałą.

To nie znaczy, że O (1) sprawność nie można uzyskać za pomocą innej metody, w przypadkach, w których min (max_x_degree, max_y_degree) < 5.

miejsca również uzyskać bardziej interesujące, jeśli zwiększy liczbę zmiennych.

Answer 4

Jeśli zbiór X nie jest zbyt duży, wówczas prosty algorytm siły może działać, tworząc macierz 2D.