PALMA junior, súťaž pre mladých programátorov v Imagine

PALMA junior

Prírodovedecká fakulta Univerzity Pavla Jozefa Šafárika, Košice

 

Úloha o analýze snímok baktérií

Autorské riešenie
[stiahni]

  • Počet riešiteľov: 7/10 = 70%

  • Úspešnosť riešenia: 2.57/7 = 37%

Rišenie tejto úlohy si rozdelíme na niekoľko častí:

  1. budeme systematicky, bod po bode prehľadávať snímku a zapamätáme si x-ovú súradnicu najľavejšej a najpravejšej časti baktérie a y-ovú súradnicu najhornejšej a najspodnejšej časti baktérie,

  2. ak sme zistili na snímke prítomnosť baktérie, podľa zistených súradníc nakreslíme okolo nej obdĺžník.

Pri prehľadávaní celej snímky budeme postupovať systematicky, prehľadáme všetky stĺpce bodov, každý bod po bode. Budeme zisťovať, či farba práve skúmaného bodu je rôzna od bielej. Ak áno, narazili sme na časť baktérie. Vždy, keď narazíme na časť baktérie otestujeme, či je potrebne rozšíriť súradnice obdĺžnika. Na začiatku si nastavíme súradnice obdĺžnika tak, aby sme ich pri nájdení prvého bodu baktérie vedeli pozmeniť.

Napr. x-ová súradnica ľavého okraja obdĺžnika sa odvíja od najľavejšieho bodu baktérie. Hľadáme teda čo najmenšiu x-ovú súradnicu bodu baktérie. Na začiatku jej preto nastavíme nejakú veľkú hodnotu, aby sme ju mohli priebežne zmenšovať, napr. 1000. Analogicky budeme postupovať aj pri ostatných troch súradniciach.

bakteria

Začiatok procedúry lokalizuj môže vyzerať nasledovne:

viem lokalizuj
  urobTu "minX 1000
  urobTu "maxX -1000
  urobTu "minY 1000
  urobTu "maxY -1000
  urobTu "kreslit "nie

  opakuj 400 [
    opakuj 300 [
      ak farbaBodu <> "biela [
        ak xSur<:minX [urobTu "minX xSur]
        ak xSur>:maxX [urobTu "maxX xSur]
        ak ySur<:minY [urobTu "miny ySur]
        ak ySur>:maxY [urobTu "maxY ySur]
        urobTu "kreslit "ano
      ]
      do 1
    ]
    vz 300
    vp 90 do 1 vl 90
  ]
koniec

Všimnime si premennú "kreslit. Ak sme narazili na nejaký bod baktérie, jej hodnotu nastavíme na "ano. Podľa nej teda vieme, či sme na snímke nejakú baktériu našli alebo nie. Ak sme baktériu našli, obdĺžnik vykreslíme. Inak nie.

Ostáva ešte vykresliť samotný obdĺžnik. Tu si musíme uvedomiť, že v premenných "minX, "maxX, "minY, "maxY sú súradnice najkrajnejších bodov baktérie. Ak by sme obdĺžnik nakreslili na týchto súradniciach, prekreslili by sme ním krajné body baktérie. Preto súradnice rohov obĺžnika posunieme o jedna smerom von. Celá procedúra aj s vykreslením obdĺžnika môže vyzerať takto:

 

viem lokalizuj
  urobTu "minX 1000
  urobTu "maxX -1000
  urobTu "minY 1000
  urobTu "maxY -1000
  urobTu "kreslit "nie

  opakuj 400 [
    opakuj 300 [
      ak farbaBodu <> "biela [
        ak xSur<:minX [urobTu "minX xSur]
        ak xSur>:maxX [urobTu "maxX xSur]
        ak ySur<:minY [urobTu "miny ySur]
        ak ySur>:maxY [urobTu "maxY ySur]
        urobTu "kreslit "ano
      ]
      do 1
    ]
    vz 300
    vp 90 do 1 vl 90
  ]

  ak :kreslit [
    nechXYSur (:minX-1) (:minY-1)
    pd
    opakuj 2 [
      do :maxY-:minY + 2
      vp 90
      do :maxX-:minX + 2
      vp 90
    ]
    ph
  ]
koniec

Vaše zaujímavé riešenia a najčastejšie chyby

Ak potrebujeme prehľadať nejaký priestor (napr. kresliacu plochu) je výhodnejšie použiť nejaký systematický prechod týmto priestorom. Niektorí z vás sa spoľahli na náhodu a body obrazovky testovali náhodným výberom. Dôsledkom je, že niektoré body testujeme zbytočne viackrát a naviac, niektoré vôbec (ak testovanie v nejakom okamihu zastavíme).

Niektorí sa snažili korytnačku jemne pootočiť a nechať ju chodiť dookola kresliacej plochy. Pri tomto spôsobe (keďže prechádzame šikmo po radoch pixeloch) sa môže stať, že niektoré body nebudeme testovať vôbec.

Vysledný obdĺžnik treba nakresliť väčší než ako sú nájdené súradnice okraja baktérie. Inak prekreslíte jej krajné body.

Niektorí z vás zabudli ošetriť situáciu, ak sa na ploche nenachádza žiadna baktéria.

© Univerzita Pavla Jozefa Šafárika v Košiciach, Prírodovedecká fakulta, Ústav informatiky

palmaj (zavinac) upjs.sk