PALMA junior
Úloha o rodokruhu

Autorské riešenie
[stiahni imp : py]                                       

• Počet riešiteľov: 29 / 48 = 60 %                       

• Úspešnosť riešenia:  5.24 / 6 = 87 %                   

Riešenie tejto úlohy je založené na počiatočnej analýze tvaru rodokruhu, ktorý je popísaný a znázornený v zadaní. Obrázok rodokruhu je zložený zo zadaného počtu kružníc (generácií), ktoré spĺňajú dve podmienky:

• kružnice majú rovnaký stred,
• polomer kružníc tvorí aritmetickú postupnosť (polomer každej ďalšej väčšej kružnice sa zväčšuje o pevnú konštantu v porovnaní s predchádzajúcou, menšou, kružnicou).

Počet lúčov, ktoré rozdeľujú jednotlivé medzikružia je v každej ďalšej generácii dvojnásobný (to znamená, že jednému potomkovi v prvej generácií prislúchajú dvaja rodičia v druhej generácii, štyria starí rodičia v tretej generácií, 8 parodičov, 16 praprarodičov, 32 prapraprarodičov a tak ďalej).

Každý šikovný programátor dokáže takéto kružnice vykresliť. Vykresľovanie čiar už vyzerá byť náročnejšie.

Riešenie nám môže uľahčiť postup, pri ktorom postupne prekresľujeme kruhy od najväčšieho po najmenší, pričom pri každom kruhu ho rozdelíme príslušným počtom lúčov (lúč je úsečka vedená od stredu kruhu po bod na jeho obvode). Počet lúčov pri najväčšom kruhu bude rovný n-1-tej mocnine čísla 2, ak vstupom je n generácií. Pri kreslení menšieho kruhu tak ostanú viditeľné len tie časti lúčov, ktoré zodpovedajú príslušnej generácii (medzikružiu).

Nasleduje možný zdrojový kód v jazykoch Imagine a Python

#Python
import turtle


def kresli_luce(dlzka, pocet):
    for i in range(pocet):
        pero.forward(dlzka)
        pero.backward(dlzka)
        pero.right(360 / pocet)


def rodokruh(pocet_generacii):
    polomer = pocet_generacii * 50
    pocet_casti = 2 ** (pocet_generacii - 1)
    for i in range(pocet_generacii):
        pero.dot(2 * polomer, 'black')
        pero.dot(2 * polomer - 2, 'white')
        if pocet_casti > 1:
            kresli_luce(polomer, pocet_casti)
            pocet_casti = pocet_casti // 2
            polomer = polomer - 50


pero = turtle.Turtle()
plocha = turtle.Screen()
rodokruh(5)

plocha.mainloop()

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

Úlohu riešilo 29 tímov, 9 z nich v jazyku Imagine a 20 v jazyku Python. Väčšina riešení v jazyku Imagine používalo vykreslenie zadaného počtu sústredných kružníc. Po vykreslení jednotlivých kružníc, korytnačka počas cesty po príslušnej kružnici vykresľovala úsečky, ktoré oddeľujú časti medzikružia. Vyskytlo sa aj jedno správne riešenie, v ktorom boli použité kruhy a lúče. Najčastejšie chyby v jazyku Imagine boli spôsobené zlým vykresľovaním kružníc, rôznymi stredmi kružníc, vykreslením nesprávneho počtu úsečiek.