Articole recomandate

Introducere

Se dă un tablou A cu n elemente întregi. Să se determine o secvență pentru care suma elementelor este maximă.

Problema este una clasică și admite diverse soluții. Vom vedea în continuare trei soluții, de complexități diferite! Să observăm însă că, dacă elementele ar fi pozitive, atunci secvența cerută ar fi întreg tabloul.

În continuare vom numi secvență candidat o secvență care ar putea fi secvența cerută.

Soluția 1

Prima soluție are complexitatea \(O(n^3)\) și poate fi folosită când valoarea lui n este în jur de 100.

Fiecare secvență a vectorului poate fi secvență candidat. Vom identifica toate secvențele delimitate de indicii i j, cu 1 ≤ i ≤ j ≤ n. Pentru fiecare secvență, vom determina suma elementelor care o compun și vom reține secvența de sumă maximă:

int st = 0 , dr = 1 , Smax = -2000000000 , S;
for(int i = 1 ; i <= n ; ++ i)
    for(int j=i;j<=n;++j)
    {
        S = 0;
        for(int k = i ; k <= j ; ++ k)
            S += A[k];
        if(S > Smax)
            Smax = S, st = i, dr = j;
    }
cout << Smax << endl;
cout << st << " " << dr;

Soluția 2

Soluția anterioară poate fi îmbunătățită folosind sume partiale pentru a determina suma elementelor din secvența i j. În acest mod complexitatea scade la \(O(n^2)\) și poate fi folosită când valoarea lui n este în jur de 1000.

SP[0] = 0;
for(int i =1 ; i <= n ; i ++)
    SP[i] = SP[i-1] + A[i];
int st = 0 , dr = 1 , Smax = -2000000000 , S;
for(int i = 1 ; i <= n ; ++ i)
    for(int j=i;j<=n;++j)
    {
        S = SP[j] - SP[i-1];
        if(S > Smax)
            Smax = S, st = i, dr = j;
    }
cout << Smax << endl;
cout << st << " " << dr;

Soluția 3

Ultima soluție, de complexitate liniară – \(O(n)\) pleacă de la ideea că dacă într-o secvență (PQ), formată prin reuniunea (lipirea) secvențelor (P) și (Q), suma elementelor din secvența (P) este negativă, atunci suma elementelor din sevența (Q) este mai mare decât suma elementelor din secvența (PQ). În cest caz secvența (PQ) nu mai este secvență candidat, dar (Q) este (probabil) secvență candidat.

Procedăm astfel:

• parcurgem tabloul și adunăm elementul curent A[i] la S – acesta reprezentând suma elementelor dintr-o secvență candidat;
• dacă S este mai mare decât suma maximă, actualizăm rezultatele;
• dacă S devine negativ, îl reinițializăm la 0; tot acum reinițializăm și poziția de început a secvenței candidat.

int st , dr, Smax = -2000000000 , S = -1, start;
for(int i = 1 ; i <= n ; ++ i)
{
    if(S < 0)
        S = 0, start = i;
    S += A[i];
    if(S > Smax)
        Smax = S, st = start, dr = i;
}
cout << Smax << endl;
cout << st << " " << dr;

Soluția de mai sus poate fi utilizată pentru valori mai mari ale lui n, de exemplu 100000 sau 1000000. De asemenea, poate fi ușor modificată încât să se evite folosirea tabloului, determinând rezultatul direct din citire. Astfel, complexitatea spațiu a algoritmului devine \(O(1)\).

Probleme propuse

• #SecvSumMax
• #ursulet

Ciurul lui Eratostene este o metodă rapidă prin care stabilește despre fiecare număr natural mai mic sau egal cu un n dat dat este prim sau nu. Valoarea lui n trebuie să fie suficient de mică pentru a putea declara un tablou P cu n+1 elemente, un element P[k] având valoarea 1 dacă k este prim, respectiv valoarea 0 dacă k nu este prim.

Următoarea secvență C++ construiește tabloul P[]:

int P[n+1];
for(int i = 0 ; i <= n ; i ++)
    P[i] = 1;
P[0] = P[1] = 0;
for(int i = 2 ; i * i <= n ; i ++)
    if(P[i] == 1)
        for(int j = 2 ; i * j <= n ; j ++)
            P[i * j] = 0;

