P-Programowanie

Algorytm dzielenia i modulo

2 sierpnia 2013, kategoria: Matura z informatyki

W tym artykule, przedstawię bardzo prosty algorytm dzielenia oraz algorytm dzielenia modulo. Długo zastanawiałem się nad odpowiednim działem ale ostatecznie zdecydowałem się na dział matura. Sam algorytm jest bardzo prosty i polega na dzieleniu liczb całkowitych bez posługiwania się operatorem dzielenia. 

Przedstawienie liczby jako kombinacja liniowa

Algorytm, który opiszę był kiedyś omawiany na matematyce dyskretnej jako wstęp do kongruencji. Stwierdziłem, że ten problem może bez wątpienia pojawić się na maturach z informatyki. Jest dość prosty i wymaga odrobinę logicznego myślenia. Nawet jeżeli nie pojawi się w drugiej części, to z pewnością może pojawić się w pierwszym arkuszu z poleceniem np. przeanalizowania tabelki.

Dzieląc liczbę 10 przez 5, otrzymujemy ładny okrągły wynik. Dzieląc liczbą 10 przez liczbę 3, otrzymujemy 3 całości i 1 reszty. Reszta ta jest wynikiem dzielenia modulo (w C++ operator „%”), a całości są wynikiem dzielenia całkowitego (w C++ operator „/”).

Dla każdej liczby całkowitej n istnieje taka para liczb q i r, że:

n=p \cdot q+r

Gdzie n jest dowolną liczbą całkowitą, p jest dzielnikiem, q ilorazem a r resztą.

Przykładowo, jeżeli n=10 oraz p=5 to q=2 i r=0 (bo 10 = 5*2 + 0).
Przykładowo, jeżeli n=13 oraz p=3 to q=4 i r=1 (bo 13 = 3*4 + 1).

Łatwo można zauważyć, że n jest liczbą, którą dzielimy, q jest wynikiem dzielenia całkowitego a r jest wynikiem dzielenia modulo.

Dzielenie bez dzielenia

Posługując się wzorem z poprzedniego paragrafu, możemy ustalić, że w ekstremalnym wypadku reszta z dzielenia jest maksymalnie równa liczbie (czyli r=n) oraz, że wynik dzielenia jest minimalnie równy zero (czyli q=0). Bardzo prawdopodobne jest, że te założenia okażą się fałszywe, zależnie od wpisanych liczb.

Budując algorytm dzielenia posłużymy się pętlą while, będzie się ona wykonywać do momentu, aż reszta z dzielenia (r) będzie większa bądź równa dzielnikowi (p). W kolejnych obiegach pętli będziemy o jeden zwiększać wynik dzielenia (q) i zmniejszać wynik dzielenia modulo (czyli resztę) o wartość dzielnika (p).

Po wykonaniu się algorytmu zmienna q będzie wynikiem dzielenia a zmienna r wynikiem dzielenia modulo. Zwróć uwagę, że wynik dzielenia modulo możemy przedstawić także jako n-(q*p). Możemy napisać funkcję w programie dzielącą liczby całkowicie i modulo, bez użycia operatorów z języka C++.

Algorytm dzielenia jest wykorzystywany do wyznaczania NWD (algorytm Euklidesa) i stanowi wstęp do kongruencji i równań kongruencyjnych w matematyce dyskretnej.

Komentarze:

Użytkownik krzysiek napisał/a:

08 września 2013


Bardzo fajnie wytłumaczone i (co bardzo pomaga w czytaniu) dopracowany graficznie :)

Użytkownik arek napisał/a:

22 listopada 2016


Niestety algorytm nie działa prawidłowo dla liczby ujemnej.

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0

Zachęcam Cię do polubienia bloga na facebooku! Dając lajka wspierasz moją pracę - wszystkie artykuły na blogu są za darmo!