Clasa VII/VIII lecția 2 - 5 oct 2013
Tema - rezolvări
Am discutat despre soluțiile la teme.
Rezolvări aici [1]
Lecție
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. Încercați să o rezolvați 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(n2).
- Prin sortare: sortăm vectorul și căutăm subsecvența de elemente egale de lungime maximă. Complexitate: O(n2) 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 7a
- Implementați algoritmii din clasă la vianuarena: bitonă, majoritar, selecție (rezolvări aici [2])
- Rezolvați următoarele probleme date la ONI 2012, clasa a 7-a:
Rezolvări aici [3]
Tema clasa a 8a
- Implementați algoritmii din clasă la vianuarena: bitonă, majoritar, selecție (rezolvări aici [4])
- Rezolvați următoarele probleme date la ONI 2012, clasa a 8-a:
Rezolvări aici [5]