PALMA junior
Úloha o veži z obdĺžnikov s rovnakou plochou

Autorské riešenie
[stiahni imp : py]

• Počet riešiteľov: 24 / 28 = 86 %

• Úspešnosť riešenia: 3,94 / 6 = 65,63 %

Ak chceme vykresliť vežu pozostávajúcu so všetkých možných obdĺžnikov  s rovnakým obsahom a celočíselnými dĺžkami strán, potrebujeme zistiť všetky delitele čísla určujúceho plochu obdĺžnika.

V prípade ak plocha N je prvočíslo, tak program vykreslí dva obdĺžniky so zadanými rozmermi (širkami a výškami): N × 1, 1 × N. Ak je plocha N zložené číslo, tak dostaneme aj ďalšie rozmery obdĺžnikov, napr. pre N = 24 dostaneme 8 obdĺžnikov s rozmermi: 24 × 1, 12 × 2, 8 × 3, 6 × 4, 4 × 6, 3 × 8, 2 × 12, 1 × 24.

Delitele môžeme priebežne výpočítavať bez ukladania, ale vhodnejšie bude vytvárať zoznam s tymíto deliteľmi. Funkcia na vytvorenie zoznamu deliteľov pomocou generátorovej notácie v jazyku Python by mohla vyzerať nasledovne:

def delitele(n):
    # vráti zoznam so všetkými deliteľmi zadaného čísla
    return [i for i in range(1, n + 1) if n % i == 0]

V jazyku Imagine Logo by sa táto funkcia mohla zapísať nasledovne:

viem delitele :n
; vráti zoznam so všetkými deliteľmi zadaného čísla
  urobTu "zoznam []
  preČísla "i ![1 (:n)][
    ak zvyšok :n :i = 0 [
      urobTu "zoznam vložPosledný :i :zoznam
    ]
  ]
  výsledok :zoznam
koniec

Zápisy týchto funkcii sú celkom krátke, ale pri nich zbytočne prechádzame možnými deliteľmi od 1 až po N. Istým vylepšením by bolo prechádzať od 1 až po N/2, ale ešte efektívnejšie by bolo prechádzať od 1 až po √N. Napr. pre N = 24 je zrejmé, že zbytočne prechádzame hodnotami od 13 (t.j. N/2+1) do 23 (t.j. N-1), lebo tam nemôžu byť ďalšie delitele čísla 24. A ďalej keď si lepšie všimneme zoznam rozmerov obdĺžnikov pre N = 24, zistíme, že prvé 4 prvky zoznamu sú symetrické s poslednými 4 prvkami. To nám ukazuje, že stačí prechádzať hodnotami od 1 až po √N. Ak si zoberieme napr. N = 1000000, tak v prvom prípade by sme prechádzali 1000000 hodnotami, v druhom prípade 1000000/2 = 500000 hodnotami a napokon v treťom prípade len √1000000 = 1000 hodnotami, čo je značné urýchlenie výpočtu.

Ak chceme všetky obdĺžniky tvoriace vežu mať zarovnané na stred, môžme vykresľovať jednotliví obdĺžniky zo stredu dolnej strany obdĺžnika a následne sa posunúť so zdvihnutým perom na stred obdĺžníka na nasledujúcom poschodí (pozri obrázok nižšie).

Riešenie celej úlohy v programovacom jazyku Imagine Logo môže vyzerať nasledovne:

viem delitele :n
; vráti zoznam so všetkými deliteľmi zadaného čísla
  urobTu "zoznam []
  preČísla "i ![2 (odmocnina :n)][
    ak zvyšok :n :i = 0 [
      urobTu "zoznam vložPosledný :i :zoznam
    ]
  ]
  urobTu "zoznam1 prevráť :zoznam
  ak prvý :zoznam1 * prvý :zoznam1 = :n [
    urobTu "zoznam1 bezPrvého :zoznam1
  ]
  prePrvky "cislo :zoznam1 [
    urobTu "zoznam vložPosledný :n / :cislo :zoznam   
  ]
  urobTu "zoznam vložPosledný :n :zoznam  
  urobTu "zoznam vložPrvý 1 :zoznam 
  výsledok :zoznam
