PALMA junior
Úloha o stavbe pyramíd

Autorské riešenie
[stiahni [py1, py2]                                       

• Počet riešiteľov: 14 / 18 =  78 %                       

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

V tejto úlohe potrebujeme rozhodnúť, či zadaný počet kociek vieme rozdeliť na dve časti tak, aby sa z každej z nich dala postaviť kompletná pyramída, pričom použijeme všetky kocky z danej časti.

Pri riešení tejto úlohy môžeme zvoliť viacero prístupov.

1. prístup

Najprv si zistíme, ktoré počty kociek tvoria kompletné pyramídy - označme si ich ako pyramídové čísla. Nebudeme uvažovať všetky možnosti. Stačí tie, pri ktorých celkový počet kociek v pyramíde je menší, ako skúmaný počet. Pyramída s počtom poschodí 1 má len 1 stavebný prvok, pyramída s počtom poschodí 2 má 2+1=3 stavebné prvky. Takto môžeme pokračovať ďalej a jednotlivé pyramídové čísla si postupne pamätáme.

Potom postupne prechádzame cez všetky pyramídové čísla a zisťujeme, či sa rozdiel zadaného čísla a aktuálneho pyramídového čísla tiež nachádza medzi pyramídovými číslami. Ak je to tak, znamená to, že z daného počtu stavebných prvkov vieme vytvoriť 2 kompletné pyramídy tak, že sa nič nezvýši. Ak také číslo nenájdeme, zo zadaného počtu sa nedajú postaviť dve pyramídy bez zvyšku. Výsledná funkcia môže vyzerať nasledovne:

#Python
def je_mozna_stavba(pocet):
    pyramidove_cisla = []
    pocet_v_pyramide = 1
    i = 1

    while pocet_v_pyramide < pocet:
        pyramidove_cisla.append(pocet_v_pyramide)
        i = i + 1
        pocet_v_pyramide = pocet_v_pyramide + i

    for i in pyramidove_cisla:
        if (pocet - i) in pyramidove_cisla:
            return True
    return False

2. prístup

Z prvého prístupu vieme, že pyramídové čísla vieme postupne vypočítavať. Ak by sme vedeli rozhodnúť, či nejaké číslo je pyramídové, nemuseli by sme vopred pyramídové čísla počítať, pretože:

• Tieto čísla zaberajú zbytočne pamäť.

• Ak už na začiatku nájdeme nejaké vhodné rozdelenie, zvyšné čísla sme počítali zbytočne.

Pozrime sa na to, či vieme o nejakom čísle rozhodnúť, či je pyramídové alebo nie. Pyramídové číslo je súčtom čísiel 1 + 2 + 3 + 4 + ... Čísla 1, 2, 3, 4, ... tvoria aritmetickú postupnosť, ktorej súčet je:

n * (n + 1) / 2,

kde n je počet čísel. Ak chceme overiť či nejaké číslo je pyramídové, rovnica:

n * (n + 1) / 2 = cislo

by mala mať prirodzené riešenie. Po úpravách dostaneme:

n * (n + 1) / 2 = cislo
(n²  + n) / 2 = cislo
n² + n = cislo * 2
n² + n - 2 * cislo = 0
n_1,2 = (-1 ± odmocnina(1 + 8 * cislo)) / 2

Navyše, my hľadáme prirodzené riešenie rovnice. Čitateľ so znamienkom - pred odmocninou by bol určite záporný. Stačí nám teda uvažovať riešenie v tvare:

n = (-1 + odmocnina(1 + 8 * cislo)) / 2

a zistiť, či je toto riešenie prirodzené.

Generujme si postupne pyramídové čísla (od najmenšieho, t.j. od 1) a zisťujme, či aj pocet - vygenerované pyramídové číslo je tiež pyramídové číslo. Ak áno, tak zo zadaného počtu kociek vieme postaviť dve pyramídy bez zvyšku.

Zamyslime sa ešte nad tým, ktoré pyramídové čísla treba generovať. V prvom prípade sme generovali všetky menšie ako zadaný počet. Tu nám stačí generovať po pocet / 2 vrátane. Ak prvé pyramídové číslo je pred polovicou zadaného počtu, druhé musí byť za ňou. Výsledné riešenie môže vyzerať nasledovne:

#Python
def je_pyramidove(cislo):
    riesenie = (-1 + (1 + 8 * cislo) ** 0.5) / 2
    return riesenie == int(riesenie)


def je_mozna_stavba1(pocet):
    pyramidove_cislo_1 = 1
    i = 1
    while pyramidove_cislo_1 <= pocet / 2:
        cislo_2 = pocet - pyramidove_cislo_1
        if je_pyramidove(cislo_2):
            return True
        i = i + 1
        pyramidove_cislo_1 = pyramidove_cislo_1 + i
    return False 

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

Častou chybou bolo nesprávne pochopenie úlohy (alebo úmyselné zľahčenie?) a následné zisťovanie, či je možné stavebné prvky rozdeliť na 2 časti tak, aby z nich vznikli 2 rovnako veľké kompletné pyramídy.

Jedným zo zlozvykov je aj vypisovanie výstupu funkcie v rôznom tvare, napríklad veta popisujúca ne/možnosť takého rozdelenia, popis počtov stavebných prvkov v pyramídach, či vypísanie hodnoty True/False.

Ďalším zlozvykom je hľadať názvy premenných len medzi písmenami abecedy, potom máme premenné a, b, c, d, aťď. a riešenie sa preto stáva ťažko čitateľným nielen pre hodnotiteľa, ale po nejakom čase určite aj pre samotného riešiteľa. Preto je vhodné používať vhodné názvy, pomenovať premennú podľa toho, akú hodnotu uchováva, hoci aj viacslovne.