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

	PALMA junior

Úloha o korytnačom desaťboji

Autorské riešenie
[stiahni]

Najpr vyriešime jednoduchšiu úlohu - nájsť tím, ktorý dosiahol najlepšie bodové skóre (tím, pre ktorý je rozdiel "dobrých" a "zlých" bodov najvyšší).

Za tím s najvyšším skóre zvolíme prvý prvok zoznamu. Index tohto prvku je 1.

urobTu "max 1

Avšak, prvý tím nemusí byť najlepším tímom. Preto postupne prejdeme cez všetky ostatné prvky zoznamu. Ak nájdeme v zozname tím, ktorý dosiahol lepšie skóre, daný tím prehlásime za najlepší. Do premennej "max potom vložíme index tohto tímu.

prePrvky "tim :zoznam [
ak (prvok 2 :tim) - (prvok 3 :tim) > (prvok 2 prvok :max :zoznam) - (prvok 3 prvok :max :zoznam) [
urobTu "max poc
]
]

Ale ako nám pomôže hľadanie najúspešnejšieho tímu pri usporiadaní tímov podľa bodového skóre? Vytvoríme si nový zoznam, do ktorého uložíme nájdené maximum. Z pôvodného zoznamu ho odstránime.

urobTu "pom vlozPosledny prvok :max :zoznam :pom
urob "zoznam bezPozicie :max :zoznam

Pokračujeme prehľadávaním pôvodného zoznamu, ktorý je kratší o jeden prvok. Takto pokračujeme, kým vstupný zoznam nie je prázdny.

Výsledná procedúra by mohla vyzerať napríklad takto:

viem usporiadaj :zoznam
;usporiadaj [["a 5 3]["b 1 4]["c 3 2]["d 4 9]["e 6 0]["f 2 9]["g 0 0]]
urobTu "pom []
kym [nieJe prazdny? :zoznam] [
   urobTu "max 1
   prePrvky "tim :zoznam [
    ak (prvok 2 :tim) - (prvok 3 :tim) > (prvok 2 prvok :max :zoznam) - (prvok 3 prvok :max :zoznam) [
     urobTu "max poc
    ]
   ]
   urobTu "pom vlozPosledny prvok :max :zoznam :pom
   urob "zoznam bezPozicie :max :zoznam
]
zo :pom
koniec

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

Zaujímavé riešenie predviedol Bali Michal. Jeho riešenie uvádzame nižšie. Ostatné tímy použili procedúru utrieď.

Riešenie tímu Bali Michal:

viem usporiadaj :vstup
;aplikoval som selection sort
urobTu "vstup1 :vstup
urobTu "start 1
urobTu "end pocet :vstup
kym [:start < :end]
   [
   urobTu "i :start
   urobTu "max (prvok 2 prvok :start :vstup) - (prvok 3 prvok :start :vstup)
   urobTu "iMax :start
   ;inicializovanie momentalne najvecsej hodnoty ako rozdiel bodov prveho prvku(pretoze netusi, ake hodnoty budu zadane)
   kym [:i <= :end]
   ;kym niesu utriedene vsetky hodnoty
    [
    ak :max < (prvok 2 prvok :i :vstup) - (prvok 3 prvok :i :vstup)
     [
     ;ak pri prechode narazil na vecsi ako mom. najvecsi, zaznamenaj to
     urobTu "max (prvok 2 prvok :i :vstup) - (prvok 3 prvok :i :vstup)
     urobTu "iMax :i
     ]
    urobTu "i :i+1
    ]
   urobTu "temp prvok :iMax :vstup
   urobTu "vstup nahrad :iMax :vstup prvok :start :vstup
   urobTu "vstup nahrad :start :vstup :temp
   ;vymena najmensieho s prvym
   urobTu "start :start+1
   ;posun hranice, za ktorou sa triedi
   ]
pis :vstup
koniec

PALMA junior

Úloha o korytnačom desaťboji