Clasa VII/VIII lecția 15 - 13 ian 2015

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

Precalculare

Precalcularea este un termen general pentru folosirea unor structuri auxiliare de date, fără o legătură directă cu problema de rezolvat, care ne ajută în rezolvarea problemei. Aceste structuri de date sînt calculate la început, ceea ce duce la denumire: precalculare.

În continuare vom vorbi despre cîteva exemple clasice de precalculare.

Ciurul lui Eratostene

V-aţi gîndit vreodată că ciurul lui Eratostene este de fapt o precalculare a unui vector de frecvenţă f[], care, pentru fiecare număr p, calculează f[p] care ne spune dacă p este prim? Avem cele doua variante, cea originală:

for ( d = 2; d < n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d + d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Există desigur şi varianta cu două optimizări:

  1. În a doua buclă for variabila i ia valorile 2∙d, 3∙d, 4∙d, ..., k∙d. Pentru k < d toate valorile de forma k∙d au fost deja tăiate de valorile k anterioare, drept pentru care nu are rost să le mai parcurgem. Putem să pornim cu i de la d∙d.
  2. Conform observației anterioare i pornește de la d∙d. De aceea nu are rost să mergem cu d mai departe de sqrt(n), deoarece nu vom mai găsi i astfel încît i ≤ n.

Implementarea optimizată:

for ( d = 2; d * d <= n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Şi acum surpriza: complexitatea ciurului lui Eratostene este O(n log log n) în ambele variante. Optimizările nu schimbă complexitatea algoritmului. Desigur că ele schimbă constanta, motiv pentru care le şi facem.

Numărul de divizori primi ai numerelor pînă la n

Ciurul lui Eratostene poate fi extins să calculeze numărul de divizori primi ai fiecărui număr din vectorul de frecvență. Modificarea este uşoară: vom folosi prima variantă, neoptimizată, şi în loc să marcăm cu 1 numerele neprime, vom aduna 1, marcînd faptul că acel număr prim divide numărul neprim.

Suma între i şi j

În multe probleme apare următoarea subproblemă: avem un vector de n elemente întregi, să se răspundă la multe întrebări de forma care este suma elementelor vectorului între poziţiile i şi j?. În acest caz vom precalcula o structură de date auxiliară, şi anume un vector s, astfel încît s[i] este suma elementelor de la 0 pînă la i. El se mai numeşte şi vectorul sumei prefixelor lui v. Construcția acestui vector se poate face liniar deoarece avem relaţia s[i] = s[i-1] + v[i].

Odată calculat acest vector putem răspunde în timp constant la întrebări. Suma elementelor între i şi j este s[j] - s[i-1]. Memoria folosită este O(n).

Suma între (i, j) şi (ii, jj)

Este problema anterioară extinsă la matrice: avem o matrice de numere întregi şi întrebări de forma: care este suma elementelor matricei în dreptunghiul care are drept colţuri opuse (i1, j1) şi (i2, j2)?. Această problemă apare în problema puncte5 dată la barajul de gimnaziu în 2012. În mod similar vom precalcula o matrice auxiliară cu suma elementelor matricei originale între (0, 0) şi (i, j). Ea poate fi calculată în timp constant per element, astfel:

Calcul matrice sume parțiale în dreptunghiuri care pornesc în origine

s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + m[i][j]

Odată calculată matricea s putem răspunde în timp constant la întrebări. Suma elementelor între (i, j) şi (ii, jj) este:

S = s[ii][jj] - s[ii][j-1] - s[i-1][jj] + s[i-1][j-1]

Calcul suma numerelor în orice dreptunghi

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).

Sume de intervale

Se dă un vector cu n elemente, iniţial zero. O operaţiune pe acest vector constă în incrementarea fiecărui element între indicii i şi j. Se dau, de asemenea, m operaţiuni de executat. Să se afişeze valorile finale ale vectorului.

Soluţia forţă brută implică execuţia celor m operaţiuni. O operaţiune constă în incrementarea a maxim n elemente din vector, deci avem n x m operaţii, plus afişarea elementelor finale. Complexitatea totală este O(mn).

Se poate mai bine? Putem optimiza timpul unei operaţiuni. Ideea este următoarea: în loc să incrementăm pe rînd elementele vectorului, am putea să le grupăm. Pentru aceasta vom întîrzia incrementarea, marcînd doar locurile unde trebuie să adunăm.

Cu alte cuvinte: am putea considera intervalele ca pe nişte paranteze aşezate pe o dreaptă. O paranteză deschisă înseamnă că de acum înainte trebuie să adunăm 1 la toate elementele care urmează. O paranteză închisă înseamnă că ne putem opri din adunat 1. Să presupunem că nu avem capete de interval suprapuse. Atunci am putea memora parantezele într-un vector separat. Vom memora 1 pentru o paranteză deschisă, -1 pentru o paranteză închisă şi 0 în caz că nu avem nici un capăt de interval în acel element.

Ipoteză: vectorul de sume parţiale ale acestui vector constituie chiar rezolvarea problemei. Să observăm ce se întîmplă atunci cînd adunăm s[i] = s[i] + s[i-1]: la început avem elemente zero. Cînd deschidem o paranteză acel element devine 1. Următoarele sume parţiale vor fi şi ele tot 1, pînă dăm de un alt capăt de interval. Să presupunem că mai deschidem o paranteză. Atunci suma va deveni 2 şi ea se va propaga în continuare pe elemente zero. Apoi să presupunem că se închide o paranteză. Adunînd -1 suma devine iarăşi 1, care se va propaga în continuare.

Funcţionează acest algoritm dacă avem capete de interval suprapuse? Da, cu condiţia ca elementul în care se suprapun capete să fie suma acelor capete, adică o sumă de 1 şi -1. Aceasta înseamnă că atunci cînd generăm vectorul de paranteze nu vom scrie s[i] = 1 ci s[i]++ (la fel şi pentru -1, vom decrementa).

Generalizare 1: putem generaliza această metodă pentru problema în care intervalele nu adună 1, ci orice număr, constant pe parcursul intervalului. Cum generalizăm? O paranteză deschisă nu va aduna 1 ci constanta respectivă.

Generalizare 2: dar dacă vectorul iniţial are valori diferite de zero? În acest caz vom calcula un vector separat, iniţializat cu zero, pe care facem calculul sumelor parţiale. Acest vector ne va spune cu cît s-a mărit fiecare element zero. În final vom aduna acest vector de sume parţiale la vectorul iniţial.

Acesta exemplu de precalculare, este cunoscut printre unii din voi drept "șmenul lui Mars", denumire care îmi displace deoarece sugerează că informatica este o colecție de șmenuri.

Cînd nu funcţionează această soluţie? Atunci cînd nu avem vector iniţial (elementele sînt toate zero), iar coordonatele intervalelor sînt prea mari pentru ca vectorul de sume parţiale să încapă în memorie. Să presupunem că ni se cere numărul maxim din vectorul de sume parţiale. În acest caz există o soluţie alternativă, mai generală (în sensul în care rezolvă o clasă mai mare de probleme cu intervale), care nu folosește precalculare: putem memora capetele de intervale, pe care apoi le ordonăm crescător, ţinînd minte de ce tip sînt, închis sau deschis. Apoi le parcurgem în ordine, calculînd sumele parţiale fără să le stocăm. Suma parţială maximă este răspunsul cerut.

Desigur că atunci cînd vectorul încape în memorie, e mai uşoară precalcularea. Acest tip de precalculare se poate extinde în două dimensiuni, pe matrice: se dau m dreptunghiuri care adună 1 la toate elementele respective dintr-o matrice. Această precalculare necesită O(n2) memorie. Ea nu se justifică decît în măsura în care este facil de programat, deoarece avem o soluție de aceeași complexitate care folosește varianta pe vector, folosind doar O(n) memorie.

Exemple de probleme cu precalculare

  • paisprezece: necesită un vector predefinit ce păstrează primele 7 numere prime, precum şi precalcularea 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

Clasa a 7a

Atenţie: cine rezolvă tema opţională va rezolva automat şi tema obligatorie, deoarece problemele sînt aceleaşi, cu restriţii mai dure. Răspunsurile la tema opţională rezolvă şi tema obligatorie (cu schimbarea numelor fişierelor de intrare/ieşire, desigur).

Tema 15 clasa a 7a

Opţional: Tema 15 opţională clasa a 7a

Rezolvări aici [2]

Clasa a 8a

Tema 15 clasa a 8a

  • Problema zona dată la OJI 2013 clasa a 10a
  • Problema bizar