Strona główna » Algorytmy » Artykuły » Dzielenie bez Operatora
 

Dzielenie bez Operatora

https://mattomatti.com/a0314

Cel

Napisz algorytm do dzielenie liczb, który nie będzie wykorzystywał standardowego operatora dzielenia. Przygotuj rozwiązanie, które będzie mogło obliczyć wynik i resztą dla dowolnych liczb całkowitych.

Algorytm

Operację dzielenia można zastąpić odejmowaniem dzielnika od dzielnej tak długo jak będzie to możliwe. Kiedy dzielna będzie mniejsza od dzielnika to pozostała wartość jest resztą z dzielenia. Innymi słowy, aby podzielić liczbę przez liczbę wystarczy tylko pętla while. Sytuacja staje się nieco trudniejsza w momencie, gdy liczby mogą być dowolnego znaku.

Implementacja

Liczby Dodatnie

W początkowej wersji algorytmu ograniczmy się do liczb dodatnich. Deklarujemy dodatkowy licznik, który będzie zliczał ile od liczby a odjęliśmy wartości b. Licznik jest wynikiem dzielenia, a końcowa wartość a resztą.

  1. pair<int, int> Podziel(int a, int b) {
  2.   int c = 0;
  3.   while (a >= b) {
  4.     c++;
  5.     a -= b;
  6.   }
  7.   return make_pair(c, a);
  8. }

Liczby Całkowite

Jednak kiedy dopuścimy liczby ujemne sprawy stają się nieco trudniejsze, ponieważ musimy uwzględnić znaki wartości, ponieważ algorytm oczekuje dwóch dodatnich wartości. Ze względu na to, że pobranie znaku wartości i wyznaczenie modułu możemy napisać specjalną funkcję. Po wywołaniu na wartości a wartość będzie dodatnia, a znak zostanie zwrócony jako 1 lub -1.

  1. int ModulZnak(int &a) {
  2.   bool wynik = a > 0;
  3.   a = abs(a);
  4.   return wynik ? 1 : -1;
  5. }

Funkcja Podziel() wymaga drobnych modyfikacji, aby obsługiwać liczby ujemne również.

  1. pair<int, int> Podziel(int a, int b) {
  2.   int c = 0;
  3.   int znak1 = ModulZnak(a);
  4.   int znak2 = ModulZnak(b);
  5.   while (a >= b) {
  6.     c++;
  7.     a -= b;
  8.   }
  9.   return make_pair(c*znak1*znak2, a*znak1);
  10. }

Dodatkowo bardzo ważne jest przekształcenie końcowego wyniku. Przydatne jest tutaj równanie a = w·b + r, gdzie w - wynik dzielenia, a r to reszta. Znak wyniku nie zmienia się jeśli dzielna i dzielnik są tego samego znaku. Z kolei resztajest ujemna wtedy i tylko wtedy, gdy dzielna jest ujemna.

Oto przykładowe dzielenie z wynikiem i resztą:

DzielnaDzielnikWynik
1343 r. 1
-134-3 r. -1
13-4-3 r. 1
-13-43 r. -1

Testowanie funkcji

Poniższy kod wczyta od użytkownika dzielną oraz dzielnik, a następnie wypisze zintepretowany wynik.

  1. int main () {
  2.   int a, b;
  3.   cout << "Podaj liczbe do podzielenia:\n a = ";
  4.   cin >> a;
  5.   cout << "Podaj dzielnik:\n b = ";
  6.   cin >> b;
  7.   pair<int, int> wynik = Podziel(a, b);
  8.   cout << a << " / " << b << " = " << wynik.first;
  9.   if (wynik.second > 0) {
  10.     cout << " r. " << wynik.second;
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }