Rezolvare BAC Informatica 2009 – Varianta 61 – Subiectul al III-lea problema 4
Mai jos puteti gasi rezolvarea problemei 4 de la subiectul III din varianta 61 pentru examenul de bacalaureat din anul 2009
Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂
strchr(v, x) – v
De ce e aici -v?
Salut. In program noi avem o matrice pentru a retine frecventa aparitiilor unei perechi de vocale(f[0][0] – reprezinta frecventa aparitiilor perechii “aa”; 0 este pozitia vocalei a in vectorul v). Astfel, cand intalnim o pereche de vocale (folosind strchr), vrem sa marim frecventa acelei perechi. Deci trebuie sa gasim indexul vocalelor din pereche (x si y) in vectorul v. Stiind ca strchr ne intoarce un pointer la adresa din vectorul v a vocalei x, facem scaderea strchr(v,x) – v, pentru a gasi indexul din v la care se afla x (daca x = ‘a’, strchr(v,x) – v ar fi egal cu 0). Sper ca am explicat cum trebuie. Zi faina.
Cum ar trebui sa fie structurat punctul (a) la astfel de probleme cu eficienta? Imi puteti da un exemplu concret pentru problema asta?
Salut. O sa incerc sa-ti explic cam ce puncte ar trebui sa atingi in rezolvarea subiectului. Tin totusi sa mentionez ca baremul la acest subiect este foarte vag si nu pot asigura primirea unui punctaj maxim (nu stiu cum se va corecta), dar daca atingi punctele pe care le voi mentiona, cred ca vei primi un punctaj daca nu maxim, aproape de el. Ca structura ar trebui sa mentionezi mai intai metoda de rezolvare, adica lucrul esential din programul tau, ideea de baza. In cazul de fata, ne folosim de o structura de data (matrice) pentru a retine frecventa aparitiilor perechilor de vocale. Dupa ce o completam, lucru efectuat in acelasi timp cu citirea, gasim maximul din aceasta matrice, printr-o parcurgere si afisam elementele care au acel maxim, din alta parcurgere. Asta ar fi cu explicarea metodei. Dupa, ar trebui sa mentionezi de ce metoda este eficienta. Aici trebuie sa te axezi pe 2 lucruri: complexitate temporala si spatiala. La complexitate temporala trebuie mentionat un ordin de marime al programului tau: e linear, patratic, exponential, polinomial (in functie de datele de intrare). In cazul de fata, programul e linear in functie de datele de intrare (citim toate caracterele din input si completam matricea, dupa care nu facem decat operatii constante, pe o matrice de 4×4, nefiind nimic variabil aici). Dupa aceasta, spui cateva lucruri despre complexitatea spatiala, tot la fel in functie de datele de intrare. In cazul de fata, programul ocupa un spatiu constant in functie de datele de intrare. Aproximativ 5*sizeof(char)(de la v) + 25*sizeof(int)(de la f) + 2*sizeof(char)(de la x si y) + 3*sizeof(int)(de la i,j,max) = 119 octeti. Aceasta valoare nu depinde de input, deci compexitate constanta. Ai putea sa mai mentionezi, ca o rezolvare mai eficienta din punct de vedere al timpului e imposibila, pentru ca citirea datelor trebuie oricum facuta, indiferent de algoritm. Cam asta ar fi. Zi faina si daca mai ai intrebari nu ezita.
Salut! Am sesizat o mica problema cand am implementat programul in Codeblocks. Ideea este ca spatiile nu sunt citite , astfel se compun grupuri formate din ultima litera si prima litera a urmatorului cuvant , care se poate a fi un grup de vocale si strica rezultatul…
Salut. Am modificat. Mersi de sesizare. Spor.