RSS

Numere mari

13 Jan

sursa: http://ler.is.edu.ro/~cex_is/Informatica/pregatire.html

Numere mari

Necesitatea

In momentul cand unei variabile i se stabileste un tip intreg, limitam valorile pe care le poate avea variabila, la tipul folosit.

Name Description Size* Range*
Char Character or small integer. 1byte signed: -128 to 127
unsigned: 0 to 255
short int (short) Short Integer. 2bytes signed: -32768 to 32767
unsigned: 0 to 65535
int Integer. 4bytes signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295
long int (long) Long integer. 4bytes signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295

 

Ce facem insa daca avem nevoie de numere intregi mai mari decat tipurile existente?

Putem reprezenta numarul intreg ca un vector ce contine sirul de cifre ale numarului.

x=40375 Vectorul asociat va fi

5 7 3 0 4

 

Dupa cum observati, in vector, numarul este scris in ordine inversa, astfel incat sa putem efectua cu usurinta operatiile aritmetice.

Declararea tipului corespunzator unui numar mare poate fi:

Typedef int nrmare[1000];

Citirea unui numar mare.

Putem realiza citirea unui numar mare intr-un sir de caractere pe care il vom transforma in vector de cifre.

void citire(nrmare v, int n)

{int I; char sir[100];

fin.get(sir,100); n=strlen(sir); //sir de caractere

for (i=n-1; i>0;i–) v[n-i-1]=(int) (sir[i]-‘0’); //convertesc caracterul cifra in cifra… numerica

}

Afisarea unui numar mare

void afisare(nrmare v, int n)

{int i;

for(i=n-1;i>0;i–) cout<<v[i];

}

Adunarea a doua numere mari

Presupunem ca avem 2 vectori Asi B, reprezentand numere cu NA, respectiv NB cifre si calculam suma C, dintre A si B.Trebuie sa efectuam operatia de adunare, cifra cu cifra, avand grija de problema depasirii ordinului. De asemenea, trebuie avute in vedere situatiile:

  • Daca valorile nu au acelasi ordin va trebui sa completam numarul mai mic cu zerouri
  • Daca in urma adunarii obtinem depasire de ordin, va trebui sa mai adaugam o cifra la vectorul suma.

Void suma (nrmareA, nrmare B, nr mare C, int NA,int NB, int N)

{Int I, t;

If (NA<NB) {for(i=NA; i<nb; i++) A[i]=0; NA=NB;}

Else {for(i=NB; i<NB; i++) B[i]=0; NB=NA;}

N=NB;t=0;

For(i=0;i<N;i++) {t=A[i]+B[i]+t;C[i]=t %10; t=t/10;}

If(t>0) {N++;C[N-1]=t;}

}

Compararea a doua numere mari

Fie A (cu NA cifre) si B (cu NB cifre) doua numere mari. Vom realiza o functie care va stabili care dintre valorile A si B este mai mare. Functia va returna -1 daca A<B, 0 daca A=B si +1 daca A>B.

Intcompar(nrmare A, nrmare B, int NA, int NB)

{if (NA<NB) return -1; //B estemai mare

if (NB<NA) return +1; //A estemai mare

//suntempecazul NA=NB.

//Cautamceamaisemnificativadiferenta de cifre.

For(i=NA; i>=0 && A[i]==B[i]; i–);

If(i<=0) return 0 ; //numerelesuntidentice

If (A[i]<B[i]) return -1;

else return +1;

}

Diferenta a doua numere mari

Calculam diferenta D dintre A (cu NA cifre) si B  (cu NB cifre). Presupunem ca B este mai mic si are completate spatiile libere cu zerouri.

Void diferenta (nrmare A, nrmare B, nr mare &D, int NA, int NB, int&N)

{IntI,t=0;

For (i=0,i<NA; i++)

{D[i]=A[i]-B[i]+t;

If(D[i]<0) {D[i]=D[i]+10; t=-1;}

Else t=0;

}
while(i>=0 && D[i]==0) i–;

N=I+1;

}

Inmultirea cu un scalar

Fie un numar mare A (cu NA cifre) si un numar natural X. Trebuie sa realizam inmultirea numarului A cu X.

Void scalare(nrmare A, int NA, int X)

{intI,t;

t=0;

for(i=0;i<NA;i++) {t=A[i]*x+t; A[i]=t%10; t=t/10;}

//ramane sa completam cu cifrele lui t, in masura in care mai exista

While (t>0) {NA++; A[NA-1]=t%10; t=t/10;}

}

Inmultirea a doua numere mari

Fie A si B doua numere mari. Dorim sa realizam produsul P intre A si B. Practic este vorba de o inmultire succesiva a  numarului mare A cu salarul B[i]. De observat ca pozitia in care incepem sa completam P este tot i.

Void produs(nrmare A, nrmare B, nrmare P, int NA, int NB, int NP)

{int I, j, t;

For (i=0;i<NB;i++)

{//produsul intre A si scalarul B[i]

t=0;

for(j=0;j<NA;j++)

{t=t+A[j]*B[i]+p[i+j];

p[i+j]=t%10;

t=t/10;}

if (t>0) p[i+j]=t;

}

NP=NA+NB+1;

}

Impartirea a doua numere mari

Fie A (cu NA cifre) si B (cu NB cifre). Vrem sa realizam impartirea lui A la B. Folosim observatia conform careia impartirea este o scadere repetata.

 

Void impartire(nrmare&A, nrmare B, nrmare C, int&NA, int NB, int&NC)

{NrmareD;

IntNC,I,ND;

NC=0;ND=0;

For(i=0;i<900;i++) c[i]=0;

While (compar(A,B,NA,NB)>0)

{//fac diferenta si o memorez tot in A

Diferenta(A,B,D,NA,NB,ND);

For(i=0;i<ND;i++) A[i]=D[i];

//incrementez catul C

t=1;

For(i=0;t!=0;i++)

{t=t+c[i];

c[i]=t%10;

t=t/10;

}

NC=i+1;

}

Afisare(A,NA);

Afisare(C,NC);

}

 

Problemepropuse:

  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=438
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=74
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=258
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=432
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=500
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: