Clasa a 7-a lecția 18 - 28 ian 2016

Lecție

Ciurul lui Eratostene utilizari

Putem utiliza ciurul lui Eratostene pentru:

• determina numarul de factori primi pentru fiecare numar <= n
• descompunerea rapida in factori primi a oricarui numar <= n

Numărul de biţi 1 într-un întreg

Cum putem calcula numărul de cifre 1 din reprezentarea în baza 2 a unui număr?

• Direct: shift and mask.
• Folosind expresia x & (x - 1).
• Cu precalculare: ţinem un vector în care elementul v[x] este numărul de biţi 1 din reprezentarea în baza 2 a lui x.
• Gîndiţi-vă la un algoritm fără vectori, dar mai rapid decît O(nr. biţi) (algoritmii discutaţi anteriori sînt O(nr. biţi).
• grupam bitii cate 2, apoi cate 4....

Exemple de probleme cu precalculare

• paisprezece: necesită precalcularea unui vector al primelor 17 numere prime, precum şi a ciurului lui Eratostene.
• intervale: necesită precalcularea ciurului lui Eratostene precum şi a sumelor parţiale ale numărului de divizori primi.
• reginald, o extindere a problemei anterioare.
• puncte5: necesită precalcularea sumelor parţiale ale unei matrice.
• extraterestri precalculare vector sume prefixe parțiale (a.k.a. șmenul lui Mars)
• extraterestri1 Mars + normalizare coordonate
• flori precalculare matrice sume prefixe parţiale (a.k.a. şmenul lui Mars 2D)
• flori1 exemplu de problemă nerezolvabilă cu precalculare 2D din lipsă de memorie

Concluzii

• Precalcularea foloseşte atunci cînd avem de răspuns la mai multe întrebări costisitoare. Aceste întrebări pot fi explicite, cerute de enunţ, sau implicite, decurgînd din metoda de rezolvare, ca la problema puncte5.
• Precalcularea poate folosi şi atunci cînd numărul de întrebări este mult mai mare decît numărul de răspunsuri posibile, caz în care putem precalcula toate răspunsurile într-un tabel înainte de a răspunde la întrebări.
• Precalcularea foloseşte o structură de date adiţională şi memorie suplimentară. Uneori putem economisi memorie folosindu-ne chiar de structura de date iniţială.

Tema

Tema 17 clasa a 7^a

• Problema paisprezece
• Problema reginald
• Problema intervale

Rezolvări aici [1]