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 . W przypadku wykonywania działań na liczbach naturalnych i usunięciu liczb ujemnych zakres zmienia się na . 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:

1
2
3
4
5
6
7

int main() {
    long long int a, b;
    cin >> a >> b;
    cout << (a + b) << endl;
    system("pause");
    return 0;
}

1
2
3
4
5
6
7

        static void Main(string[] args) {
            long a, b;
            a = Convert.ToInt64(Console.ReadLine());
            b = Convert.ToInt64(Console.ReadLine());
            Console.WriteLine(a + b);
            Console.ReadKey();
        }

Jednak co w przypadku, gdy taki zakres nie jest 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:

1

string znakiCyfry = "0123456789ABCDEFGHIJKLMNOPQRSTUWXYZ";

1

        static 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 .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

string dodaj(string a, string b, int base = 10) {
    string w = "";
    int i = 0;
    int t = 0;
    while (i < a.length() || i < b.length()) {
        t += pobierzZnak(a, i) + pobierzZnak(b, i);
        w = znakiCyfry[t % base] + w;
        t /= base;
        i++;
    }
    if (t != 0)
        w = znakiCyfry[t] + w;
    return w;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

        static string dodaj(string a, string b, int ab_base = 10) {
            string w = "";
            int i = 0;
            int t = 0;
            while (i < a.Length || i < b.Length) {
                t += pobierzZnak(a, i) + pobierzZnak(b, i);
                w = znakiCyfry[t % ab_base] + w;
                t /= ab_base;
                i++;
            }
            if (t != 0)
                w = znakiCyfry[t] + w;
            return w;
        }

(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.

1
2
3
4
5

int pobierzZnak(string a, int i) {
    if (i < a.length())
        return znakiCyfry.find(a[a.length() - i - 1]);
    return 0;
}

1
2
3
4
5

        static int pobierzZnak(string a, int i) {
            if (i < a.Length)
                return znakiCyfry.IndexOf(a[a.Length - i - 1]);
            return 0;
        }

(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.

1
2
3
4
5
6
7
8
9

int main() {
    string a, b;
    int base;
    cout << "Podaj liczby oraz system:\n";
    cin >> a >> b >> base;
    cout << dodaj(a, b, base) << endl;
    system("pause");
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

        static void Main(string[] args) {
            string a, b;
            int ab_base;
            Console.WriteLine("Podaj liczby oraz system:");
            a = Console.ReadLine();
            b = Console.ReadLine();
            ab_base = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine(dodaj(a, b, ab_base));
            Console.ReadKey();
        }

Przykład

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

• Kod źródłowy Implementacja
• Kod źródłowy Implementacja