Articole

amongus∓∅∈∊└■└■│└\lim_{n \rightarrow \infty}\( \)sus

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:

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 x ← x, n , x  execută
        V[y] ← V[y] + 1
    sf_pentru
sf_pentru