PALMA junior
Úloha o ťažisku úsečkovníka

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 6 / 10 = 60 %

• Úspešnosť riešenia: 5.66 / 8 = 71 %

Úloha spočíva v spracovaní zadaného zoznamu kresliacich inštrukcií v štýle korytnačej grafiky, pomocou ktorých sa generuje 2D útvar. Kreslenie sa začína v bode (0,0) a smeruje vertikálne nahor. Cieľom je vypočítať ťažisko vytvoreného útvaru. Každá úsečka má hmotnosť rovnakú ako jej dĺžku a za svoj stred (ťažisko) sa považuje jej geometrický stred.

1. Získanie segmentov (funkcia vytvor_zoznam_segmentov):

Zoznam inštrukcií má rekurzívnu štruktúru a každá položka vo formáte [uhol, vzdialenosť, podpríkaz1, podpríkaz2, ...] sa interpretuje nasledovne:

• uhol: relatívna zmena smeru v stupňoch (kladné znamená vpravo, záporné znamená vľavo),
• vzdialenosť: dĺžka úsečky, ktorú korytnačka nakreslí v danom smere,
• podpríkazy: zoznamy rovnakého typu, ktoré sa kreslia z koncového bodu aktuálnej úsečky (vetvenie).

Príklad: Zadaný zoznam

 [0, 100, [-45, 50], [45, 50, [-30, 25], [30, 25]], [30, 50]] 

sa interpretuje nasledovne:

1. Korytnačka sa otočí o 0°, teda nemení smer, a nakreslí úsečku dĺžky 100, to je hlavný "kmeň" obrázku (zvislá úsečka smerom nahor).
2. Na konci tejto úsečky vznikajú tri vetvy:
• [-45, 50], teda úsečka odbočujúca doľava pod uhlom 45° (ľavá vetva v obrázku),
• [45, 50, [-30, 25], [30, 25]], teda úsečka doprava pod uhlom 45°, ktorá sa ďalej vetví na dve menšie úsečky:
  • [-30, 25], teda doľava (vnútorná vetva),
  • [30, 25], teda doprava (pravá vonkajšia vetva).
• [30, 50], teda samostatná vetva smerom doprava o 30° (najnižšia pravá vetva).

Z každej z týchto vetiev sa zaznamená jeden alebo viac segmentov (dĺžka a stred úsečky). Rekurzívna funkcia ich prechádza hĺbkovo a zbiera do zoznamu segmentov, ktorý sa následne použije na výpočet ťažiska.

2. Výpočet ťažiska (funkcia vypocet_taziska):

Po vytvorení zoznamu segmentov, ktorý obsahuje dvojice [dĺžka, [x, y]], sa vypočíta vážený priemer všetkých stredov. Každý segment prispieva do výpočtu pomerom svojej dĺžky (hmotnosti), tzn. dlhšie segmenty "ťahajú" výsledné ťažisko viac svojím smerom.

Výsledkom je súradnicový bod (tx, ty), ktorý reprezentuje ťažisko celého útvaru.

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

def vytvor_zoznam_segmentov(zoznam):
    vysledok = []
    zaciatok = turtle.position()
    turtle.right(zoznam[0])
    turtle.forward(zoznam[1])
    koniec = turtle.position()
    stred = [(zaciatok[0] + koniec[0]) / 2, (zaciatok[1] + koniec[1]) / 2]
    vysledok.append([zoznam[1], stred])
    for idx in range(2, len(zoznam)):
        vysledok.extend(vytvor_zoznam_segmentov(zoznam[idx]))
    turtle.forward(-zoznam[1])
    turtle.right(-zoznam[0])
    return vysledok


def vypocet_taziska(usecky):
    suradnice_x = [usecka[1][0] for usecka in usecky]
    suradnice_y = [usecka[1][1] for usecka in usecky]
    vahy = [usecka[0] for usecka in usecky]
    celkova_vaha = sum(vahy)
    tx = sum(x * vaha for x, vaha in zip(suradnice_x, vahy)) / celkova_vaha
    ty = sum(y * vaha for y, vaha in zip(suradnice_y, vahy)) / celkova_vaha
    return tx, ty

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

• Niektoré riešenia správne používali vážený priemer, ale zanedbali Y-ovú súradnicu alebo nesprávne manipulovali so stavom (napr. globálne premenné, modifikácia pozície na mieste).
• Pri nesprávnom zaokrúhľovaní sa zhoršila presnosť výpočtov. Odporúčame zaokrúhľovať až na konci a výpočty robiť s `float` hodnotami.
• Viacerí riešitelia mali správne rozdelené funkcie na rekurzívne spracovanie zoznamov, ale kombinovali váhy nekorektným spôsobom alebo nevrátili správne stredy úsečiek.