Articole

Considerăm următoarea problemă: Se dau două șiruri de cifre zecimale. Să se determine cifrele comune, în ordine crescătoare.

În funcție de numărul de cifre din cele două șiruri, putem realiza diverse soluții:

• căutăm fiecare termen din primul șir în al doilea șir. Șirul cu valorile comune va trebui sortat.
• dacă șirurile sunt sortate (sau le sortăm) procedăm ca mai sus, dar căutăm binar. Șirul cu valorile comune este de la început sortat.
• dacă șirurile sunt sortate (sau le sortăm) putem folosi interclasarea pentru a afla elementele comune.

Vector caracteristic

Nicio soluție dintre cele de mai sus nu ține cont de o proprietate a valorilor din șir – că sunt cifre, adică între 0 și 9. Putem proceda astfel:

• pentru fiecare șir vom folosi un vector cu doar 10 elemente, indexate de la 0 la 9; fie acestea v[] și u[];
• indicii elementelor din șir reprezintă cifrele – valorile posibile ale elementelor din șir;
• inițial elementele celor doi vectori sunt 0;
• pentru fiecare valoare x (care este cifră) care apare în primul șir vom marca în vectorul v[] elementul corespunzător cu 1, v[x] = 1;
• similar, fiecare element y din al doilea șir va fi marcat în vectorul u[] cu 1, u[y] = 1;
• la final sunt comune cifrele c (de la 0 la 9) care sunt marcate cu 1 atât în vectorul v[], cât și în vectorul u[].

Cei doi vectori v[] și u[] sunt vectori caracteristici. Elementele lor caracterizează cifrele dintre 0 și 9, stabilind despre fiecare cifră dacă face sau nu parte din șirul corespunzător.

Observăm că nu trebuie memorate elementele celor două șiruri date. Ne interesează numai valorile distincte care apar în fiecare șir, indiferent de ordinea în care apar.

Exemplu:

Observații:

• vectorul caracteristic are dimensiune constantă – egală cu numărul de valori pe care le caracterizează;
• elementele vectorului caracteristic sunt 0 sau 1 (echivalent cu Adevărat și Fals); valorile din vectorul caracteristic NU sunt valorile date;
• valorile date se află printre indicii vectorului caracteristic, respectiv indicii corespunzători elementelor egale cu 1;

Când folosim vectorul caracteristic?

Pentru a putea folosi un vector caracteristic trebui îndeplinite (cel puțin) următoarele condiții:

• ordinea datelor de intrare nu contează
• datele de intrare au valori mici, sunt numere naturale dintr-un interval de forma [0,M] sau pot fi echivalente cu astfel de numere
• practic, putem folosi un vector caracteristic dacă memoria disponibilă permite declararea unui vector cu un număr de elemente corespunzător:
  • dacă datele de intrare sunt din intervalul [0, 1000] sau [0,10000] putem folosi un vector caracteristic
  • dacă datele de intrare sunt din intervalul [0, 1 milion] putem folosi un vector caracteristic – deși poate există metodă mai bună
  • dacă datele de intrare sunt din intervalul [0, 1 miliard] NU putem folosi un vector caracteristic

Vector de frecvență

Să considerăm din nou un șir de cifre zecimale. Să se determine cifra care apare de cele mai multe ori. Dacă sunt mai multe cifre care apar de număr maxim de ori, să se determine cea mai mică (sau cea mai mare, sau toate, etc.).

De această dată nu putem folosi un vector caracteristic, dar putem folosi un vector de frecvență, adică un vector cu același număr de elemente ca numărul posibil de valori distincte din șirul dat (adică 10), cu semnificația: v[c] = numărul de apariții ale cifrei c în șirul dat.

După construirea acestui vector, valoarea maximă din el va reprezenta numărul maxim de apariții ale unei cifre, iar indicii pentru care elementul corespunzător are valoare maximă reprezintă cifrele care apar de număr maxim de ori.

Exemplu:

