Clasa VII/VIII lecția 2 - 5 oct 2013

From Algopedia
Jump to navigationJump to search

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

Rezolvări aici [3]

Tema clasa a 8a

Rezolvări aici [5]