Strona główna » Algorytmy » Artykuły » Dodawanie bardzo dużych liczb
999..9999

Dodawanie bardzo dużych liczb

Cel

Obecnie przekroczenie limitu na zwykłym kalkulatorze w systemie jest bardzo trudne. Rozwój technologii spowodował zwiększenie dostępnych zasobów. Co za tym idzie deweloper może śmiało używać zmiennej long long int, która zajmuje 8 bajtów.

Zmienna tego typu może przechować liczbę z zakresu [-232, 232 - 1]. W przypadku wykonywania działań na liczbach naturalnych i usunięciu liczb ujemnych zakres zmienia się na [0, 264 - 1]. Wystarczy taką liczbę wyliczyć i spróbować odczytać, aby zdać sobie sprawę jak ogromny ten zakres jest: 18 446 744 073 709 551 615 (słownie: 18 trylionów 446 biliardów 744 biliony 73 miliardy 709 milionów 551 tysięcy 615). Innymi słowy wystarczy prosty kod, aby użytkownik mógł dodawać "dowolne" liczby:

C++
C#
  1. int main() {
  2.   long long int a, b;
  3.   cin >> a >> b;
  4.   cout << ( a + b ) << endl;
  5.   system("pause");
  6.   return 0;
  7. }

Jednak co w przypadku, gdy taki zakres jest nie wystarczający ?

Implementacja

Opis

Jednym z mało efektywnych, ale wystarczających metod, które pozwalają na uzyskanie większego zakresu jest przechowywanie liczby w postaci tekstu. Wtedy pamięć nie jest wykorzystana w 100%, dlatego takiego rozwiązania nie znajdzie się w profesjonalnych rozwiązaniach informatycznych.

Rozpoznawanie cyfr

W celu rozpoznania i-tej cyfry zadeklarowana zostaje zmienna znakiCyfry, która przechowuje wszystkie rozpoznawane cyfry:

C++
C#
  1. string znakiCyfry = "0123456789ABCDEFGHIJKLMNOPQRSTUWXYZ";

Cyfra na j-tej pozycji ma wartość j w systemie dziesiętnym.

Dodawanie

W przypadku wykorzystania zmiennej string będzie można przechować 4 294 967 291 znaków czyli tyle samo cyfr. Funkcja dodaj() będzie przyjmowała dwa argumenty a i b - liczby do dodania. Argument base jest opcjonalny i pozwala określić w jakim systemie jest zapisana liczba a i b. Zarówna liczby podane w argumencie jak i zwracana liczba będą przechowywane w zmiennej string.

C++
C#
  1. string dodaj(string a, string b, int base = 10){
  2.   string w = "";
  3.   int i = 0;
  4.   int t = 0;
  5.   while(i < a.length() || i < b.length()){
  6.     t += pobierzZnak(a, i) + pobierzZnak(b, i);
  7.     w = znakiCyfry[t % base]+w;
  8.     t /= base;
  9.     i++;
  10.   }
  11.   if(t != 0)
  12.     w = znakiCyfry[t] + w;
  13.   return w;
  14. }

(2.) Utwórz zmienną wynikową. Zadeklaruj zmienne pomocnicze (3.) i - będzie kontrolować, która cyfra jest dodawana oraz (4.) t - będzie przechowywać wartość przenoszoną do dalszych cyfr. (5.) Dopóki w chociaż jednej liczbie jest jeszcze cyfra to: (6.) dodaj cyfry do wartości przenoszonej. Następnie (7.) oblicz cyfrę i ją dopisz do wyniku. (8.) Usuń ostatnią cyfrę z wartości przenoszonej i (9.) przejdź do dodawania następnej liczby. (10.) Po dodaniu wszystkich liczb należy się upewnić, że zmienna t ma wartość 0. Jeśli nie to (11.) należy dopisać dodatkową cyfrę, a następnie (12.) zwrócić wynik.

Wybieranie cyfr

W procesie pobierania cyfr wykorzystywana jest funkcja pobierzZnak(). Przyjmuje ona dwa argumenty: a - liczbę zapisaną jako słowo oraz i - indeks cyfry do pobrania od prawej strony.

C++
C#
  1. int pobierzZnak(string a, int i){
  2.   if(i < a.length())
  3.     return znakiCyfry.find( a[a.length() - i - 1] );
  4.   return 0;
  5. }

(2.) Jeśli i-ta cyfra istnieje to (3.) zwróć jej wartość zgodnie z pozycją w zmiennej znakiCyfry. (4.) Jeśli jednak taka cyfra nie istnieje to należy zwrócić 0. (Przed liczbą w dowolnym systemie można dostawić dowolną ilość zer.)

Testowanie funkcji

W celu przetestowania funkcji dodaj() należy zmienić funkcję main() tak, aby wczytywane liczby były wczytane jako tekst.

C++
C#
  1. int main() {
  2.   string a, b;
  3.   int base;
  4.   cout << "Podaj liczby oraz system:\n";
  5.   cin >> a >> b >> base;
  6.   cout << dodaj(a, b, base) << endl;
  7.   system("pause");
  8.   return 0;
  9. }

Przykład

Przykładowo dodając dwie liczby 34F oraz 623 w systemie szesnastkowym program wypisze na ekran:

  1. 972