Considerăm un tabloul cu elemente numerice. În unele probleme se cere să determinăm rapid suma elementelor din anumite secvențe date. Desigur, o soluție este parcurgerea tuturor elementelor din secvență și determinarea sumei, dar această operație are complexitatea \( O(n) \), iar dacă numărul de sume care trebuie calculate este mare soluția poate fi inacceptabilă.

În asemenea situații putem folosi sumele parțiale.

Reamintim că se numește secvență a vectorului X o succesiune de elemente consecutive din X, în ordinea din X. Mai multe detalii sunt disponibile aici.

Sume parțiale în vectori

Fie un vector X[] cu n elemente. Pentru simplitate vom considera că elementele sunt indexate de la 1 la n.

Să determinăm suma elementelor din secvența determinată de indicii 4 7:

Valoarea sumei este X[4] + X[5] + X[6] + X[7] = 8 + 1 + 3 + 0 = 12.

Pentru a determina rapid această sumă, vom construi un vector auxiliar, \( S[] \), cu următoarea semnificație: \( S[i]=X[1]+X[2]+...+X[i] \). Acest vector se construiește în timp liniar, folosind următoarea relație de recurență:

$$ S[i] = \begin{cases}
0& \text{dacă } i = 0,\\
S[i-1] + X[i] & \text{dacă } i > 0.
\end{cases} $$

pentru a determina suma elementelor din secvența determinată de indicii i j folosim următoarea formulă, în timp constant:

$$ X[i] + X[i+1] + ... + X[j] = S[j] - S[i-1] $$

Astfel:
$$ \begin{split} X[4] + X[5] + X[6] + X[7] & = S[7] - S[3] \\ & = 28 - 16 \\ & = 12 \end{split} $$

Observație: Este posibil ca suma elementelor din vectorul X[] să depășească limita maximă a tipului de date folosit (ex. int), ceea ce duce la overflow. În acest caz, vectorul S[] trebuie declarat de un tip mai larg (ex. long long int).

Secvență C++

int n, X[100001], S[100001];
//citire n, X[]

S[0] = 0;

for(int i = 1 ; i <= n ; i ++)
    S[i] = S[i-1] + X[i];

int st, dr; // capetele secvenței
//citire st,dr

cout << S[dr] - S[st-1];

Sume parțiale în matrice

Observațiile de mai sus pot fi extinse pentru a calcula suma elementelor dintr-o submatrice a unei matrice date A[][], cu n linii și m coloane:

Pentru matricea de mai sus, să calculăm suma elementelor din submatricea cu colțul stânga-sus la coordonatele (2,3) și colțul dreapta-jos la coordonatele (3,5). La fel ca în cazul vectorilor, considerăm, pentru simplitate, că liniile și coloanele matricei sunt indexate de la 1.

Parcurgerea element cu element a submatricei are complexitate \( O(n \cdot m) \). Pentru o complexitate constantă considerăm matricea S[][] a sumelor parțiale, astfel:

• S[i][j] – suma elementelor din submatricea cu colțul stânga-sus la coordonatele (1,1) și colțul dreapta-jos la coordonatele (i,j). Elementele de pe linia 0 și coloana 0 vor avea valoarea 0:

Odată construită această matrice, pentru determinarea sumei elementelor din submatricea cu colțul stânga-sus la coordonatele (is,js) și colțul dreapta-jos la coordonatele (ij,jj) vom folosi următoarea formulă:

• Suma(is,js,ij,jj) = S[ij][jj] - S[is-1][jj] - S[ij][js-1] + S[is-1][js-1]

Matricea S[][] se construiește similar cu modul în care se determină suma din submatrice:

$$ S[i][j] = \begin{cases}
0& \text{dacă } i = 0 \text{ sau } j = 0,\\
S[i-1][j] + S[i][j-1] – S[i-1][j-1] + A[i][j] & \text{dacă } i > 0 \text{ și } j > 0.
\end{cases} $$

Observație: Este posibil ca suma elementelor din matricea dată să depășească limita maximă a tipului de date folosit (ex. int), ceea ce duce la overflow. În acest caz, matricea S[][] trebuie declarată de un tip mai larg (ex. long long int).

