(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)
În acest articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume acea de acoperire în plan. În general acest tip de probleme sunt $NP complete$, dar pentru cazurile particulare prezentate problemele sunt rezolvabile.
În acest articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume aceea de acoperire în plan. În general acest tip de probleme sunt $NP complete$, dar pentru cazurile particulare prezentate problemele sunt rezolvabile.
h3. *Problema 1* (Olimpiada de informatică, Bucureşti, etapa pe sector, 1995 şi [1])
Se dă un pătrat de latură $2$<sup>$n$</sup> care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:
Se dă un pătrat de latură $2^n^$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:
p=. !probleme-de-acoperire?OlimpBuc1.jpg!
h3. Soluţie:
* Prima întrebare care ne vine în minte este dacă aria ce trebuie acoperită este divizibilă cu $3$. Aria este $4^n^ – 1 = (4 – 1)(4^n-1^ + 4^n-2^ + … + 4 + 1)$, deci este multiplu de trei. Să trecem acum la ideea rezolvării.
* Împărţim pătratul în patru pătrate de dimensiuni egale. Unul dintre ele are un pătrat lipsă, facem ca celelalte trei pătrate să aibă şi ele un pătrat lipsă prin plasarea unei piese care sa acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase dupa cum observăm în figură.
* Prima întrebare care ne vine în minte este dacă aria ce trebuie acoperită este divizibilă cu $3$. Aria este $4^n^ – 1 = (4 – 1)(4^n-1^ + 4^n-2^ + … + 4 + 1)$, deci este multiplu de $3$. Să trecem acum la ideea rezolvării.
* Împărţim pătratul în $4$ pătrate de dimensiuni egale. Unul dintre ele are un pătrat lipsă. Facem ca celelalte trei pătrate să aibă şi ele un pătrat lipsă prin plasarea unei piese care să acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase, după cum observăm în figură.
p=. !probleme-de-acoperire?OlimpBuc2.jpg!
