Clasa VI/VII/VIII lecția 4 - 25 sep 2012

From Algopedia
Jump to navigationJump to search

Introducere

  • Treceţi pe codeblocks: este oficial. Găsiți kit-ul la olimpiada.info
  • Cum se indentează frumos if/else in C
  • Nu aveți voie să aveți warnings, vă pot fi fatale: declaraţi int main() si folosiţi return 0 la final. Eliminați orice alte warnings deoarece majoritatea sînt o problemă reală. Unele concursuri compilează sursa cu opriri la warnings (adică tratează warning-urile ca erori).

Temă

  • Spuneți dacă o secvență de numere este monotonă folosind un automat:
    • Mulţi aţi uitat sa transferaţi a în b. Trebuie făcut în afara automatului.
    • if-uri imbricate, vă rog.
    • Am discutat automatul și programul care rezultă.
  • Numărare cuvinte/numere:
    • Folosiți fgetc pentru citire caractere, fscanf este riscant.
    • Numărarea cuvintelor și a numerelor se face la intrarea în stare, altfel pierdeţi cuvinte (sau număraţi în plus)
    • Am discutat automatul și programul care rezultă.
  • Fracţie în notaţie zecimală:
    • Am discutat soluția, fără demonstrație, precum și programul.
  • Rezolvări aici: [1]

Lecție

Recapitularea materiei

  • Recapitulare probleme de bază:
    • Algoritmul lui Euclid pentru cmmdc. Complexitate: O(log max(a, b))
    • Numărare multiplii lui k în intervalul [a, b]. Aplicație: numărare ani bisecți între doi ani.
    • Descompunerea în factori primi. Optimizarea la
    • Calcul divizori, similar cu descompunerea în factori primi.
    • Numere palindrom (simetrice). Discuție despre algoritmul clasic care poate depăși întregul maxim.
    • Despre sortare. Sortarea prin selecție este O(n2). Quicksort este O(n log n) pe cazul mediu. Sortarea optimală este O(n log n), deci nu se poate mai bine. Am vorbit despre primul pas al quicksort: pivotarea. Aplicație: algoritmul de selecție.
    • Selecție: dat un șir de 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.

Temă

  • Diferenţiat pe clase, ONI 2012 de pe campion:
    • clasa a 6-a: cartier, medalion (matrice), numar5 (rezolvări medalion și numar5 aici [2])
    • clasa a 7-a: bile6, proiecte, zigzag
    • clasa a 8-a: alune, cuburi4, optim (rezolvare optim aici [3])
  • Trimiteți sursele la campion și apoi și mie, pe email.