Secvență C++

int n,m, A[1001][1001], S[1001][1001];
//citire n,m,A[][]

for(int i = 0 ; i <= n ; i ++)
    S[i][0] = 0;
for(int j = 0 ; j <= m ; j ++)
    S[0][j] = 0;

for(int i = 1 ; i <= n ; i ++)
    for(int j = 1 ; j <= m ; j ++)
        S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];

int is,js; // coltul stanga sus
int ij,jj; // coltul dreapta jos
//citire is,js, ij,jj;

cout << S[ij][jj] - S[is-1][jj] - S[ij][js-1] + S[is-1][js-1];

Introducere

Căutarea unei valori într-un vector se poate face în două moduri:

• secvențial – presupune analizarea fiecărui element al vectorului într-o anumită ordine (de obicei de la stânga la dreapta). Când se găsește valoarea căutată parcurgerea vectorului se poate opri. În cel mai rău caz, pentru un vector cu n elemente parcurgerea face n pași, complexitatea timp a căutării secvențiale este O(n)
• binar. Căutarea binară se poate face într-un vector numai dacă elementele acestuia sunt în ordine (de obicei crescătoare) după un anumit criteriu (de obicei criteriul este chiar relația de ordine naturală între numere, cuvinte, etc). Căutarea binară presupune împărțirea vectorului în secvențe din ce în ce mai mici, înjumătățindu-le și continuând cu jumătatea în care se poate afla valoarea dorită (conform ordinii elementelor din vector).

Algoritm pseudocod

Algoritmul căutării binare este următorul:

Date de intrare:

• un vector v[] cu n elemente, indexate de la 1 la n, ordonate crescător și o valoare x care se va căuta.

Date de ieșire:

• un indice poz dacă valoarea x apare în vectorul v[] sau 0 în caz contrar.

Algoritm pseudocod:

st ← 1
dr ← n
poz ← 0
CÂTTIMP st≤dr SI poz=0 EXECUTĂ
    m ← (st + dr) DIV 2
    DACĂ v[m] = x ATUNCI 
        poz = m
    ALTFEL
        DACĂ v[m] < x ATUNCI
            st ← m + 1
        ALTFEL
            dr ← m - 1
        SFDACĂ
    SFDACĂ
SFCÂTTIMP

DACĂ poz≠0 ATUNCI
    // x apare în vector pe poziția poz
ALTFEL
    // x nu apare în vector 
SFDACĂ

Notă: În algoritmul de mai sus a DIV b reprezintă câtul împărțirii lui a la b, iar cu V ← EXPR s-a notat atribuirea la variabila V a rezultatului expresiei EXPR.

Altă variantă a căutării binare

De multe nu este suficient să știm dacă o valoare dată apare sau nu în vector. Sunt numeroase situații în care trebuie să aflăm un indice al vectorului (element al vectorului) care respectă o anumită condiție în raport cu valoarea dată. De exemplu:

• să se determine cel mai mare indice poz pentru care v[poz] ≤ x;
• să se determine cel mai mare indice poz pentru care v[poz] < x;
• etc.

Algoritmul de mai jos determină cel mai mare indice poz pentru care v[poz] ≤ x. El poate fi folosit și pentru a verifica dacă x apare în vector, astfel: dacă la final v[poz] = x, atunci x apare în vector, in caz contrar nu apare.

st ← 1
dr ← n
poz ← n + 1
CÂTTIMP st ≤ dr EXECUTĂ
    m ← (st + dr) DIV 2
    DACĂ v[m] ≥ x ATUNCI 
        poz ← m
        dr ← m - 1
    ALTFEL
        st ← m + 1
    SFDACĂ
SFCÂTTIMP

DACĂ v[poz] = x ATUNCI
    // x apare în șir pe poziția poz
ALTFEL
    // x nu apare în șir (în acest caz, v[poz] > x)
SFDACĂ

Șmenul lui Mars în vector

