Najmniejsza wspólna wielokrotność – implementacje

W jednym z poprzednich postów omawialiśmy czym jest największy wspólny dzielnik i jak go w sposób programistyczny wyznaczyć. W ramach serii wpisów o algorytmach dzisiaj omówimy czym jest najmniejsza wspólna wielokrotność dwóch liczb naturalnych, a także jak ją wyznaczyć.

Za najmniejszą wspólną wielokrotność n i k uznajemy taką najmniejszą liczbę, która jest różna od zera i jednocześnie jest wielokrotnością obu liczb. Najmniejsza wspólną wielokrotność dwóch liczb może zostać obliczona, gdy znamy ich największy wspólny dzielnik ze wzoru n*k/NWD(n, k). O tym, jak wyznaczać NWD przeczytasz tutaj.  

Choć, raczej nie wygląda to jak w programie komputerowym, to wyszukiwanie NWW wykonujemy np. podczas szukania wspólnego mianownika dodawanych ułamków. Weźmy dla przykładu liczby 36, 60, 210. Dosyć niepraktycznym byłoby ich wymnażanie, bo ich iloczyn wynosi 453 600. Łatwo sobie zatem wyobrazić jak wielkie by były wtedy liczniki. Bardziej praktycznym rozwiązaniem jest wyznaczenie ich NWW, które wynosi 1260. Jak więc wyznaczyć NWW? Poniżej omówimy algorytm, a następnie dokonamy jego implementacji w trzech, dostępnych na maturze językach programowania.

Algorytm wyszukiwania największej wspólnej wielokrotności

Z racji, iż znamy wzór na największą wspólną wielokrotność, możemy go wykorzystać w naszym algorytmie. Znacząca jego część opiera się jednak na algorytmie wyznaczania największego wspólnego dzielnika. Jeżeli więc chcesz dokładniej przeanalizować jego działanie, odsyłam Cię do tego wpisu.

Sam algorytm na wyznaczanie NWW nie jest skomplikowany, gdy mamy już gotowy na NWD. Pobieramy najpierw od użytkownika dwie liczby naturalne dodatnie a oraz b. Następnie obliczamy ich największy wspólny dzielnik i zapisujemy go w zmiennej pomocniczej. Teraz wystarczy już tylko obliczyć iloczyn z a i b. Następnie trzeba podzielić go przez przechowany NWD, a następnie zwrócić wartość. Tak opisany algorytm możemy przedstawić na schemacie blokowym:

największa wspólna wielokrotność - schemat blokowy

Implementacja wyszukiwania NWW w Javie, C++ oraz Pythonie

Mając już nasz algorytm, możemy użyć go w programie. Zapewne większość z Was, czytelnicy, przygotowuje się właśnie do egzaminu maturalnego z informatyki. Z myślą o Was, tak jak w poprzednich wpisach o algorytmach, przygotowałem trzy implementacje w dostępnych na maturze językach: C++, Java i Python. W każdym z nich użyłem, już wcześniej zaimplementowaną funkcję, liczącą NWD w sposób rekurencyjny. Jeżeli nadal nie wiesz, czym jest rekurencja, to polecam zapoznać się z tym wpisem, w którym wszystko jest wyjaśnione.nww.cpp

C++

Java

Python

Najmniejsza wspólna wielokrotność — co warto o niej wiedzieć

  • Podobnie jak w przypadku NWD, aby obliczyć najmniejszą wspólną wielokrotność więcej niż dwóch liczb, wystarczy obliczyć p=NWW pierwszych dwóch. Następnie NWW dla p i kolejnej liczby i tak dalej, aż dojdziemy do ostatniej liczby.
  • Wzór na NWW można przekształcić, przez co możliwe jest obliczenie NWD dwóch liczb, gdy mamy ich największą wspólną wielokrotność: NWD = a*b/NWW(a,b)
  • NWW można również obliczyć, mając jedynie kartkę papieru i długopis. Wystarczy rozpisać czynniki obu liczb, wyznaczyć te czynniki, które nie są dla nich wspólne, a następnie obliczyć iloczyn jednej z tych dwóch liczb i czynników, które nie są wspólne z drugiej liczby.

Matura z informatyki coraz bliżej, a Ty nadal nie wiesz jak się do niej przygotować? Rzuć okiem na wpis, w którym omówiłem na co należy najbardziej zwrócić uwagę przy nauce. Znajdziesz też tam inne ważne algorytmy i odnośniki do ich objaśnienia.

grupa wsparcia matura z informatyki
You Might Also Like
1 Comment
Dodaj komentarz

icon