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

From Algopedia
Jump to: navigation, search

Lecție

  • Prezentarea profesorului
  • Prezentarea cercului: vom face informatică la cel mai înalt nivel. Vom include cunoștințele de olimpiadă dar nu ne vom rezuma la ele. Nu vom face dopaj.
  • Prezența, completat chestionare.
  • Exemple de jocuri care stimulează mintea: cubul rubik, scrabble flash, powerball
  • Problemă matematică: dacă 10 oameni construiesc 10 case în 15 zile, în cît timp construiesc 8 oameni 16 case? Generalizare simbolică.
  • Exemple de întrebări puzzle:
    • De ce este cerul albastru
    • De ce nu cade luna pe Pămînt
    • De ce se formează mareele

Test

Verificare cunoștințe, 8 probleme într-o oră, vezi mai jos.

Tema

Problema selecție de la test, căci nu a făcut-o nimeni: dat un vector v și o poziție k în acel vector să se afle ce număr s-ar afla pe poziția k în v dacă v ar fi sortat crescator. Încercați să găsiți o rezolvare mai rapidă decît sortarea. Nu folosiți funcții de sortare de bibliotecă.

Test cunoștințe informatică

Rezolvați cît mai multe din următoarele exerciții. Dați răspunsurile folosind un limbaj de programare sau pseudocod. Puteți considera datele deja citite și nu trebuie să faceți afișări. Scrieți strict secvența de calcul (care poate necesita citiri de date, atenție!). Pentru fiecare exercițiu rezolvat calculați complexitatea timpului de execuție (numărul de operații efectuat de algoritm în funcție de datele de intrare). Iată un exemplu de exercițiu rezolvat:


Cifra k Rezolvare
Calculați cifra k a unui număr n, numărînd cifrele de la dreapta la stînga.
while ( k > 1 ) {
  n = n / 10;
  k--;
}
cf = n % 10;

Complexitate: proporțional cu numărul de cifre al lui n

Factori primi

Afișați descompunerea în factori primi a numărului n. Exemplu: 1176 = 23 x 31 x 72

Numere cu două cifre

Spuneți dacă numărul n este format din exact două cifre repetate de oricâte ori. 23223 și 900990 sînt astfel de numere, pe cînd 593 și 44002 nu. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Putere

Calculați an în mod cît mai eficient (a și n numere naturale).

Secvență monotonă

Spuneți dacă o secvență de numere este monotonă. O secvență este monotonă dacă numerele ei sînt fie în ordine crescătoare fie în ordine descrescătoare. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Paranteze

Dată o secvență de 0 și 1, unde 0 înseamnă paranteză deschisă '(', iar 1 înseamnă paranteză închisă ')', spuneți dacă secvența reprezintă o expresie corectă de paranteze și dacă da calculați numărul maxim de paranteze una într-alta. Exemplu: 0 1 0 0 1 0 1 1 este corectă și are factorul de imbricare de 2, pe cînd secvența 0 0 0 1 1 1 0 este incorectă. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Interclasare vectori

Dați doi vectori sortați crescător construiți un al treilea vector sortat care să conțină toate elementele din cei doi vectori. Sînt permise elemente duplicat. Exemplu: dați vectorii 1 4 6 9 și 2 4 5 9 12 rezultatul este vectorul 1 2 4 4 5 6 9 9 12. Nu aveți voie să folosiți funcții de sortare din biblioteca C sau Pascal.

Ștergere element

Dat un vector v și un element e să se elimine din vector prima apariție a elementului e, în caz că acesta apare în vector. Exemplu: v = 5 9 2 7 9 3 5 7 4 si e = 9, la final v = 5 2 7 9 3 5 7 4

Selecție

Dat un vector v și o poziție k în acel vector să se afle ce număr s-ar afla pe poziția k în v dacă v ar fi sortat crescator. Încercați să găsiți o rezolvare mai rapidă decît sortarea. Nu folosiți funcții de sortare de bibliotecă.