Să presupunem că avem un vector A[] cu n elemente, indexate de la 1 la n, inițial nule, în care se fac mai multe operații Adună(s,d,X) prin care toate elementele din secvența delimitată de indicii s d cresc cu valoarea X. Se cere afișarea elementelor din A după efectuarea acestor operații.

Metoda descrisă în continuare este cunoscută în lumea olimpicilor la informatică sub numele de “Șmenul lui Mars”, atribuită fostului olimpic Marius Andrei. De asemenea, se regăsește sub numele “Difference Array”, de exemplu pe www.geeksforgeeks.org. Vezi Șmenul lui Mars pe infoarena.ro!

Operațiile pot fi efectuate eficient construind un vector suplimentar B[], cu n+1 elemente, astfel încât A[i]=B[1]+B[2]+...+B[i]. Vectorul A[] este vector de sume parțiale pentru vectorul B[].

Operația Adună(s,d,X) devine:

B[s] += X;
B[d+1] -= X;

La final, elementele lui A se reconstituie astfel: A[i]=B[1]+B[2]+...+B[i]

A[1] = B[1];
for(int i = 2 ; i <= n ; i ++)
    A[i] = A[i-1] + B[i];

Șmenul lui Mars în matrice

Cunoscută și sub denumirea de Șmenul lui Mars 2D, această tehnica se aplică în rezolvarea problemelor la care se cere, pentru o matrice dată A[][] mărirea cu o valoare dată X a tuturor elementelor din submatricea determinată de colțul stânga-sus (i1,j1) și colțul dreapta-jos (i2,j2). Această operație se aplică de mai multe ori, pentru diverse submatrice și diverse valori ale lui X și se cere determinarea elementelor din A[][] după aceste operații.

Putem proceda similar ca în cazul unidimensional, construind o matrice suplimentară M[][], astfel incât matricea A[][] reprezintă matrice de sume parțiale pentru M[][].

Operațiile date devin:

M[i1][j1] += x;
M[i1][j2+1] -= x;
M[i2+1][j1] -= x;
M[i2+1][j2+1] += x;

Observații:

• Matricea M[][] are cu o linie și o coloană mai mult decât matricea A[][].
• Fiecare operație prin care se măresc elementele dintr-o submatrice are complexitate constantă.

Exemplu

Refacerea matricei A[][] se face ținnând cont de faptul că este matrice de sume parțiale pentru M[][]:

for(int i = 1 ; i <= n ; i ++)
	for(int j = 1; j <= m ; j ++)
		A[i][j] = M[i][j] + A[i-1][j] + A[i][j-1] - A[i-1][j-1];

În anumite situații, tipurile de date existente în limbajele de programare nu sunt suficient de “încăpătoare” – nu permit memorarea de valori foarte mari, alcătuite din multe cifre. De aceea este necesară implementarea unor structuri de date care să permită memorarea unor asemenea valori, precum și operațiile aritmetice de bază cu ele. Aceste structuri se numesc numere mari, iar operațiile realizate cu acestea se numesc operații cu numere mari.

Acest articol prezintă operațiile cu numere mari pentru numere naturale, folosind limbajul C++.

Memorarea numerelor mari

Vom folosi în acest scop un vector, care sa conțină pe prima poziție v[0] lungimea numărului mare (numărul de cifre), iar pe pozițiile 1, 2, … , v[0] vom memora cifrele numărului, în ordine inversă.

De exemplu, pentru memorarea numărului 15207, vom avea structura:

   i  0  1  2  3  4  5  6  7 
v[i]  5  7  0  2  5  1  0  0 

unde v[0] = 5 reprezintă numărul de cifre, iar v[1] = 7 cifre unităților, v[2] = 0 cifra zecilor, v[3] = 2 cifra sutelor, etc.

Memorarea “răsturnată” a numărului nu este foarte firească, dar este foarte practică pentru implementarea operațiilor aritmetice.

ATENȚIE! Este important ca v[0] sa memoreze corect lungimea numărului, fără a fi luate în considerare zerourile nesemnificative (cele de la începutul numărului, respectiv sfârșitul vectorului).

Pentru rezolvarea problemei vom defini tipul NrMare, pentru a clarifica operațiile care urmează.

