Dodawanie dużych liczb


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie

 

Problem

Dodać do siebie dwie dowolnie duże, dodatnie liczby całkowite, przedstawione w postaci łańcucha cyfr.

 

 

Problem rozwiążemy w sposób szkolny (profesjonalne algorytmy wymagają innego podejścia). Dodawane liczby musimy wyrównać do ostatnich cyfr:

 

21638626396236623668969866232198
95832808595775579737342988203408934789797363

 

Dodawanie rozpoczniemy od ostatnich cyfr łańcuchów. Stosujemy przy tym poznane w szkole podstawowej zasady dodawania dwóch liczb. Dodajemy ostatnie cyfry. W łańcuchu wynikowym umieszczamy ostatnią cyfrę wyniku. Natomiast pierwsza cyfra wyniku staje się przeniesieniem do następnej pozycji:

 

10
21638626396236623668969866232198
+ 95832808595775579737342988203408934789797363
1

 

W następnym kroku dodajemy do siebie dwie kolejne cyfry oraz przeniesienie. Do łańcucha wynikowego wpisujemy na przedostatniej pozycji ostatnią cyfrę wyniku, a pierwsza cyfra wyniku staje się przeniesieniem na dalszą pozycję.

 

100
21638626396236623668969866232198
+ 95832808595775579737342988203408934789797363
61

 

Jeśli w jednym z łańcuchów skończą się zbyt wcześnie cyfry, to przyjmujemy, że posiada on resztę cyfr równych 0. Sprowadza się to wtedy do dodawania przeniesień do pozostałych cyfr drugiego łańcucha. Gdy wszystkie cyfry zostaną przetworzone, a przeniesienie ma wartość większą od 0, to umieszczamy je na początku łańcucha wynikowego jako pierwszą cyfrę wyniku.

Przy dodawaniu cyfr musimy pamiętać, że są one przechowywane w łańcuchach w postaci kodów ASCII:

 

Cyfra Kod ASCII
0 48
1 49
2 50
3 51
4 52
5 53
6 54
7 55
8 56
9 57

 

Dlatego w celu otrzymania wartości cyfry należy od jej kodu odjąć 48, a przy otrzymywaniu kodu znaku z wartości cyfry należy do niej dodać 48.

 

Algorytm dodawania dwóch dowolnie dużych, nieujemnych liczb całkowitych

Wejście:
s1,s2    dodawane łańcuchy z cyframi
Wyjście:

s3 – łańcuch wynikowy, który zawiera cyfry sumy

Elementy pomocnicze:
p    przeniesienie z poprzedniej pozycji, p Z
w  – wynik dodawania, w N
i,j  – indeksy w łańcuchach s1 i s2, i,j Z
k  – licznik pętli, k Z
n  – długość krótszego z łańcuchów s1 i s2, n  Z
kod(x)  – zwraca kod znaku x
znak(x)  – zamienia kod x na odpowiadający mu znak ASCII
Lista kroków:
K01: i ←  |s1| ; wyznaczamy długości łańcuchów
K02: j ← |s2|  
K03: ni ; w n wyznaczamy długość krótszego z łańcuchów
K04: Jeśli j < i, to nj  
K05: p ← 0 ; zerujemy przeniesienie
K06: s3 ← "" ; zerujemy łańcuch wyniku s3
K07: Dla k = 1,2,...n: wykonuj K08...K12 ; przebiegamy wstecz przez cyfry łańcuchów
K08:     w ← kod(s1[i]) + kod(s2[j]) + p - 96 ; obliczamy sumę cyfr i przeniesienia. 96 = 2 x 48
K09:     ii - 1 ; cofamy indeksy o 1 pozycję dla kolejnego obiegu
K10:     jj - 1  
K11:     pw div 10 ; obliczamy przeniesienie do następnej pozycji
K12:     s3 ← znak((w mod 10) + 48) + s3 ; cyfrę sumy dołączamy do wyniku
K13: Dopóki i > 0 wykonuj K14...K17 ; jeśli w s1 pozostały cyfry
K14:     w ← kod(s1[i]) + p - 48 ; to dodajemy do nich tylko przeniesienia
K15:     ii - 1  
K16:     pw div 10  
K17:     s3 ← znak((w mod 10) + 48) + s3  
K18 Dopóki j > 0 wykonuj K19...K22 ; to samo dla s2
K19:     w ← kod(s2[j]) + p - 48;  
K20:     jj - 1  
K21:     pw div 10  
K22:     s3 ← znak((w mod 10) + 48) + s3  
K23 Jeśli p > 0, to s3 ← znak(p + 48) + s3 ; jeśli jest przeniesienie, to jest ono pierwszą cyfrą wyniku
K24: Jeśli s3 = "", to s3 = "0" ; jeśli wynik nie zawiera cyfr, to s1 i s2 były puste.
K25: Zakończ ; wynik dodawania w s3

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje dwie liczby o dowolnej ilości cyfr, dodaje je i wyświetla wynik. Program nie sprawdza poprawności wprowadzonych liczb.

 

Lazarus
// Dodawanie dużych liczb
// Data: 07.10.2012
// (C)2012 mgr Jerzy Wałaszek
//---------------------------------------

program sumbignums;

var

 s1,s2,s3    : ansistring;
 p,w,i,j,k,n : integer;

