Clasa VII/VIII lecția 2 - 30 sep 2014

Tema - rezolvări

Rezolvări aici [1]

Lecție

Cei care se plictisesc (cei de a 8^a poate) începeți să lucrați problemele date la baraj gimnaziu. Începem cu 2014 și descreștem.

Recapitulare materie

Secvență bitonă prin rotație

Verificare secvență bitonă prin rotație. O secvență este bitonă dacă mai întîi crește și apoi, eventual, descrește. O secvență bitonă prin rotație este o secvență care fie este bitonă, fie poate fi făcută bitonă prin rotații succesive. Problema trebuie rezolvată fără a folosi vectori, similar cu problema secvenței crescătoare prin rotație. Soluție liniară. Dacă ați înțeles algoritmul încercați-vă forțele rezolvînd problema secvență bitonă.

Elementul majoritar

Dat un vector cu n elemente să se spună dacă conține un element majoritar. Un element majoritar este un element care apare de cel puțin n/2 + 1 ori. Încercați să dați o soluție mai bună decît sortarea. Am discutat variante de algoritmi:

• Forță brută: luăm fiecare element din vector și vedem de cîte ori apare. Complexitate O(n²).
• Prin sortare: sortăm vectorul și căutăm subsecvența de elemente egale de lungime maximă. Complexitate: O(n²) cu sortare prin selecție, O(n log n) cu quicksort.
• Algoritmul optim: considerăm primul element drept candidat, iar apoi parcurgem vectorul, numărînd de cîte ori apare candidatul. De fiecare dată cînd apare un element diferit de candidat decrementăm contorul. Dacă contorul ajunge negativ repornim procedura cu elementul curent drept nou candidat. În final dacă candidatul are măcar o apariție îl verificăm de cîte ori apare în vector. Complexitate O(n).

Dacă ați înțeles algoritmul încercați-vă forțele rezolvînd problema elementul majoritar.

Problema selecției

Dat un șir de n numere și o poziție k în acel șir să se spună ce element s-ar afla pe acea poziție dacă șirul ar fi sortat. Aplicăm repetat pivotarea quicksort. Calcul aproximativ al complexității pe cazul mediu: este O(n), în loc de O(n log n) dacă am fi făcut sortare. Dacă ați înțeles algoritmul încercați-vă forțele rezolvînd problema selecție.

Paranteze

Verificare expresie cu paranteze. Se dă o expresie cu paranteze rotunde, pătrate și acolade: (), [] și {}. Ele pot să apară în orice ordine, adică și ) după ]. Să se spună dacă o expresie este corectă. Exemple: ([()[]()]())[] este corectă, ([)], )(, ([()] nu sînt corecte. Am discutat despre cazul mai simplu, în care avem doar paranteze rotunde, apoi am generalizat la cazul cu mai multe tipuri de paranteze, folosind o stivă.

Tema

Tema clasa a 7^a

• Implementați algoritmii din clasă la vianuarena: bitonă, majoritar, selecție
• Tema 2 clasa a 7^a
• Opţional: Tema de la clasa a 8^a

Rezolvări aici [2]

Tema clasa a 8^a

• Implementați algoritmii din clasă la vianuarena: bitonă, majoritar, selecție
• Tema 2 clasa a 8^a

Rezolvări aici [3]