typedef int NrMare[1010];

Inițializarea numerelor mari

Un număr mare se poate inițializa cu alt număr mare sau cu un număr mic – adica un număr ce face parte dintr-un tip de date întreg predefinit; în cele ce urmează, îl vom considera int.

void AtribMic(NrMare x, int n)
{
  x[0]=0;
  if(n==0)
    x[(x[0]=1)]=0;
  else
    for(;n;n/=10)
      x[++x[0]]=n%10;
}

void AtribMare(NrMare Dest, NrMare Sursa)
{
  int i;
  for(i=0;i<=Sursa[0];i++)
    Dest[i]=Sursa[i];
}

Compararea numerelor mari

Compararea este cea matematica:

• dacă un număr are mai multe cifre decât celălalt, este mai mare;
• dacă nu, se compară cifrele începând cu cele mai semnificative, până la capăt (în cazul egalității) sau până se deduce relația dintre cele două numere. Aici este foarte importantă corectitudinea numărului de cifre (memorata în v[0]).

Funcția care urmează compară două numere mari, returnând 0 dacă numerele sunt egale, -1 dacă primul este mai mic decât al doilea și 1 în cealaltă situație.

int Compara(NrMare x, NrMare y)
{
  while(x[0]>1 && x[x[0]]==0)
    x[0]--; //ma asigur ca nu sunt zerouri nesemnificative
  while(y[0]>1 && y[y[0]]==0)
    y[0]--;
  if(x[0]!=y[0])
    return (x[0]<y[0]?-1:1);
  int i=x[0];
  while(x[i]==y[i] && i>0) 
    i--;
  if(i==0)
    return 0;
  if(x[i]<y[i])
    return -1;
  return 1;
}

Adunarea numerelor mari

Următoarele funcții realizează de fapt atribuirea A = A + B. Aceasta este suficientă în majoritatea problemelor. Dacă doriți, puteți implementa similar o operație de de forma A = B + C. Aceeași observație este valabilă pentru toate operațiile care urmează: scăderea, înmulțirea cu număr mic, înmulțirea cu număr mare, câtul împărțirii la un număr mic, restul împărțirii la un număr mic.

Algoritmul de adunare este cel folosit la adunarea numerelor pe hârtie: se adună cifrele corespunzătoare între ele și cu eventualul transport. Dacă suma este mai mare decât 10, aflăm cifra corespunzătoare și recalculăm transportul.

void Adunare(NrMare x,NrMare y)
// x = x + y
{
  int i,t=0;
  if(x[0]<y[0]) 
    x[0]=y[0];
  for(i=1;i<=x[0];i++,t/=10)
  {
    t=x[i]+y[i]+t;
    x[i]=t%10;
    // echivalent x[i]=(t+=x[i]+y[i])%10
  }
  if(t)
    x[++x[0]]=t;
}

Scăderea numerelor mari

În cazul scăderii A = A - B, se consideră ca A este mai mare sau egal cu B, chestiune ce poate fi verificată cu ajutorul funcției descrise mai sus.

Scăderea se face și ea la fel ca pe hârtie. Dacă pot scădea cifrele corespunzătoare, le scădem, dacă nu “ne împrumutăm” de la următoarea cifră nenulă și facem scăderea corespunzătoare.

void Scadere(NrMare x, NrMare y)
// x <-- x-y
{
  int i,j, t = 0;
  for (i = 1; i <= x[0]; i++)
    if(x[i]>=y[i]) 
      x[i]-=y[i];
    else
    {
      j=i+1;
      while(x[j]==0)
        x[j++]=9;
      x[j]--;
      x[i]=10+x[i]-y[i];
    }
  for (; x[0] > 1 && !x[x[0]]; x[0]--); // sa n-am zerouri nesemnificative
}

Înmulțirea unui număr mare cu un număr mic

Și înmulțirea se poate face ca pe foaie. De fapt chiar așa facem. Dacă numărul mic este de o singura cifra, este evident. Partea bună este că procedăm analog și dacă înmulțitorul (număr mic) are mai multe cifre. Trebuie însă să fim atenți că transportul final poate fi format din mai multe cifre, asă că trebuie distribuit pe mai multe poziții.

