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

©2024 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:

s1,s2 : dodawane łańcuchy z cyframi.

Wyjście:

s3 : ł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 s1s2; i,j ∈ C.
k : licznik pętli; k ∈ C.
n : długość krótszego z łańcuchów s1s2; n ∈ C.
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: n ← i ; 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: ; przebiegamy wstecz przez cyfry łańcuchów
     wykonuj kroki K08…K12
K08:   w ← kod(s1[i])+kod(s2[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:   s3 ← znak((w mod 10)+48)+s3 ; cyfrę sumy dołączamy do wyniku
K13: Dopóki i > 0: ; jeśli w s1 pozostały cyfry
     wykonuj kroki K14…K17
K14:   w ← kod(s1[i])+p-48 ; to dodajemy do nich tylko przeniesienia
K15:   i ← i-1
K16:   p ← w div 10
K17:   s3 ← znak((w mod 10)+48)+s13
K18: Dopóki j > 0: ; to samo dla s2
     wykonuj kroki K19…K22
K19:   w ← kod(s2[j])+p-48;
K20:   j ← j-1
K21:   p ← w div 10
K22:   s3 ← znak((w mod 10)+48)+s3
K23: Jeśli p > 0, ; jeśli jest przeniesienie, to jest ono
     to s3 ← znak(p+48)+s3 ; pierwszą cyfrą wyniku
K24: Jeśli s3 = "", ; jeśli wynik nie zawiera cyfr,
     to s3"0"    ; to s1 i s2 były puste.
K25: Zakończ ; wynik dodawania w s3

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
Python (dodatek)
# Dodawanie dużych liczb
# Data: 30.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# odczytujemy liczby do dodawania

s1 = int(input("L1 = "))
s2 = int(input("L2 = "))

# obliczamy sumę

s3 = s1 + s2

# wyświetlamy wynik

print("   =",s3)
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
©2024 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.