Puterm reprezenta, in conformitate cu tipurile de baza
din limbajul C, numere intregi pozitive de la 0 la 2^32 - 1 sau numere intregi
cu semn in domeniul: -2^31, +2^31 - 1.
Intrucat limbajul nu impune restrictii (dar sistemul de operare si compilatorul pot
impune restrictii!) asupra dimensiunii tablourilor de intregi (== asupra memoriei alocate static), putem
imagina un sistem de citire si afisare a numerelor intergi lungi de o
dimensiune convenabila utilizatorului, fiind, de asemenea, posibila si
simularea operatiilor aritmetice cu astfel de numere.
Desigur, trebuie tinut cont de mecanismul de transport:
daca doua cifre situate pe pozitii corespunzatoare dau, adunate, un rezultat
mai mare decat valoarea bazei de reprezentare, in cazul de fata 10, trebuie
adunat 1 (== valoarea transportului) la rezultatul adunarii cifrelor de pe
urmatoarea pozitie si, de asemenea, verificat iar rezultatul prin comparatie cu
baza etc.
Este clasicul algoritm invatat in clasa a 2-aJ
In cazul intregilor lungi, exemplul urmator foloseste
vectori de lungime prestabilita, 31 de digiti, pentru a stoca cifrele
numerelor.
Este folosita functia gets() pentru citirea, ca sir de caractere, a
cifrelor numarului. Intrucat o pozitie este rezervata terminatorului de sir
'\0' necesar manipularii sirurilor de caractere, raman 30 de pozitii utile in
care pot fi memorate cifrele numerelor (sau coeficientii puterilor bazei 10).
Apare,
insa, o problema: functia gets() plaseaza cifra corespunzatoare celui mai mare
ordin pe pozitia 0 in sirul de caractere. Pe pozitia 1 este plasata cifra
corespunzatoare ordinului imediat urmator etc.
La
siruri de lungime diferita, ultima cifra, corespunzatoare ordinului unitatilor,
va ocupa pozitii de index diferit in tablourile dedicate stocarii celor doua
numere lungi:
Daca char a[31] si char b[31] sunt cele doua tablouri,
pentru valorile intregi 19781 si 999 vom avea urmatoarea alocare a cifrelor.
/*
index 0 1
2 3 4 5 6…
char a '1' '9' '7' '8' '1' '\0' '\0'…
char b '9' '9' '9' '\0' '\0' '\0' '\0'…
*/
Pentru a putea lucra cu aceste tablouri, o idee practica
a ar fi sa "aliniem" elementele din tablou, astfel incat pe pozitii
corespunzatoare diverselor ordine sa se afle coeficientii corespunzatori (de
pilda, in a[31] si b[31] sa se stocheze coeficientii unitatilor, in a[30] si
b[30], coeficientii zecilor etc.
In acest sens, se va defini o functie void AliniereDreapta(char a[]) care,
luand ca parametru un tablou in care sunt stocate cifrele intregului lung, va
permuta o pozitie la dreapta aceste cifre atat timp cat valoarea permutata este
nula (== terminatorul de sir '\0', cod ASCII 0).
Ramane, bineinteles, de definit o functie de afisare
corecta, corespunzatoare intentiilor utilizatorului, pentru numerele astfel
stocate in tablou (va itera prin tot tabloul, de la index 0 la index 31 si va
afisa ca si caractere, nu ca
intregi, valorile numerelor stocate in elementele de indecsi corespunzatori.
Trebuie sa ne reamintim ca am "citit" intregii lungi drept siruri de
caractere si in elementele a[i], b[i] se afla codurile ASCII ale acestor
caractere).
De asemenea, trebuie definita functia de adunare, dupa
urmatorul algoritm:
- fie cei doi vectori a[i], b[i], "aliniati" cu
functia AliniereDreapta;
- se itereaza de la 31 la 0 inclusiv. Daca a[i] este
nenul (a[i] != '\0') atunci, daca si
b[i] este nenul, cifra de index [i + 1] a rezultatului se deduce astfel:
c[i + 1] = 48 + (a[i] + b[i] - 2*48 + t) % 10;
Vectorul- rezultat c are dimensiunea 32 pentru a acoperi
si cazurile eventualelor depasiri, de ex:
9999
+
9999
=
19998
Trebuie verificat trasportul t (initial este zero). Daca a[i]
+ b[i] - 2*48 + t >= 10, urmatoarea valoare a transportului este 1 (t = 1)
Daca
a[i] e nenul si b[i] este nul, atunci c[i + 1] = 48 +
(a[i] - 48 + t) % 10.
Trebuie verificat, de asemenea, transportul la depasire.
Daca, dimpotriva, a[i]
== '\0', atunci daca b[i] != '\0' ne regasim intr-un caz similar celui
anterior, cu c[i + 1] = 48 + (b[i] - 48
+ t) % 10.
Daca si a[i] ==
'\0' si b[i] == '\0' atunci daca t == 1, c[i + 1] = 48 + t.
Altfel, c[i + 1] ramane cu valoarea rezultata in urma aplicarii functiei de aliniere, adica '\0'.
Altfel, c[i + 1] ramane cu valoarea rezultata in urma aplicarii functiei de aliniere, adica '\0'.
Evident,
tinand cont de tot acest rationament, se poate imagina si o functie pentru
scadere, e.g. daca a[i] - b[i] < 0, atunci c[i + 1] = 48 + (a[i] - b[i] -
2*48 + 10 + t) iar valoarea urmatoare a transportului t = -1 etc.
Codul si printscreen-ul executiei:
// Adunarea intregilor lungi
#include <stdio.h>
void AliniereDreapta(char a[])
{
int i; char
temp;
while(a[30] ==
'\0')
{
temp =
a[30];
for(i = 30;
0 < i; i--) a[i] = a[i - 1];
a[0] = temp;
}
}
void Display(char a[], int dim)
{
int i;
for (i = 0; i
< dim; i++) printf("%c ", a[i]);
printf("\n");
}
void Add(char a[], char b[], char c[])
{
int i, t =0;
for(i = 30; i
>= 0; i--)
{
if(a[i]
!= '\0')
{
if(
b[i] != '\0')
{
c[i + 1] = 48 + (a[i] + b[i] - 96 + t)%10;
if((a[i] + b[i] - 96 + t) >= 10 ) t = 1;
else t = 0;
}
else
{
c[i + 1] = 48 + (a[i] + t - 48)%10;
if(a[i] + t - 48 >= 10 ) t = 1;
else t = 0;
}
}
else
if(b[i] != '\0')
{
c[i
+ 1] = 48 + (b[i] - 48 + t)%10;
if(b[i] - 48 + t >= 10) t = 1;
else t = 0;
}
else
{
if(t) c[i + 1] = 48 + t;
t =
0;
}
}
if(t != 0
&& (a[0] != '\0' || b[0] != '\0')) c[0] = 49; // codul ASCII pentru '1'
}
int main()
{
char a[31] =
{'\0'};
char b[31] =
{'\0'};
char c[32] =
{'\0'}; // pentru rezultat se suplimenteaza dimensiunea cu 1, pentru a lua in
calcul depasirea la transport
int k;
puts("Introduceti numere de max 30 de cifre. Primul:");
gets(a);
puts("Al
doilea:");
gets(b);
puts("Vom
afisa numerele cu functia Display.");
Display(a, 31);
Display(b, 31);
puts("Vom
alinia numerele la dreapta si le vom afisa din nou.");
AliniereDreapta(a);
AliniereDreapta(b);
Display(a, 31);
Display(b, 31);
puts("Vom
efectua adunarea lui a cu b.");
Add(a, b, c);
printf("%c
", ' ');
Display(a, 31);
for(k = 0; k
< 63; k++)printf("%c", ' ');
printf("%c\n", '+');
printf("%c
", ' ');
Display(b, 31);
for(k = 0; k
< 63; k++)printf("%c", ' ');
printf("%c\n", '=');
Display(c, 32);
return 0;
}
No comments:
Post a Comment