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
 
 

2 responses to “Numere mari

  1. persa claudiu

    08/04/2017 at 07:20

    Buna ziua.
    As vrea sa fac cateva obvervatii cu privire la corectititudinea subprogramelor.
    1. Pentru a se citi, afisa sau parcurge corect testul din for trebuie sa fie i>=0 (nu i>0) ca mai jos
    for (i=n-1; i>=0;i–)
    2. Pentru parametrul n din procedura citire trebuie sa fie folosita referinta
    void citire(nrmare v, int &n)
    3. In multe locuri apar litere mari (probabil ca sunt erori de copiere de text)
    4. Am mai fi si observatii legate de indentarea codului sursa care este din aceasta cauza greu de citit.

     
  2. mchelariu71

    08/04/2017 at 11:31

    Aveti dreptate. Din pacate, WordPress intervine cand inserez text. De aici apar cele mai multe discordante. Asta ma face sa regret alegerea acestei platforme.

     

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: