Strona główna » Algorytmy » Artykuły » Dzielenie pisemne
12:43

Dzielenie pisemne

Wstęp

Dzielenie pisemne pozwala na wygodne dzielenie dwóch liczb dodatnich. Komputery nie potrzebują znać takiego sposobu, aby podzielić liczby, ale mogą nam podpowiedzieć jak takie dzielenie wykonać krok po kroku.

Zadanie

Na wejściu będą dane dwie liczby całkowite. Zadaniem programu jest wypisać na wyjście kolejne kroki dzielenia pisemnego czyli wszystkie linijki jakie trzeba by zapisać podczas tradycyjnego zapisywania dzielenia na kartce. Przykładowo dla danych:

  1. 1253
  2. 12

program wypisze na ekran:

  1. Wynikiem dzielenia jest: 104, reszty 5
  2.   104 r. 5
  3. ───────────
  4.  1253 : 12
  5. -12
  6. ───
  7.  ==53
  8.   -48
  9.   ───
  10.    =5

Implementacja

Założenia wstępne

Zwykła konsola Windows nie udostępnia możliwości formatowania wypisywanego tekstu, więc wszystkie linie poziome będziemy wypisywać jako linijkę znaków. Najprostszym rozwiązaniem jest użycie znaku myślnika, ale zdecydowanie lepszym pomysłem jest użycie znaku 196, którego głównym przeznaczeniem jest rysowanie tabelek w konsoli. W celu uniknięcia powtarzania wpisywania 196 i castowania na typ char zadeklarujemy stałą LINE, która będzie przechowywać znak:

  1. const char LINE = 196;

Funkcja pomocnicze

Funkcją, która ułatwi pisanie kodu pozwoli na wypisanie tego samego znaku n razy. Nazwijmy ją coutChar(). Będzie przyjmować dwa argumenty: liczbę całkowitą n oraz znak c. n określi nam ile znaków c chcemy wypisać. Domyślnie ustalamy, że znakiem, który chcemy wypisać jest spacja, więc w celu wypisania n spacji nie musimy podawać drugiego argumentu.

  1. void coutChar(int n, char c = ' '){
  2.   for(; n>0; n--) cout << c;
  3. }

Wszystkie wiersze muszą być odpowiednio wyrównane. Nie możem tego osiągnąć bez znajomości długości wypisywanej liczby, dlatego deklarujemy funkcję intLength(), która dla podanej liczby sprawdzi z ilu składa się z cyfr i zwróci tę wartość. W funkcji stosuje rekurencje.

  1. int intLength(int n){
  2.   return n < 10 ? 1 : 1 + intLength(n / 10);
  3. }

Ostatnią funkcją, której zastosowanie pozwala uprościć kod też dotyczy liczby. Będziemy potrzebowali "odciąć" od liczby pierwszą cyfrę. Taką implementację przedstawia funkcja getFirstDigit():

  1. int getFirstDigit(int &n){
  2.   int w = n / (pow(10, intLength(n) - 1));
  3.   n = n - w * pow(10, intLength(n) - 1);
  4.   return w;
  5. }

(1.) Nasz funkcja zwróci liczbę całkowitą to jak pierwszą cyfrę. Argumentem jest liczba n, którą przekazujemy przez referencję. Zaletą takiego rozwiązania jest używanie tylko zmienny prostych bez struktur, ponieważ inaczej byśmy musieli zwrócić dwie liczby całkowite jako jedną zmienną. Dzięki referencji możemy zmodyfikować liczbę, a przez return zwrócić interesującą nas liczbę. (2.) Jeśli podzielimy zmienną int przez 10dl - 1, gdzie dl jest długością liczby n. W części całkowitej zostanie wtedy tylko pierwsza cyfra, a pozostałem będą w części ułamkowej, która zostanie obcięta ze względu na typ danych. (3.) Z liczby n pobraliśmy pierwszą cyfrę, ale teraz musimy jej się pozbyć z liczby n. (4.) Zwracamy pobraną cyfrę.

Funkcja właściwa

Na początek wczytujemy dane:

  1. int main () {
  2.   int a, b;
  3.   cout << "Dla a/b podaj a i b:\n";
  4.   cin >> a >> b;

(2.) Deklarujemy zmienne - a będzie dzielną, a b dzielnikiem. (3.) Wypisujemy komunikat co chcemy, aby użytkownik wprowadził. (4.) Wczytujemy obydwie liczby.

  1.   if(a < 0 || b <= 0){
  2.     cout << "Podano nieprawidłowe argumenty!\n";

(5.) Jeśli wprowadzone liczby nie są dodatnie i / lub dzielnik jest zerem to (6.) wypisujemy komunikat o nieprawidłowych argumentach.

  1.   } else {
  2.     int reszta = a % b;
  3.     int wynik = a / b;
  4.     cout << "Wynikiem dzielenia jest: " << wynik;
  5.     if(reszta != 0) cout << ", reszty " << reszta;
  6.     cout << "\n\n";

(7.) Jeśli jednak liczby spełniają założenia to (8.) obliczamy wynik (bez reszty) oraz (9.) resztę. (10.) Wypisujemy zdanie o wyniku dzielenia. (11.) Informacje o reszcie wypisujemy tylko wtedy, gdy rzeczywiście jest taka potrzeba. (12.) Zostawiamy odstęp pomiędzy zdaniem, a częścią zapisu dzielenia pisemnego.

  1.     int a_length = intLength(a);
  2.     coutChar(a_length - intLength(wynik) + 1);
  3.     cout << wynik;
  4.     if(reszta != 0) cout << " r. " << reszta;
  5.     cout << "\n";
  6.     coutChar(a_length + intLength(reszta) + 6, LINE);
  7.     cout << "\n " << a << " : " << b << "\n";

(13.) Zmienna a_length będzie przechowywać długość dzielnej. (14.) Wypisujemy odpowiednią ilość spacji, aby ostatnie cyfry dzielnej i wyniku dzielenia były w tej samej kolumnie. (15.) Wypisujemy wynik dzielenia i jeśli (16.) istnieje reszta to również ją. (17.) Przechodzimy do następnej linijki i wypisujemy kreskę odpowiedniej długości. (18.) Wypisujemy dzielną oraz dzielnik.

  1.     int countf = 0;
  2.     while(wynik != 0){
  3.       int wynik_length = (wynik == 0 ? 0 : intLength(wynik));
  4.       int minus = getFirstDigit(wynik) * b;
  5.       while(minus > countf){
  6.         countf *= 10;
  7.         countf += getFirstDigit(a);
  8.       }

(19.) Deklarujemy zmienną countf, która będzie przechowywać aktualny wynik odejmowania kolejnych części liczby. (20.) Kolejne kroki dzielenia pisemnego będziemy wyprowadzać w pętli dopóki wynik nie osiągnie 0. Wynikać to będzie z pobierania kolejnych z cyfr wyników w celu obliczenia ile w danym kroku powinniśmy odjąć od liczby. (21.) Deklarujemy zmienną wynik_length, której użyjemy do pozycjonowania operacji w konsoli. Warto zauważyć, że liczby 0 nie będziemy wypisywać, ale funkcja intLength() zwróci nam jej faktyczną długość zapisu 1. Co będzie prowadzić do nieprawidłowego przesunięcia w dalszej części. (22.) Zmienna minus w każdej linijce pozwoli na określić ile odejmujemy w dany kroku. (23. - 26.) Pozostaje nam teraz jedynie pobrać odpowiednią część dzielnej, aby można było odjąć i wypisać wynik. Pobieranie kolejnych cyfr z liczby wykonujemy, aż uzyskamy liczbę większą lub równą minus - czyli będziemy mogli wykonać operacje.

  1.       int margin = a_length - intLength(minus) - wynik_length + 1;
  2.       coutChar(margin);
  3.       cout << "-" << minus << endl;
  4.       coutChar(margin);
  5.       coutChar(intLength(minus) + 1, LINE);
  6.       cout << endl;

(27.) Liczymy kolejną zmienną margin, która pozwoli nam odpowiednio wyrównać wypisywaną liczbę. (28.) Pozycjonujemy liczbę, którą odejmujemy i (29.) ją też wypisujemy i przechodzimy do następnej linijki. Kreska też musi być odpowiednio ustawiona. (30.) Wypisujemy odpowiednią ilość spacji i (31.) samą kreskę o długości równej liczbie odejmowanej + 1. (32.) Przechodzimy do następnej linijki.

  1.       countf -= minus;
  2.       coutChar(margin + 1);
  3.       coutChar(intLength(minus) - (countf == 0 ? 0 : intLength(countf)), '=');
  4.       if(countf != 0) cout << countf;

(33.) Od liczby utworzonej z kolejnych cyfr odejmujemy odpowiednią liczbę. (34.) Wynik z linijki 33. będzie mniejszej lub równej długości co minus, więc margines zostawiamy bez zmian. Jeśli liczby różnią się długością to znaczy, że musimy (35.) wypisać, że w danej kolumnie liczby się wyzerowały. (36.) Jeśli wynik odejmowania jest różny od 0 to wynik wypisujemy w przeciwnym wypadku nie, ponieważ = już ją zastąpiły w całości.

  1.       int ac = a, countfc = countf, wynikc = wynik;
  2.       minus = getFirstDigit(wynikc) * b;
  3.       while(minus > countfc){
  4.         countfc *= 10;
  5.         countfc += getFirstDigit(ac);
  6.         cout << countfc % 10;
  7.       }
  8.       cout << endl;
  9.     }

Na sam koniec pętli (37.) Wykonujemy kopie odpowiednich zmiennych. (38.) Wyliczamy również ile będziemy w następnej linijce odejmować, aby (39. - 43.) w tej linijce wypisać odpowiednie cyfry. (44.) Przechodzimy do następnej linijki i rozpoczynamy kolejną iterację.

  1.     cout << "\n";
  2.   }
  3.   system("pause");
  4.   return 0;
  5. }

(46.) Na sam koniec instrukcji if wypisujemy znak końca linii - ma to zabieg czysto kosmetyczny. (48.) Czekamy na interakcję użytkownika i (49.) kończymy wykonywanie programu.