Probleme cu numere lipsa si nu numai ...

(Categoria Diverse, autor Cosmin Negruseri)

Problema 1 ( interviu Microsoft )

Se dau numere distincte de la la , sa se dea un algoritm cat mai eficient care sa determine numarul lipsa.

Rezolvare

Prima rezolvare ce ne poate veni in minte este aceea ca pentru fiecare numar de la la sa verificam daca numarul curent nu exista in sir prin o parcurgere. Un astfel de algoritm are complexitatea si vom vedea mai departe ca putem obtine solutii mult mai bune.

O rezolvare triviala ar fi sa sortam cu metoda noastra preferata numerele si sa le parcurgem pentru a vedea cand . Aceasta rezolvare are complexitatea .

O rezolvare mai eficienta poate fi data urmarind ideea algoritmului Quick Sort. Putem imparti numerele in doua multimi, una in care vom pune mumerele mai mici sau egale cu , iar in cealalta numerele mai mari decat . Acum vom sti daca numarul lipsa este mai mic sau egal cu sau mai mare ca , dupa numarul de elemente din fiecare lista. Astfel in pasi am redus problema la jumatate. Daca avem timpul de executie al acestui algoritm, atunci . Deci algoritmul este liniar, si foloseste memorie ignorand memoria consumata de sirul de numere pentru stiva din algoritmul divide et impera.

O alta idee este aceea de a folosi un tabel de dispersie sau un sir de valori booleene care va folosi memorie suplimentara , iar daca folosim biti reducem memoria suplimentara la .

O rezolvare eleganta se foloseste de proprietatea ca suma numerelor naturale de la la este , iar suma numerelor o putem afla prin o parcurgere. Acum determinarea numarului lipsa se face prin scaderea din suma numerelor de la la a sumei numerelor noastre. Aceasta solutie are complexitatea ca timp si ca memorie folosita.

Daca este destul de mare, s-ar putea ca sa depaseasca domeniul de reprezentare al intregilor de pe calculatorul nostru si ar trebui sa implementam operatii cu numere mari ca solutia anterioara sa produca rezultatul corect. O rezolvare ce nu are aceasta problema se foloseste de operatia xor si de proprietatile ei si . Vom face suma xor a numerelor cu de la la :

Astfel fiecare numar care apare in sir va fi in suma de doua ori si va fi anulat, iar pentru numarul lipsa, in suma va aparea doar indicele lui, care este si valoarea finala a sumei. Solutia are compexitatea ca timp si ca spatiu.

Problema 2 ( interviu Microsoft )

Se da un sir de numere de la la in care unul se repeta, iar restul sunt distincte. Sa se dea un algoritm cat mai eficient care sa determine numarul ce se repeta.

Rezolvare

Evident, abordarile de la problema anterioara se aplica si aici.

Problema 3 ( lot 1999, interviu Microsoft )

Se da o lista inlantuita prin primul ei element. Se cere un algoritm cat mai eficient care sa determine daca lista are sau nu ciclu.

Rezolvare

Fie numarul total de elemente ale listei. O solutie in timp si memorie ar fi sa parcurgem lista si sa adaugam pe rand elementele listei unui tabel de dispersie. Cand am introdus acelasi element de doua ori in lista este evident ca am gasit un ciclu. O metoda folosita de unii concurenti a fost parcurgerea listei pe o perioada de timp determinata, de exemplu timpul de executie fixat in problema. Acum sunt sanse mari ca daca nu am ajuns la capatul listei aceasta sa aiba ciclu.

Exista un algoritm mai elegant ce foloseste memorie suplimentara si este liniar. Acest algoritm se numeste Algoritmul lui Floyd de detectie a ciclului intr-o lista. O aplicatie importanta a lui este Algoritmul Pollard , folosit pentru factorizarea intregilor cu multe cifre. Algoritmul foloseste doi pointeri si , unde se misca de doua ori mai repede decat in lista, de aceea se mai numeste si Algoritmul iepurelui si testoasei.

Reprezentarea grafica seamana cu litera greceasca . Notam lungimea lantului cu si lungimea ciclului cu .