Algorytm dzielenia i modulo
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*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 liczb bez dzielenia
Posługując się wzorem z poprzedniego akapitu, 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).
int n, p, q, r;
n = 10; // jakaś liczba całkowita
p = 2; // dzielnik
q = 0;
r = n;
while (r>=p)
{
q = q + 1;
r = r - 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++:
#include <iostream>
#include <cstdlib>
using namespace std;
void dziel(int liczba, int dzielnik)
{
int n, p, q, r;
n = liczba; // jakaś liczba całkowita
p = dzielnik; // dzielnik
q = 0;
r = n;
while (r>=p)
{
q = q + 1;
r = r - p;
}
cout << "dzielenie: " << q << endl;
cout << "modulo: " << r << endl << endl; // n-(q*p) = r
}
int main()
{
dziel(10,5);
dziel(3,3);
dziel(10,3);
system("pause >nul");
return 0;
}
Algorytm dzielenia jest wykorzystywany do wyznaczania NWD (algorytm Euklidesa).
