PALMA junior
Úloha o trojtlačidlovej kalkulačke

Autorské riešenie
[stiahni [imp][py]]

• Počet riešiteľov: 1 / 1 = 100 %

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

Riešenie úlohy pozostáva z dvoch častí:

1. pre zadané prirodzené číslo určiť čo najkratšiu postupnosť klávesov, stláčaním ktorých dosiahneme toto číslo (procedúra/funkcia postupnost)
2. pre zadanú postupnosť klávesov vypočíta číslo, ktoré dostaneme na displeji po stláčaní tejto postupnosti klávesov (procedúra/funkcia vypocet)

Najprv vyriešme prvú podúlohu - určiť postupnosť klávesov pre zadané číslo. Najjednoduchším riešením by bolo stlačenie klávesu 0 a následné opakované stlačenie klávesu +1 až dokiaľ by sme nedostali zadané číslo. Počet stlačení +1 by bol rovný práve zadanému číslu. Ak použijeme aj kláves ×3, celkový počet klávesov vieme zmenšiť. Pre dosiahnutie čísla, ktoré je mocninou čísla 3 (3^K), stačí po klávese 0 stlačiť kláves +1 a po ňom K-krát kláves ×3. Napríklad číslo 9 dosiahneme postupným stlačením klávesov:
0 +1 ×3 ×3 a číslo 81 stláčaním klávesov 0 +1 ×3 ×3 ×3 ×3. Pre mocniny 3 je to najkratšia postupnosť klávesov.

Pri hľadaní riešenia tejto podúlohy pre ľubovoľné číslo môžmne postupovať od konca. Ak je zadané číslo deliteľné tromi, tak ho vydelíme tromi. Ak nie je, tak od neho odpočítame raz alebo dvakrát číslo 1 a potom vydelíme tromi. Takýmto "pažravým" spôsobom (založenom na čo najväčšom počte stlačení klávesu ×3) sa postupne dostaneme až k číslu 0. Tento postup je pre každé prirodzené číslo jednoznačný, lebo v každom kroku výpočtu nastáva práve 1 situácia (zvyšok daného čísla pri delení 3 je 0, resp. 1, resp. 2), pri ktorej sa použije práve 1 operácia (vydelenie 3, resp. odčítanie 1, resp. 2 odčítania 1). Riešením pôvodnej úlohy bude postupnosť klávesov ×3, medzi ktorými bude žiaden až dva klávesy +1. Dá sa ukázať, že počet klávesov ×3 v postupnosti je maximálne možný (pri väčšom počte klávesov ×3 by sme presiahli požadované číslo). Pri menšom počte klávesov ×3 by sme nutne museli použiť viac ako 2 klávesy +1. Každé in0 riešenie obsahujúce aspoň 3 klávesy +1 za sebou vieme skrátiť nasledovným spôsobom: ×3 +1 +1 +1   -->   +1 ×3.

Rovnakým spôsobom prevádzame prirodzené čísla z desiatkovej do trojkovej sústavy, napr:

7 = (2 × 3) + 1 = 21₃ ... postupnosť klávesov 0 +1 +1 ×3 +1

9 = ((1 × 3) × 3) = 100₃ ... postupnosť klávesov 0 +1 ×3 ×3

11 = ((1 × 3) × 3) + 2 = 102₃ ... postupnosť klávesov 0 +1 ×3 ×3 +1 +1

Celkový počet klávesov (0, +1, ×3) potrebných na vytvorenie zadaného prírodzeného čísla je rovný počtu cifier tohto čísla zapisaného v trojkovej sústave zvýšeného o ciferný súčet tohto čísla v trojkovej sústave.

Procedúra postupnost, ktorá pre zadané prirodzené číslo vytvorí postupnosť klávesov môže v jazyku Imagine Logo vyzerať napríklad takto:

Funkcia postupnost, ktorá pre zadané prirodzené číslo vytvorí postupnosť klávesov môže v jazyku Python vyzerať napríklad takto:

def postupnost(n):
    '''
    Pre zadane cislo n vypocita postupnost klavesov
    :param n:  cislo
    :type  n:  float
    :rtype: list
    '''
    tlacidla = []
    while n > 0:
        cifra = n % 3
        n = n // 3
        for i in range(0,cifra):
            tlacidla.insert(0,"+1")
        tlacidla.insert(0,"x3")
    del tlacidla[0]
    tlacidla.insert(0,"0")
    return tlacidla

V procedúre/funkcii postupnost sme vytvárali postupnosť klávesov zo zvyškov po delení tromi, ktoré sme postupne pridávali na začiatok postupnosti. Nakoniec sme zrušili z postupnosti prvý kláves ×3 a pridali kláves 0.

Riešenie 2. podúlohy zameranej na výpočet čísla podľa zadanej postupnosti klávesov je veľmi priamočiare. Procedúra vypocet môže v jazyku Imagine Logo vyzerať napríklad takto:

Funkcia vypocet môže v jazyku Python vyzerať napríklad takto:

def vypocet(t):
    '''
    Pre zadanu postupnost klavesov vypocita cislo
    :param t:  zoznam
    :type  t:  list
    :rtype: int
    '''
    hodnota = 0
    for z in t:
        if z == '+1':
            hodnota += 1
        elif z == 'x3':
            hodnota *= 3
    return hodnota

Táto súťažná úloha je zameraná na využitie stratégie "rieš problém odzadu" pri tvorbe algoritmu prevodu medzi číselnými sústavami, na precvičenie použitia procedúr s výstupom, resp. funkcií s parametrami, na precvičenie práce s príkazmi priradenia, opakovania a vetvenia.

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

Do riešenia tejto úlohy pre kategóriu GURU sa zapojil len 1 tím, ktorý úspešne vyriešil úlohu v jazyku Python.

V riešení súťažiacich sme zaregistrovali nasledovné pozitívne stránky:

• pri funkcii vypocet boli veľmi šikovným spôsobom použité regulárne výrazy,
• uvedenie alternatívneho postupu s postupnosťou začínajúcou nulou alebo bez nej,
• podrobné okomentovanie programového kódu.