koniec   	
              	            	
viem obdlznik :sirka :vyska
; vykreslí obdĺžnik so zadanou šírkou a výškou zo stredu vodorovnej strany
  dopredu :sirka / 2
  vľavo 90
  dopredu :vyska
  vľavo 90
  dopredu :sirka 
  vľavo 90
  dopredu :vyska
  vľavo 90
  dopredu :sirka / 2
koniec

viem kresli :n 
; vykreslí vežu ako zoznam obdĺžnikov, ktorého dĺžky sú deliteľmi zadaného čísla
  vpravo 90
  urobTu "zoznam_cisel delitele :n
  prePrvky "cislo :zoznam_cisel [
    obdlznik posledný :zoznam_cisel / :cislo :cislo
    peroHore
    vľavo 90
    dopredu :cislo
    vpravo 90
    peroDolu
  ] 
koniec

import turtle


def delitele(n):
    # vráti zoznam so všetkými deliteľmi zadaného čísla
    zoznam1 = [i for i in range(2, int(n ** 0.5) + 1) if n % i == 0]
    zoznam2 = [n // i for i in zoznam1[::-1] if i * i != n]
    zoznam = [1] + zoznam1 + zoznam2 + [n]
    return zoznam


def obdlznik(sirka, vyska):
    # vykreslí obdĺžnik so zadanou šírkou a výškou zo stredu vodorovnej strany
    pero.forward(sirka / 2)
    pero.left(90)
    pero.forward(vyska)
    pero.left(90)
    pero.forward(sirka)
    pero.left(90)
    pero.forward(vyska)
    pero.left(90)
    pero.forward(sirka / 2)


def kresli(n):
    # vykreslí vežu ako zoznamu obdĺžnikov, ktorého dĺžky sú deliteľmi zadaného čísla
    zoznam = delitele(n)
    for cislo in zoznam:
        obdlznik(zoznam[-1] // cislo, cislo)
        pero.penup()
        pero.left(90)
        pero.forward(cislo)
        pero.right(90)
        pero.pendown()


tabula = turtle.Screen()
pero = turtle.Turtle()

kresli(24)

tabula.mainloop()

Táto úloha je zameraná na dôslednú analýzu matematického problému, na použitie dekompozície ako stratégie riešenia problému a deliteľnosti  čísel, na precvičenie aritmetických operácii, príkazov korytnačej grafiky, cyklu, vetvenia, funkcie s parametrami a výstupom a práce s údajovým typom zoznam.

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

Do riešenia tejto úlohy sa zapojilo 15 tímov z kategórie EXPERT a 9 tímov z kategórie GURU. Jazyk Python použilo 18 súťažiacich a prostredie Imagine Logo len 6 súťažiaci. Plný počet bodov dosiahli 3 tímy (Šedá eminencia dodekedrónov, Bubak V7 Amavet a HairyElephants), ktorým gratulujeme.

Korytnačiu grafiku použilo 21 súťažiacich, karteziánsku (tkinter) len 3 súťažiaci. Len 6 súťažiacich použilo zoznam na uchovanie deliteľov zadaného čísla (obsahu obdĺžnikov). Niektorí súťažiaci navyše použili koeficient na vykreslenie násobku rozmerov obdĺžnika, aby zabezpečili názornejšie a kvalitnejšie zobrazenie veže.

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému, tvorby menej efektívneho riešenia či z pretrvajúcich programátorských zlozvykov:

• riešenie pozmenenej úlohy - nie pre rovnaké obsahy, ale rovnaké obvody obdĺžnikov,

• nezohľadnenie prípadu pre obsah obdĺžnikov rovný 1,

• pri výpočte deliteľov zbytočné prechádzanie všetkými hodnotami od 1 po N,

• riešenie úlohy zúžené len pre mocniny čísla 2,

• nepresné vykresľovanie obdĺžnikov vo veži - ich prekrývanie, resp. nezarovnanie na stred,

• použitie príkazu input vo vnútri funkcie,

• použitie nemnemonických jednopísmenkových identifikátorov premenných,

• použitie globálnych premenných namiesto lokálnych (v prostredí Imagine Logo).