Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

Dodawanie dużych liczb

SPIS TREŚCI

Problem

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

Rozwiązanie

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:

                                            1
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ę.

                                           1
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:

s 1, s 2  –  dodawane łańcuchy z cyframi

Wyjście:

s 3  –  łańcuch wynikowy, który zawiera cyfry sumy
Zmienne pomocnicze:
p  –  przeniesienie z poprzedniej pozycji, p  ∈ C
w  – wynik dodawania, w  ∈ N
i, j  – indeksy w łańcuchach s 1 i s 2, i, j  ∈ C
k  – licznik pętli, k  ∈ C
n  – długość krótszego z łańcuchów s 1 i s 2, n  ∈ C
kod ( x  )  – zwraca kod znaku x
znak ( x  )  – zamienia kod x na odpowiadający mu znak ASCII

Lista kroków:

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

Przykładowe programy

Uwaga:

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.
Pascal
// Dodawanie dużych liczb
// Data: 07.10.2012
// (C)2020 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.
C++
// Dodawanie dużych liczb
// Data: 07.10.2012
// (C)2020 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;

}
Basic
' Dodawanie dużych liczb
' Data: 07.10.2012
' (C)2020 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)2020 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ć?
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.