[python] Re: matematická olympiáda - P (programování)

[Zdeněk Böhm]

Jan Kara wrote:
>> ...Hlavnim cilem programatorske olympiady neni cvicit programovani v tom
ci onom programovacim jazyce.... Druhou (vyhodou), a tu povazuji za tu
hlavni, je to, ze
tyto jazyky (C, C++, Pascal) neposkytuji prilis "pokrocilych" konstrukci
(coz je prave
to, proc ty bys Python chtel pouzivat ;)...

Dobry den.
Rozhodne s vami nesouhlasim:

Tak za prve:
Programovaci jazyk neni dulezity jen pokud prave vymyslite algoritmus.
Myslim tim to, ze teoreticky, abstraktne, dumate nad tim jak to udelat.
Jenze v momente, kdy ten algoritmus chcete implementovat je uz prog.jazyk
dulezity. A vy v zadani pozadujete, aby ulohy P-I-1, P-I-2 a P-I-3 byly v
odladenem programu! A jeste navic chcete posuzovat casove a pametove naroky
programu!!! Je-li vasim cilem procvicovani "algoritmickeho" mysleni, tak tam
zadne takove pozadavky nemaji co delat.

Za druhe:
To, ze C, Pascal a ostatní neposkytuji "pokrocile" funkce je naopak jejich
nevyhoda. Zeptejte se soutezicich, jak dlouho jim trvalo vymysleni algoritmu
a jak dlouho jim trvala implementace. Vsadim se, ze to psali a ladili
desetkrat dele, nez to vymysleli.
A tady prave vystupuje napovrch bajecna jednoduchost Pythonu. Nestarate se
deklarace, o alokaci pameti, nesilite ze zadnych ukazatelu. Vymyslet
algoritmus musite stejne jako v C nebo Pascalu. Ale na to, ze algoritmus
nefunguje nebo ze ma chybu prijdete v Pythonu daleko rychleji, protoze jej
rychleji napisete :-)

Za treti:
V praxi je vecinou vice dulezite, za jak dlouho bude program hotov (funkcni
a uveden do provozu), nez kolik casu mu zabere vykonani ulohy. Proto my
(uspesni programatori :-) pracujeme v Pythonu.

Napsal jsem ulohu "P-I-1 Prádelna" v Pythonu, abyste videl, ze z hlediska
algoritmu se v nem pouzitim nejakeho modulu nic osidit neda a taky pro
srovnani slozitosti zapisu s ostatnimi prog. jazyky:

#!/usr/bin/python
# --- zadani ---------------------------
zakaznici = (
    (1000,1000),
    (1900,900),
    (1500,700),
    (2000,500)
        )
pocet_zakazniku = len(zakaznici)
# --- vypocet ---------------------------
pracky = []
ANO = 1
NE  = 0
for cislo_zakaznika in range(len(zakaznici)):
    # pro kazdeho zakaznika se hleda volna pracka
    od = zakaznici[cislo_zakaznika][0]
    do = od + zakaznici[cislo_zakaznika][1]
    vsechny_pracky_jsou_obsazeny = ANO
    for pracka in pracky:
        # u kazde pracky se zjisti, je-li volna
        pracka_je_obsazena = NE
        for cislo_v_pracce,obsazeno_od,obsazeno_do in pracka:
            # pro vsechny terminy konkretni pracky
            if do > obsazeno_od and od < obsazeno_do:
                # zakaznikuv termin se kryje s jinym v pracce
                pracka_je_obsazena = ANO
                break
        if not pracka_je_obsazena:
            # pracka neni obsazena, pridame do ni zakaznika
            pracka.append( (cislo_zakaznika,od,do) )
            vsechny_pracky_jsou_obsazeny = NE
            break
    if vsechny_pracky_jsou_obsazeny:
        # vsechny pracky jsou obsazeny, pridame dalsi pracku
        pracky.append( [(cislo_zakaznika,od,do)] )
# --- vytiskneme vysledek ---------------------------
print len(pracky) # pocet pracek, ktere budeme potrebovat
for cislo_zakaznika in range(len(zakaznici)):
    cislo_pracky_zakaznika=0
    for cislo_pracky in range(len(pracky)):
        for cislo_v_pracce,od,do in pracky[cislo_pracky]:
            if cislo_zakaznika == cislo_v_pracce:
                cislo_pracky_zakaznika = cislo_pracky+1
                break
        if cislo_pracky_zakaznika:
            print cislo_pracky_zakaznika # cislo pracky, kterou zakaznik
pouzije
            break
#--- konec programu ---

S pozdravem
Z.Böhm