Ideea de mai sus poate fi utilizată pentru a determina diverse rezultate în care intervin divizorii unui număr, rezultate calculate pentru toate numerele mai mici sau egale cu n:

• numărul de divizori
• suma divizorilor
• cel mai mic divizor prim
• cel mai mare divizor prim
• indicatorul lui Euler

Numărul de divizori

• construim un vector Nr[]. La final, Nr[x] va fi numărul de divizori ai lui x;
• inițializăm elementele vectorului Nr[] cu 0;
• parcurgem vectorul și pentru fiecare element Nr[i] mărim valorile elementelor Nr[k], unde k = i * j este multiplu al lui i – dacă i este divizor al lui k, atunci trebuie numărat ca atare.

int Nr[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    Nr[i] = 0;
for(int i = 1; i <= DIM ; i ++)
    for(int j = 1 ; i * j <= DIM ; j ++)
        Nr[i * j] ++;

OBS: Un număr x este prim dacă și numai dacă la final Nr[x] este egal cu 2.

Suma divizorilor

• construim un vector S[]. La final, S[x] va reprezenta suma divizorilor lui x;
• inițializăm elementele vectorului S[] cu 0;
• parcurgem vectorul și pentru fiecare element S[i] mărim valorile elementelor S[k] cu i, unde k = i * j este multiplu al lui i – dacă i este divizor al lui k, atunci trebuie adunat la suma divizorilor lui k.

int S[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    S[i] = 0;
for(int i = 1; i <= DIM ; i ++)
    for(int j = 1 ; i * j <= DIM ; j ++)
        S[i * j] += i;

OBS: Un număr x este prim dacă și numai dacă la final S[x] este egal cu x+1.

Cel mai mic/mare divizor prim

• construim un vector M[]. La final, M[x] va reprezenta cel mai mic divizor (factor) prim al lui x;
• inițializăm elementele vectorului M[x] cu x – pentru numerele prime cel mai mic factor prim sunt ele însele;
• parcurgem numerele începând de la 2 și pentru fiecare număr i prim (pentru care M[i] = i) modificăm, dacă este cazul, cel mai mic factor prim pentru toți multipli k = i * j lui i.

int M[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    M[i] = i;
for(int i = 2; i <= DIM ; i ++)
    if(M[i] == i)
        for(int j = 2 ; i * j <= DIM ; j ++)
            if(M[i * j] == i * j)
                M[i * j] = i;

OBS:

• Un număr x este prim dacă și numai dacă la final M[x] este egal cu x.
• La parcurgerea multiplilor lui i, vom modifica multiplul k = i * j numai dacă M[k] este încă k. De exemplu, pentru i=3, nu-l mai modifică pe M[6] – a fost deja modificat pentru i=2.
• Dacă modificăm M[k] de pentru fiecare i, deoarece i este considerat în ordine crescătoare, la final M[k] va memora cel mai mare divizor prim al lui k. Următoarea secvență obține acest rezultat – observați că modificările sunt minore:

int M[DIM + 1];
for(int i = 1 ; i <= DIM ; i ++)
    M[i] = i;
for(int i = 2; i <= DIM ; i ++)
    if(M[i] == i)
        for(int j = 2 ; i * j <= DIM ; j ++)
            M[i * j] = i;

Indicatorul lui Euler

Indicatorul lui Euler este tratat în acest articol. Reluăm aici numai secvența C/C++:

int F[DIM + 1];
for(int i =1 ; i <= DIM ; i ++)
    F[i] = i;
for(int i = 2;  i <= DIM ; i ++)
    if(F[i] == i)
    {
        for(int j = 1 ; j * i <= DIM ; j ++)
            F[j * i]= F[j * i] / i * (i - 1);
    }

OBS: Un număr x este prim dacă și numai dacă la final F[x] este egal cu x-1.

Alte probleme

Încercați să determinați în același mod:

• numărul factorilor primi
• suma/produsul factorilor primi
• etc.

Standard Template Library – STL conține două funcții extrem de utile care realizează căutarea binară, lower_bound și upper_bound. Ele se găsesc în headerul algorithm și realizează căutarea atât pentru vectori STL cât și pentru tablourile unidimensionale standard C. În ambele cazuri elementele structurii de date trebuie să fie ordonate după un anumit criteriu, iar funcțiile au următoarele rezultate:

• lower_bound – cel mai din stânga element care este mai mare sau egal cu valoarea căutată;
• upper_bound – cel mai din stânga element care este strict mai mare decât valoarea căutată.

Observație: STL conține și funcția binary_search, care caută într-o structură de date o anumită valoare și returnează true dacă o găsește și false în caz contrar. Funcția lower_bound furnizează informații suplimentare, fiind astfel mai utilă în practică.

Căutarea în vectori STL

Antetele funcțiilor sunt:

1. Iterator lower_bound(Iterator p, Iterator u, Valoare v);
2. Iterator lower_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Valoare este un tip de date oarecare pentru care este definită relația de ordine < sau funcția comparator fcmp, iar p și u sunt iteratori la elemente ale unui vector STL de tip vector<Valoare>.

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare sau egal cu v și returnează iterator la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

1. Iterator upper_bound(Iterator p, Iterator u, Valoare v);
2. Iterator upper_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare strict decât v și returnează iterator la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

În funcțiile de mai sus, numele parametrilor au următoarea semnificație:

• p – primul
• u – ultimul
• v – valoarea de căutat
• f – comparator (funcție de comparare)

Important: Elementul u nu face parte din secvența în care se caută valoarea v.

Exemplu

vector<int> A;
int k;
....
auto I = lower_bound(A.begin(), A.end(), k); // I este iterator
if(I == A.end() || *I != k)
    cout << k << " nu apare în vector";
else
    cout << k << " apare în vector pe poziția " << I - A;

Căutarea în tablouri unidimensionale standard C

Antetele funcțiilor sunt:

1. Valoare * lower_bound(Valoare * p, Valoare * u, Valoare v);
2. Valoare * lower_bound(Valoare * p, Valoare * u, Valoare v, Comparator fcmp);

Valoare este un tip de date oarecare pentru care este definită relația de ordine < sau funcția comparator fcmp, iar p și u sunt pointeri la Valoare șî reprezintă adresele unor elemente ale unui tablou declarat Valoare A[dim];.

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare sau egal cu v și returnează pointer la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

1. Iterator upper_bound(Iterator p, Iterator u, Valoare v);
2. Iterator upper_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare strict decât v și returnează pointer la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

Exemplu 1

#include <iostream>
#include <algorithm>

int main()
{
    int n = 10, v[]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // indexare de la zero

    //lower_bound: cel mai din stânga iterator i pentru care v[i] >= x
    std::cout << std::lower_bound(v , v + n , 20) - v << std::endl; // 1, v[1] >= 20
    std::cout << std::lower_bound(v , v + n , 25) - v << std::endl; // 2, v[2] >= 25

    //upper_bound: cel mai din stânga iterator i pentru care v[i] > x

    std::cout << std::upper_bound(v , v + n , 20) - v << std::endl; // 2, v[2] > 20
    std::cout << std::upper_bound(v , v + n , 25) - v << std::endl; // 2, v[2] > 25

    return 0;
}

Exemplu 2

int A[1000], n; // indexat de la  0  la n - 1
int k;
....
int * q = lower_bound(A, A + n, k); // q este pointer
    if(q == A + n || *q != k)
        cout << k << " nu apare în tablou";
    else
        cout << k << " apare în tablou la indicele " << q - A;

Funcția de comparare

Dacă elementele vectorului (tabloului) satisfac altă relație de ordine, va trebui să definim o funcție de comparare, fcmp, sau să folosim un predicat din STL. De exemplu, dacă vectorul (tabloul) are elementele în ordine descrescătoare putem folosi greater. De exemplu:

int A[1000], n; // indexat de la  0  la n - 1
int k;
....
int * q = lower_bound(A, A + n, k, greater<int>());

În cazul unei relații de ordine mai complexe, se poate defini o funcție de comparare, în felul următor:

bool fcmp(Valoare A, Valoare B);

Funcția are doi parametru de același tip cu elementel tabloului (vectorului) în care face căutarea și va returna true, dacă primul parametru, A, este strict înaintea lui B în ordinea dorită și false în caz contrar.

Referințe

• cppreference.com: lower_bound
• cppreference.com: upper_bound

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 trebuie î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 tablou 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];

Să spunem că știm notele unor elevi și trebuie să le afișăm în ordine crescătoare. Dacă sunt trei elevi, vom folosi trei variabile, dacă sunt 6 elevi, putem folosi 6 variabile, dar dacă sunt 50 de elevi? Putem folosi 50 de variabile, dar nu este tocmai ușor!! Probabil, niciun om întreg la minte nu va folosi 50 de variabile…. Aici își arată forța tablourile!

Un tablou este o colecție de date de același tip, stocat în memorie într-o zonă continuă. Fiecare dată din colecție, numită element al tabloului poate fi folosită ca variabilă oarecare de tipul precizat, fiind identificat printr-o operație numită indexare.

Elementele tablourilor pot avea unul sau mai mulți indici. Astfel, tablourile pot fi:

• unidimensionale, numite și vectori – fiecare element are un indice
• bidimensionale, numite și matrice – fiecare element are doi indici
• multidimensionale – fiecare element are trei sau mai mulți indici.

Acest articol este dedicat tablourilor unidimensionale!

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 ori 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];

Introducere

Ciurul lui Eratostene reprezintă o metodă de determinare a tuturor numerelor prime mai mici sau egale cu o valoare dată, n. În practică, valoarea lui n trebuie să fie una rezonabilă, ea depinzând de restricțiile de timp și memorie aplicate problemei.

Ciurului Eratostene se aplică în felul următor – în continuare lucrăm cu n=30:

• se scriu toate numerele naturale de la 1 la n=30:

• se taie din lista numărul 1, care nu este prim

• se identifică următorul număr netăiat, 2. Acest este prim, iar din listă se vor tăia toți multipli săi, mai mari decât acesta.

• se identifică următorul număr netăiat, 3. Acest este prim, iar din listă se vor tăia toți multipli săi, mai mari decât acesta. Unii dintre ei au fost deja tăiați, deoarece sunt și multipli ai lui 2.

• se identifică următorul număr netăiat, 5. Acest este prim, iar din listă se vor tăia toți multipli săi, mai mari decât acesta. Unii dintre ei au fost deja tăiați, deoarece sunt și multipli ai lui 2 sau 3.

• se identifică următorul număr netăiat, 7. Acesta este prim, dar totodată 7*7>30 căutarea numerelor prime s-a încheiat. Toate numerele care nu au fost tăiate sunt prime.

Animație

Algoritm

Pentru identificarea numerelor prime într-un algoritm/program, vom folosi un vector caracteristic, v[], cu următoarea semnificație:

\( v[x]=\begin{cases} 0& \text{dacă $x$ prim},\\1& \text{dacă $x$ nu este prim}.\end{cases} \)

Vom porni de la un vector cu toate elementele nule, apoi vom marca pe rând cu 1 toate numerele care sunt multipli ai unor numere mai mici. Un algoritm pseudocod care realizează acest operații este:

pentru i←0,n execută
    V[i] ← 0
sf_pentru
V[0] ← 1
V[1] ← 1
pentru i ← 2,sqrt(n) execută
    dacă V[i] = 0 atunci
        pentru j ← 2, [n/i] execută
            V[i*j] ← 1
        sf_pentru
    sf_dacă
sf_pentru

Probleme similare

Mecanismul prin care se identifică numerele prime specific Ciurului lui Eraostene poate fi folosit și la determinarea altor rezultate. De exemplu, vrem să aflăm pentru un n dat (nu prea mare) câți divizori are fiecare număr natural din intervalul [1,n].

Pentru acesta, vom construi un vector V, în care v[x] reprezintă numărul de divizori ai lui x. Pentru a construi acest vector, vom parcurge numerele de la 1 la n, și pentru fiecare număr x vom identifica multiplii săi. Pentru fiecare y multiplu al lui x vom incrementa valoarea lui v[y].

Un algoritm pseudocod este:

pentru i←1,n execută
    V[i] ← 0
sf_pentru
pentru x ← 1,n execută
    pentru y ← x, n , x  execută
        V[y] ← V[y] + 1
    sf_pentru
sf_pentru

Î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).