Izpitno vprašanje RAČ2PRA 14400

Iz MaFiRaWiki

Vprašanje

Kako lahko tlakujemo kvadratno mrežo dimenzij 2n x 2n, ki ji manjka en kvadrat, z L tlakovci?

Odgovor

Problem rešujemo z metodo deli in vladaj.

Imamo polje P[i,j; n; x,y]:

  • točka (i,j) določi levi zgornji kvadrat polja
  • 2n je velikost polja
  • (x,y) koordinata manjkajočega kvadrata

Postopek:

  • Polje razdelimo na 4 enake dele.
  • Pogledamo v katerem razdelku se nahaja manjkajoči kvadrat.
  • Dodamo 3 kvadrate (oz. tlakovce). Po enega v razdelek, kjer nimamo manjkajočega kvadrata. Postavimo jih na mesta, kjer se stikajo razdelki.
  • Naprimer, da se manjkajoči kvadrat nahaja v četrtem razdelku. Dodamo kvadrate na mesta (i+n/2, j+n/2), (i+n/2+1, j+n/2), (i+n/2, j+n/2+1).
  • Sedaj nam vsak razdelek predstavlja problem iste vrste.
  • Ponovimo algoritem na podproblemu.
Osebna orodja