void ProdusMic(NrMare x, int n)
//x <- x*n
{
  int i,t=0;
  for(i=1;i<=x[0];i++,t/=10)
  {
    t+=x[i]*n;
    x[i]=t%10;
  }
  for(;t;t/=10)
    x[++x[0]]=t%10;
}

Înmulțirea numerelor mari

Și înmulțirea numerelor mari se face aproximativ conform algoritmului clasic: înmulțim fiecare cifră a numărului y cu numărul x și adunăm corespunzător rezultatele.

De data aceasta este nevoie sa folosim un “număr mare” suplimentar, pentru rezultatele parțiale. Lungimea lui este x[0]+y[0]-1 sau x[0]+y[0], după cum avem transport la sfârșit.

Prezentăm mai jos aplicarea algoritmului pe un caz concret:

Înmulțim 312 cu 87

      3   1   2 *
          8   7

Calculăm produsele intermediare

      21   7  14
  24   8  16

Calculăm sumele

  24  29  23  14
 <-2 <-3 <-2 <-1

Corectăm rezultatul

2  7   1   4   4

Funcția corespunzătoare este:

void ProdusMare(NrMare x, NrMare y)
//x = x * y
{
  int i,j,t=0;
  NrMare z;
  //stabilim lungimea rezultatului. S-ar putea modifica
  z[0]=x[0]+y[0]-1;
  //initializez vectorul z
  for(i=1;i<=x[0]+y[0];i++) 
    z[i]=0;
  //calculez produsele intermediare, impreuna cu suma intermediara
  for(i=1;i<=x[0];i++)
    for(j=1;j<=y[0];j++)
      z[i+j-1]+=x[i]*y[j];
  //corectez sumele intermediare
  for(i=1;i<=z[0];i++)
  {
    t+=z[i];
    z[i]=t%10;
    t/=10;
  }
  if(t)
    z[++z[0]]=t;
  // pun rezultatul in x
  for(i=0;i<=z[0];i++)
    x[i]=z[i];
}

Impărțirea unui număr mare la un număr mic

Ca de obicei, algoritmul folosit este cel folosit și la calculul pe hârtie: determinăm pe rand cifrele câtului și corectăm restul.

Funcția prezentată mai jos returnează restul împărțirii și transformă deîmpărțitul în cât.

int Divide(NrMare x, int n)
//x = x /n, returneaza x%n
{
  int i,r=0;
  for(i=x[0];i>0;i--)
  {
    r=10*r+x[i];
    x[i]=r/n;
    r%=n;
  }
  for(;x[x[0]]==0 && x[0]>1;) 
    x[0]--;
  return r;
}

Folosirea altor baze de numerație

În anumite situații, realizarea calculelor cu numere mari în baza 10 nu este destul de eficientă, datorită numărului mare de operații care se efectuează.

Pentru a spori eficiența programului, putem considera numerele date ca fiind scrise în alte baze, puteri ale lui 10. De exemplu, numărul 123456789012345678901234567890 are 30 de cifre în baza 10, dar numai 5 cifre în baza 106. Acestea sunt: 123456 789012 345678 901234 567890

Toate operațiile descrise mai sus se fac similar, dar trebuie ținut cont de următoarele observații:

• la afișare trebuie analizat numărul de cifre zecimale a fiecărei cifre a numărului mare și eventual completat cu zerouri. De exemplu, numărul scris în baza 1000 format din cifrele (în ordine inversă) 876 2 34 75 se va scrie 75034002876
• baza trebuie aleasă astfel încât operațiile cu cifrele numărului mare să nu producă depășire de tip (overflow). De exemplu, dacă numerele sunt scrise în baza 1000000 și se folosește pentru cifrele numărului mare tipul int, nu se vor realiza corect operațiile de înmulțire (la înmulțirea a două numere de ordinul sutelor de mii se depășește 231-1 – limita superioară a tipului int).