algorytm do obliczania zestawu roztworu z jednym prostym równaniem o dwóch zmiennych

Question

Załóżmy, że ma prostą równania w postaci:

7x + 4y = n 

, w którym n jest wybrane przez nas i X, Y i n są wszystkie dodatnie liczby całkowite. To jest jedyne równanie, które jest nam dane. Wśród możliwych rozwiązań potrzebujemy rozwiązania (x, y), w którym x jest najmniejszy. na przykład

7x + 4y = 14, then (2, 0) is the solution 
7x + 4y = 15, then (1, 2) is the solution 
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions, 
of which (0, 8) is the correct solution 

Chciałbym zaprojektować algorytm do obliczenia go w jak najmniejszym czasie pracy. Obecny algorytm, który mam na myśli coś takiego:

Given an input n 
Calculate max(x) = n/7 
for i = 0 to max(x) 
    If the equation 7*i + 4*y = n holds 
     return value of i and y 
    else 
     continue 

Algorytm ten, jak sądzę, może mieć czas pracy upto O (n) w najgorszym przypadku zachowań. Czy istnieje jakiś lepszy algorytm do obliczenia rozwiązania?

Answer 1

Rozważmy bardziej ogólny problem

• Dla dwóch względnie pierwsze liczby całkowite dodatnie a i b, zważywszy dodatnia n, znaleźć parę (x,y) o nieujemnych liczb całkowitych takie, że a*x + b*y = n przy minimalnym x. (Jeśli jest jedna. Nie muszą być np 7*x + 4*y = 5 ma rozwiązanie nieujemną x i y.)

Pomijając nonnegativity na chwilę, biorąc pod uwagę wszelkie rozwiązania

a*x0 + b*y0 = n 

wszystkie rozwiązania mają postać (x0 - k*b, y0 + k*a) dla pewnej liczby całkowitej k. Więc reszta x modulo b i y modulo a jest niezmiennikiem rozwiązań i mamy

a*x ≡ n (mod b), and b*y ≡ n (mod a) 

więc musimy rozwiązać równanie a*x ≡ n (mod b) - drugi następuje.

Niech jest to liczba całkowita z a*c ≡ 1 (mod b).Można go znaleźć na przykład w rozszerzonym algorytmie Euklidesa lub (ekwiwalentnie) kontynuowaniu rozszerzenia frakcji a/b w krokach O (log b). Oba algorytmy w naturalny sposób dają unikatową właściwość c < b.

Następnie minimalny kandydat na x jest pozostałą wersją x0 z n*c modulo b.

problem posiada rozwiązanie nieujemną x i y wtedy i tylko wtedy, gdy x0*a <= n, a następnie x0 jest minimalna dodatnią x nie pojawia się w roztworze nonnegtaive x i y.

Oczywiście, dla małych a i b jak 7 i 4, brute force nie mniejsza niż obliczenie odwrotności a modulo b.

Answer 2

Mamy

7(x-4)+4(y+7)=7x+4y 

więc jeżeli (x, y) jest w postaci roztworu, a następnie (4 x, y + 7) jest również rozwiązanie. Stąd, jeśli istnieje rozwiązanie, to jest jeden z x < 4. Dlatego musisz tylko przetestować x = 0..3, który działa w stałym czasie.

Można to rozszerzyć na dowolne równanie formularza ax + by = n, wystarczy przetestować x = 0..b-1.

Answer 3

O (n):

y=n/4; 
while((n-4y)%7!=0 && y!=0){ 
y--; 
} 
x=(n-4y)/7; 

Answer 4

Polecam sprawdzanie metody Simplex w książce Numerical Recipes in C. Możesz łatwo traktować kod C jak pseudo-kod i utworzyć wersję java. Wersja żądanego simpleksa to "ograniczony-simplex", który zajmuje się tylko dodatnimi wartościami. Książka jest available online for free. Zacznij od sekcji 10.8 i czytaj dalej.