Zainspirowani tanią, szybką, dobrą , zaimplementujemy algorytm, który ma dokładnie dwa z nich.
Matematyka
Biorąc pod uwagę dwie niezerowe liczby całkowite a i b , GCF d jest największą liczbą całkowitą, która dzieli zarówno i b bez reszty. Współczynniki Bézouta to pary liczb całkowitych (x, y) takie, że ax + by = d . Współczynniki Bézouta nie są unikalne. Na przykład biorąc pod uwagę:
a = 15, b = 9
Mamy
d = 3
x = 2
y = -3
Od 15*2 + 9*(-3) = 30 - 27 = 3
.
Powszechnym sposobem obliczania GCF i pary współczynników Bézouta jest użycie algorytmu Euclida , ale w żadnym wypadku nie jest to jedyny sposób.
Kod
Twój program powinien przyjąć dwie liczby całkowite jako dane wejściowe. Powinien generować / zwracać największy wspólny współczynnik i jedną parę współczynników Bézouta.
Przykładowe dane wejściowe:
15 9
przykładowe wyjście
3 (2, -3)
Dane wyjściowe mogą być w dowolnej kolejności i formacie, ale powinno być jasne, która jest GCF, a które są współczynnikami.
Podstępni
Twój program może być tani, szybki i dobry. Niestety mogą to być tylko dwa z nich jednocześnie.
- Jeśli nie jest tani , program powinien zużywać nadmierną ilość zasobów systemowych.
- Gdy nie jest to szybkie , program powinien zająć zbyt dużo czasu.
- Jeśli nie jest dobrze , wynik programu powinien być nieprawidłowy.
Program powinien być w stanie zrobić (dobrze, nie rób) wszystkie trzy. Co dzieje się, kiedy zależy od Ciebie - może być oparte na czasie, kompilatorze, którego dane wejściowe są większe itp. Kilka dodatkowych uwag:
- Twój program nie powinien być oczywiście podstępny i powinien przejść pobieżną kontrolę. Byłbym trochę podejrzliwy, jeśli zaimplementujesz trzy osobne algorytmy.
- W taniej sytuacji „nadmierna ilość zasobów systemowych” to wszystko, co spowolniłoby inne programy. Może to być pamięć, przepustowość itp.
- W szybkim przypadku „nadmierny czas” oznacza w stosunku do tego, jak przebiega w tanich i dobrych przypadkach. Program powinien się jeszcze zakończyć. Im bliżej „niesamowicie frustruje, ale nie jest wystarczająco frustrujące, aby zatrzymać program”, tym lepiej (zabawniej i).
- W dobrym przypadku wynik nie powinien być oczywiście nieprawidłowy i powinien przejść pobieżną kontrolę. Byłbym bardzo podejrzliwy, gdyby dał mi GCF „2 anna half”.
To konkurs popularności, więc większość entuzjastów wygrywa!
EDYTOWAĆ
Aby to wyjaśnić, szukam programów, które mogą być „szybkie i tanie” oraz „tanie i dobre” oraz „szybkie i dobre” w różnych przypadkach, a nie takie, które wykonują tylko jeden z nich.
źródło
Odpowiedzi:
do
Jest tani i szybki. Dostajesz gcd w mgnieniu oka. Jednak facet, który to zrobił, nie miał pojęcia o tym „czymś Béziera”, więc po prostu podzielił aib przez gcd. (co gorsza, w tym momencie aib są dość dalekie od ich początkowej wartości z powodu algorytmu, który mądrze wybrał)
źródło
DO#
Oblicza to współczynniki Bézouta. Użyłem rozszerzonego algorytmu euklidesowego .
źródło
Perl 5
Nie tanie: main () jest wywoływany rekurencyjnie (zapełnianie stosu), dopóki perl nie wyśle ostrzeżenia o „głębokiej rekurencji”, który opuści aplikację z powodu obsługi __WARN__.
Nie szybko: gdy algorytmy gcf () zwracają poprawne wyniki, kod po prostu zawiesza się na kilka sekund (select () w main ()).
Niezbyt dobrze: wszystkie wyniki powyżej 99 (lub poniżej -99) są nieprawidłowe.
W sumie nie tak kreatywne; czekam na bardziej eleganckie odpowiedzi.
źródło
Pyton
Jest to tanie i szybkie, ale złe jest to, że zakres jest ograniczony do największego wejścia, więc może nie znaleźć pary współczynników.
Dobra łamigłówka.
źródło
JavaScript
Nie tanie
Zużywa wiele zasobów systemowych.
Nie szybko
Użyj oddzwaniania, tak jak dodatkowe zabezpieczenie w razie awarii.
Niedobrze
Ścisły limit
gcf(10, 10)
, tylko do bezpiecznego miejsca na dysku.źródło