PALMA junior
Úloha o riečnom hlavolame

Autorské riešenie
[stiahni py]                                       

• Počet riešiteľov: 27 / 35 = 77  %                       

• Úspešnosť riešenia:  7.14 / 8 = 89 %                   

Zo zadania úlohy sa dá rýchlo zistiť, že na brehu sú len malé a veľké korytnačky, pričom loďka unesie maximálne dve malé alebo jednu veľkú korytnačku. Je hneď zrejmé, že vstupnými parametrami bude počet malých a počet veľkých korytnačiek. Takisto je potrebné si uvedomiť, že zrejme pri niektorých hodnotách týchto parametrov riešenie existovať nebude. Z týchto dôvodov si môžeme riešenie úlohy o riečnom hlavolame rozdeliť do nasledujúcich častí:

• rozpoznanie situácií, v ktorých riešenie neexistuje,

• vyriešenie špecifických situácií,

• všeobecná časť, v ktorej sa cyklicky opakuje prenášanie malých a veľkých korytnačiek.

Pri riešení tejto úlohy sa nám ľahko môže stať, že nejakú situáciu nebudeme uvažovať alebo ju vyhodnotíme nesprávne. Jednou zo stratégií riešenia problémov je stratégia "sprav si  tabuľku". Táto stratégia nám umožní prehľadne zobraziť všetky situácie.

Ak si vykonáme analýzu niektorých konfigurácií, tak ľahko zistíme, že riešenie nebude existovať v prípade, ak na počiatočnom brehu nemáme žiadnu malú korytnačku a zároveň aspoň dve veľké korytnačky. V takomto prípade nebude mať kto preplaviť loďku na pôvodný breh tak, aby do neho mohla nastúpiť druhá korytnačka a obe tak ostali na druhej strane brehu. Takisto riešenie nebude existovať v prípade, ak je síce na počiatočnom brehu jedna malá korytnačka a zároveň aspoň jedna veľká korytnačka. V takomto prípade nebude mať opäť kto preplaviť loďku na pôvodný breh tak, aby sa na druhý breh dostala aj malá korytnačka aj veľká korytnačka.

Ďalej nás budú zaujímať špecifické situácie, v ktorých je na pôvodnom brehu len jedna malá alebo len jedna veľká korytnačka. V takom prípade nemusíme toho robiť až tak veľa, postačí nám danú korytnačku preplaviť osamote na druhý breh a úloha je vyriešená.

Takisto ak je na pôvodnom brehu nula veľkých korynačiek a ľubovoľný počet malých korytnačiek, vždy si vieme pomôcť postupným preplavením jednej malej korytnačky a zároveň bude vždy k dispozícii jedna malá korytnačka, ktorá loďku vráti spät (uvedomme si, že loďka dokáže naraz preplaviť dve malé korytnačky).

Poslednú všeobecnú časť využijeme na popis prípadu, ak na pôvodnom brehu sú aspoň dve malé korytnačky a ľubovoľný počet veľkých korytnačiek. V takom prípade si pomocou dvojice malých korytnačiek najprv prenesieme všetky veľké korytnačky a následne riešenie ukončíme preplavím sa zvyšných malých korytnačiek. Na takéto riešenie si môžeme pripraviť pomocné funkcie presun_velkej_korytnacky(), presun_malej_korytnacky(), maly_prenes_velkeho(), ktoré sme si vytvorili v nasledujúcom možnom zdrojovom kóde v jazyku Python:

Nasleduje možný zdrojový kód v jazyku Python:

# Python
def presun_velkej_korytnacky():
  print("nastup_velka")
  print("preplav")
  print("vystup_velka")     

def presun_malej_korytnacky():
  print("nastup_mala")
  print("preplav")
  print("vystup_mala")

def maly_prenes_velkeho():
  print("nastup_mala")
  print("nastup_mala")
  print("preplav")
  print("vystup_mala")
  print("preplav")
  print("vystup_mala")
  print("nastup_velka")
  print("preplav")
  print("vystup_velka")
  print("nastup_mala")
  print("preplav")


def harmonogram(pocet_malych, pocet_velkych):
  if (pocet_malych==0 and pocet_velkych==0):
    print("Nemáme nikoho na prenášanie cez rieku")
  elif (pocet_malych==0 and pocet_velkych>1) or (pocet_malych==1 and pocet_velkych>=1):
    print("Riešenie neexistuje")
  elif (pocet_malych==0 and pocet_velkych==1):
    presun_velkej_korytnacky()
  elif (pocet_malych==1 and pocet_velkych==0):
    presun_malej_korytnacky()
  elif pocet_malych > 1:
    if (pocet_velkych == 0): print("nastup_maly") 
    for i in range(pocet_velkych):
      maly_prenes_velkeho()
    for j in range(pocet_malych-1):
      presun_malej_korytnacky()
      if j!=pocet_malych-2: print("preplav")
    print("vystup_mala")

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

Úlohu riešilo 27 tímov. Väčšina tímov použila správny postup na dosiahnutie vhodného riešenia a využilo postup uvedený v autorskom riešení. Niektoré tímy si vytvorili vlastné pomocné funkcie pre opakované príkazy, iné tímy to riešili vo forme jednej funkcie harmonogram. Viaceré riešenia boli výborne okomentované. V niektorých riešeniach chýbali vstupné parametre funkcie, a teda úloha bola vyriešená len pre istý počet malých a veľkých korytnačiek. V niektorých riešeniach neboli správne ošetrené prípady, ak riešenie neexistovalo, najmä prípad harmonogram(0,1). V iných sa stávalo, že chýbalo vystúpenie poslednej malej korytnačky, alebo sa prepravovali dve malé korytnačky, ale aktuálne bola už na danej strane je jedna malá korytnačka.