NWD problem aptekarza.

ďťż

Paweł Kubik - 9 lip 2010, o 19:46
" />W artykule na temat algorytmu Euklidesa na 3 stronie, znajduje się opis rozwiązania problemu z odważaniem porcji leku za pomocą dwóch rodzajów odważników.
Nie do końca jasny jest dla mnie fragment:

Damian Rusak - 12 lip 2010, o 16:49
" />Algorytm Euklidesa daje nam metodę znalezienia X i Y takich, że faktycznie aX + bY = d, stąd też bierze się pierwsza linijka. Zauważmy, że skoro d dzieli zarówno a jak i b to każda ich kombinacja liniowa musi też być podzielna przez d.
Zatem, jeśli chcemy znaleźć x i y takie, że ax + by = k to możemy zrobić to właśnie w taki sposób, że przemnażamy X i Y przez k/d, wiedząc, że d musi dzielić k więc k/d jest całkowite.
Wtedy, zgodnie z linijką trzecią, zauważamy, że całe równanie zostało przemnożone przez k/d, co daje nam szukane równanie na przedstawienie k jako kombinacji liniowej a i b.

Paweł Kubik - 18 lip 2010, o 11:33
" />Dziękuje. Wystarczyło pomyśleć.

Darmowy hosting zapewnia PRV.PL