PALMA junior, Programovanie, ALgoritmy, MAtematika, súťaž pre mladých programátorov v Pythone

	PALMA junior

Úloha o špeciálnych číselných kódoch pre IoT

Autorské riešenie
[stiahni py]

Počet riešiteľov: 27 / 27 = 100.00 %
Úspešnosť riešenia: 4,22 / 6 = 60.32 %

Ako prvé riešenie, ktoré nás hneď napadne, je prechádzať všetkými n-cifernými číslami a zisťovať, ktoré z nich majú rovnaký zápis spredu aj zozadu a zároveň sú deliteľné 11.

Požadovaná funkcia generuj() môže vyzerať napr. nasledovne:

def generuj(pocet_cifier):
    if pocet_cifier == 1:
        return [0]
    elif pocet_cifier < 1:
        return []
    vysledok = []
    prve = 10 ** (pocet_cifier - 1)
    posledne = 10 * prve - 1
    for pocitadlo in range(prve, posledne + 1):
        if str(pocitadlo) == str(pocitadlo)[::-1] and pocitadlo % 11 == 0:
            vysledok.append(pocitadlo)
    return vysledok

V uvedenej funkcii sme očetrili hraničné prípady, keď počet cifier je rovný 1 a tiež ak počet cifier je menší ako 1.

Toto riešenie nie je efektívne, lebo prechádzame zbytočne všetkými n-cifernými číslami. Ak číslo má zapis rovnaky spredu a zozadu, stačí prejsť všetky možné čísla s polovičným počtom cifier a druhu polovicu čísla len prevrátime a pripíšeme. V prípade nepárneho počtu cifier dopočítame prostrednú cifru. Funkcia generuj() naprogramovaná pomocou tohto prístupu môže vyzerať nasledovne:

def generuj(pocet_cifier):
    if pocet_cifier == 1:
        return [0]
    elif pocet_cifier < 1:
        return []
    vysledok = []
    prve = 10 ** (pocet_cifier // 2 - 1)
    posledne = 10 * prve - 1
    for pocitadlo in range(prve, posledne + 1):
        cast_lava = str(pocitadlo)
        cast_prava = str(pocitadlo)[::-1]
        if pocet_cifier % 2 == 0:
            vysledok.append(int(cast_lava + cast_prava))
        else:
            if len(cast_lava) % 2 != 0:
                stred = int(cast_lava + str(0) + cast_prava) % 11
            else:
                stred = (11 - int(cast_lava + str(0) + cast_prava) % 11) % 11
            if stred != 10:
                vysledok.append(int(cast_lava + str(stred) + cast_prava))
    return vysledok

Pri výpočte prostrednej číslice pri nepárnom počte cifier treba ešte rozlíšiť dva prípady - ak je počet cifier prvej časti nepárny a ak je počet párny. Napr. v čísle 121 sme dopočítali prostrednú cifru 2, ale pri čísle 10901 sme dopočítali prostrednú cifru 9.

Pre lepšiu predstavu porovnania neefektívneho prvého riešenia s druhý riešení môžeme uviesť niekoľko faktov:

pri prvom riešení sme pre n=9 prechádzali 900000000 čísel (od 100000000 až do 999999999) za dobu cca 240 s
pri druhom riešení sme pre n=9 prechádzali len 9000 čísel (od 1000 až do 9999) za dobu cca 0,007 s

Táto úloha je zameraná na:

použitie stratégie riešenia problémov - dekompozícia problému na podproblémy,
precvičenie príkazov volania funkcií s parametrami s výstupom, cyklu for, vetvenia, prácu so zoznamom, matematickú operáciu zvyšok po celočíselnom delení, funkcie na konverziu medzi dátovými typmi str a int..

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

Do riešenia úlohy sa zapojilo 27 tímov z kategórie GURU. Plný počet bodov za svoje riešenie dosiahli 3 tímy oliverseman, sigma a cestoviny bez posypky s posypkou, ktorým srdečne gratulujeme.

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému:

neefektívne riešenie, pri ktorom sa prechádza všetkými n-cifernými číslami,
nezohľadnenie prípadu pre jednociferné čísla,
vyriešenie úlohy len pre čísla s párnym počtom cifier,
v riešení boli uvedené aj čísla s menším počtom cifier,
v riešení pre nepárny počet cifier sa namiesto čísla 0 vkladalo číslo 11,
vo funkcii namiesto vrátenia výsledku (zoznamu čísel) jeho vypisovanie,
zmena zadania, v ktorom sa vypisujú náhodné čísla s požadovanými vlastnosťami s náhodným počtom cifier, resp. len dvojciferné čísla.

PALMA junior

Úloha o špeciálnych číselných kódoch pre IoT