begin

  // odczytujemy liczby do dodawania

  readln(s1);
  readln(s2);

  // obliczamy długości każdego z łańcuchów

  i := length(s1);
  j := length(s2);

  // w n wyznaczamy długość najkrótszego łańcucha

  n := i; if j < i then n := j;

  // zerujemy przeniesienie oraz łańcuch wynikowy

  p := 0;

  s3 := '';

  // sumujemy kolejne od końca cyfry obu łańcuchów

  for k := 1 to n do
  begin
    w  := ord(s1[i]) + ord(s2[j]) + p - 96;
    dec(i); dec(j);
    p  := w div 10;
    s3 := chr((w mod 10) + 48) + s3;
  end;

  // jeśli łańcuch s1 ma jeszcze cyfry, to dodajemy do nich
  // przeniesienia i umieszczamy w łańcuchu wynikowym

  while i > 0 do
  begin
    w  := ord(s1[i]) + p - 48;
    dec(i);
    p  := w div 10;
    s3 := chr((w mod 10) + 48) + s3;
  end;

  // jeśli łańcuch s2 ma jeszcze cyfry, to dodajemy do nich
  // przeniesienia i umieszczamy w łańcuchu wynikowym

  while j > 0 do
  begin
    w  := ord(s2[j]) + p - 48;
    dec(j);
    p  := w div 10;
    s3 := chr((w mod 10) + 48) + s3;
  end;

  // jeśli pozostało przeniesienie, to dołączamy je do cyfr
  // w łańcuchu wynikowym

  if p > 0 then s3 := chr(p + 48) + s3;

  // jeśli w s3 nie ma cyfr, to wpisujemy tam 0

  if s3 = '' then s3 := '0';

  // wyświetlamy wynik

  writeln(s3);

end.
Code::Blocks
// Dodawanie dużych liczb
// Data: 07.10.2012
// (C)2012 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s1,s2,s3;
  int p,w,i,j,k,n;

  // odczytujemy liczby do dodawania

  cin >> s1 >> s2;

  // obliczamy długości każdego z łańcuchów

  i = s1.length();
  j = s2.length();

  // w n wyznaczamy długość najkrótszego łańcucha

  n = i; if(j < i) n = j;

  // zerujemy przeniesienie oraz łańcuch wynikowy

  p = 0;

  s3 = "";

  // sumujemy kolejne od końca cyfry obu łańcuchów

  for(k = 1; k <= n; k++)
  {
    w  = (int)(s1[--i]) + (int)(s2[--j]) + p - 96;
    p  = w / 10;
    s3 = (char)((w % 10) + 48) + s3;
  }

  // jeśli łańcuch s1 ma jeszcze cyfry, to dodajemy do nich
  // przeniesienia i umieszczamy w łańcuchu wynikowym

  while(i)
  {
    w  = s1[--i] + p - 48;
    p  = w / 10;
    s3 = (char)((w % 10) + 48) + s3;
  }

  // jeśli łańcuch s2 ma jeszcze cyfry, to dodajemy do nich
  // przeniesienia i umieszczamy w łańcuchu wynikowym

  while(j)
  {
    w  = s2[--j] + p - 48;
    p  = w / 10;
    s3 = (char)((w % 10) + 48) + s3;
  }

  // jeśli pozostało przeniesienie, to dołączamy je do cyfr
  // w łańcuchu wynikowym

  if(p) s3 = (char)(p + 48) + s3;

  // jeśli w s3 nie ma cyfr, to wpisujemy tam 0

  if(s3 == "") s3 = "0";

  // wyświetlamy wynik

  cout << s3 << endl;

}
Free Basic
' Dodawanie dużych liczb
' Data: 07.10.2012
' (C)2012 mgr Jerzy Wałaszek
'---------------------------------------

Dim As string s1,s2,s3
Dim As Integer p,w,i,j,k,n

' odczytujemy liczby do dodawania

Line Input s1
Line Input s2

' obliczamy długości każdego z łańcuchów

i = Len(s1)
j = Len(s2)

' w n wyznaczamy długość najkrótszego łańcucha

n = i: If j < i Then n = j

' zerujemy przeniesienie oraz łańcuch wynikowy

p = 0

s3 = ""

' sumujemy kolejne od końca cyfry obu łańcuchów

For k = 1 To n
  w  = Asc(Mid(s1,i,1)) + Asc(Mid(s2,j,1)) + p - 96
  i -= 1: j -= 1
  p  = w \ 10
  s3 = Chr((w Mod 10) + 48) + s3
Next

' jeśli łańcuch s1 ma jeszcze cyfry, to dodajemy do nich
' przeniesienia i umieszczamy w łańcuchu wynikowym

While i > 0
  w  = Asc(Mid(s1,i,1)) + p - 48
  i -= 1
  p  = w \ 10
  s3 = Chr((w Mod 10) + 48) + s3
Wend

' jeśli łańcuch s2 ma jeszcze cyfry, to dodajemy do nich
' przeniesienia i umieszczamy w łańcuchu wynikowym

While j > 0
  w  = Asc(Mid(s2,j,1)) + p - 48
  j -= 1
  p  = w \ 10
  s3 = Chr((w Mod 10) + 48) + s3
Wend

' jeśli pozostało przeniesienie, to dołączamy je do cyfr
' w łańcuchu wynikowym

If p > 0 Then s3 = Chr(p + 48) + s3

' jeśli w s3 nie ma cyfr, to wpisujemy tam 0

If s3 = "" Then s3 = "0"

' wyświetlamy wynik

Print s3

End
Wynik
481084081308409834234234008219934109784217102740921707907072414421
892719749217498721847921749827210740217402147210740210472107402149
1373803830525908556082155758047144850001619249951661918379179816570

 

Dodawanie dużych liczb dodatnich
(C)2012 mgr Jerzy Wałaszek

Zadanie

Powyższy algorytm nie usuwa zer wiodących. Suma 0001 i 2 da wynik 0003. Zastanów się, jak usunąć z wyniku te zera wiodące. W którym miejscu algorytmu najlepiej to zrobić?

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.