Eficienta.docx

V1 Algoritmul de rezolvare propus citește, unul câte unul, numerele din fișier, analizând paritatea fiecăruia: întâlnirea unui număr par va duce la "prelungirea" secvenței curente, iar întâlnirea unui număr impar va conduce la trecerea la o nouă secvență. La finele oricărei secvențe se analizează lungimea ei, în vederea memorării lungimii maxime. Eficiența algoritmului, ca timp de executare, constă în faptul că parcurgem o singură dată șirul. Deoarece numărul de valori din fișier (1000000) este dimensiunea care contează în problemă, spunem că am obținut un algoritm liniar. Ca spațiu de memorie, soluția propusă este eficientă, deoarece utilizează doar variabile simple. Pentru o descriere coerentă a metodei se acordă 1p., iar pentru justificarea eficienței, încă 1p. - în total 2p.

V2 Algoritmul de rezolvare propus determină suma cifrelor primului număr sx și apoi citește un număr din fișier, comparând suma cifrelor acestuia cu sx: în caz de egalitate se "prelungește" secvența curentă, în caz contrar, se trece la o nouă secvență cu o nouă sumă sx curentă. La finalul oricărei secvențe se analizează lungimea ei, în vederea memorării lungimii maxime. Eficiența algoritmului, ca timp de executare, constă în faptul că determinăm valoarea cerută în timpul citirii datelor, deci parcurgem o singură dată șirul de numere. Ca spațiu de memorie, soluția propusă este eficientă, deoarece utilizează doar variabile simple, fără folosirea unor structuri suplimentare de date. Pentru o descriere coerentă a metodei se acordă 1p., iar pentru justificarea eficienței, încă 1p. - în total 2p. Deși o implementare cu ajutorul unui subprogram ce calculează suma cifrelor unui număr natural era mult mai elegantă, putem duce la extrem noțiunea de eficiență, spunând că apelul unui subprogram necesită operații în plus (gestiunea stivei la apel și la revenire), deci e mai bine să nu utilizăm subprograme. În general, nu considerăm că trebuie dusă la absurd noțiunea de eficiență prin invocarea unor detalii tehnice de limbaj, ci ea trebuie să rămână la nivel algoritmic.

V3 Algoritmul de rezolvare propus presupune determinarea poziţei pp a primului numr format doar din cifre pare, respectiv ui a ultimului numar format doar din cifre impare, din fişier pe măsura citirii datelor și utilizează doar variabile simple fără folosirea unor structuri suplimentare de date. Eficiența algoritmului, ca timp de executare, constă în faptul că parcurgem o singură dată șirul cu un număr impresionant de numere. Deoarece numărul de valori din fișier (1000000) este dimensiunea care contează în problemă, spunem că am obținut un algoritm liniar. Ca spațiu de memorie, soluția propusă este eficientă, deoarece utilizează doar variabile simple. Lungimea subşirului căutat va fi: ui-pp+1 sau 0 dacă pp=0 sau ui=0. Pentru o descriere coerentă a metodei se acordă 1p., iar pentru justificarea eficienței, încă 1p. - în total 2p.

V4 Vom utiliza un vector de frecvențe cu 10 elemente fc pentru a contoriza aparițiile fiecărei cifre. Vom parcurge fișierul bac.in, folosind variabila c o variabila, și, în cazul în care variabila c conține o cifră, vom crește frecvența sa cu 1. Cel mai mare număr care se poate forma folosind cifrele tuturor numerelor din fișier se obține scriind în fișierul bac.out fiecare cifră c, de la 9 la 0, de un număr de ori egal cu frecvența sa.

Eficiența algoritmului din punct de vedere al timpului de executare constă în faptul că parcurgem o singură dată fișierul de intrare bac.in, obținând astfel un algoritm liniar în raport cu numărul de cifre din fișier. Eficiența algoritmului din punct de vedere al memoriei utilizate constă în faptul că se va folosi doar un vector de frecvențe cu 10 componente, evitând astfel memorarea tuturor celor maximum 9000000 de cifre din fișier într-un vector de caractere. Pentru o descriere coerentă a metodei se acordă 1p., iar pentru justificarea eficienței, încă 1p. În total 2p.

V5. Vom utiliza un vector de frecvențe cu 10 elemente fc pentru a contoriza aparițiile fiecărei cifre. Vom parcurge fișierul bac.incaracter cu caracter, folosind variabila c , și, în cazul în care variabila c conține o cifră, vom crește frecvența sa cu 1. Ținând cont de faptul că un număr nu poate să înceapă cu cifra 0, vom determina cel mai mic număr care se poate forma folosind cifrele tuturor numerelor din fișierul bac.in astfel: 

căutăm prima cifră nenulă cn având frecvența cel puțin egală cu 1 (sigur există această cifră deoarece numerele din fișierul bac.in sunt nenule!), o scriem în fișierul de ieșire bac.out și îi scădem frecvența cu 1;



începând cu cifra 0, scriem în fișierul de ieșire toate cifrele până la 9, fiecare cifră c fiind scrisă de un număr de ori egal cu frecvența sa fc[c].

Eficiența algoritmului din punct de vedere al timpului de executare constă în faptul că parcurgem o singură dată fișierul de intrare bac.in, obținând astfel un algoritm liniar în raport cu numărul de cifre din fișier. Eficiența algoritmului din punct de vedere al memoriei utilizate constă în faptul că se va folosi doar un vector de frecvențe cu 10 componente, evitând astfel memorarea tuturor celor maximum 9000000 de cifre din fișier într-un vector de caractere. Pentru o descriere coerentă a metodei se acordă 1p., iar pentru justificarea eficienței, încă 1p. - în total 2p.