Mam trzy liczby 6,9,20. Dla danej liczby muszę sprawdzić, czy może być równa sumie wielokrotności tych trzech liczb. Dla przykładu: n = 47 to można stwierdzić, że 47 = 9 * 3 + 20Algorytm ustalania, czy liczba jest sumą wielokrotności innych liczb
n = 23, wtedy nie może być żadnych kombinacji.
Można to ustalić za pomocą o (n^3). Ale czy jest lepszy sposób na zrobienie tego?
To jest równanie liniowe diofantyczne.
Jeżeli współczynnik może być ujemna, a następnie sprawdzić Bézout's identity:
Jeżeli suma jest wielokrotnością GCD liczb, to nie jest rozwiązanie.
W twoim przykładzie gcd = 1, więc istnieje rozwiązanie dla każdej sumy. Więc myślę, że szukasz nieujemnych coefficents .. :(
Károly, jako algorytm pro, mógłbyś rzucić okiem na moje rozwiązanie? – gkovacs90
Chyba mam rozwiązanie dla Ciebie (tylko wtedy, gdy współczynniki może być 0).
Suma wielokrotności 6 i 9 są wielokrotności 3 (z wyjątkiem samego 3). można więc powiedzieć, musimy sprawdzić, czy liczba jest równa 3*k + 20*l.
Tak więc, jeśli masz numer n,
n jest wielokrotnością 3, następuje dekompozycja i możemy ją uznać za prostą (jeśli n jest parzysta, to x*6, jeśli jest to dziwne, że jest 9+x*6n nie jest wielokrotnością liczby 3, zmniejszy się o 20, aż będzie to, niż iść do pierwszego kroku. Jeśli zejdziesz poniżej 0 i nadal nie znajdziesz wielokrotności 3, nie ma rozwiązania.n > 60Bądź ostrożny z 23 i 43, od 3 nie mogą być napisane w taki sposób, 23 i 43 może nie.
Dlaczego to powinno działać? Ponieważ 20 mod 3 = 2, 40 mod 3 = 1, 60 mod 3 =0. Więc po zmniejszeniu o maksymalnie 20 razy 2 razy, znajdziesz wielokrotność 3, które można łatwo rozwiązać.
czy współczynniki mogą być ujemne? –
trzeba spojrzeć na teorię grupową i generatory. Zostało to rozwiązane przez matematyków w celu określenia na przykład minimalnego zestawu monet (groszy, dolarów) potrzebnych do pokrycia całego zestawu wartości pieniężnych. – lucasg
@KarolyHorvath: n = 41 może być rozwiązany z ujemnymi współczynnikami, więc nie sądzę. – grc