Logo UK Logo MFF

Institute of Formal and Applied Linguistics


Charles University, Czech Republic
Faculty of Mathematics and Physics

ÚFAL
NPRG030
SIS code: 
NPRG030
Semester: 
winter
E-credits: 
5
Examination: 
Z
Instructor: 
Rudolf Rosa

Programování 1 (kruh 32)

Obsah této stránky

Jak se připojit na Zoom

  • ideálně kliknutím na následující odkaz: https://cesnet.zoom.us/j/99956265162
  • je možné se účastnit přes webový prohlížeč, ale lepší je nainstalovat si aplikaci
  • také je možné se (bez videa) připojit po telefonu vytočením jednoho z následujících čísel:
    • +420228882388,,99956265162#
    • +420239018272,,99956265162#
  • meeting ID je 999 5626 5162
  • bude-li po vás Zoom chtít heslo, pak vězte, že heslo je 1921 (aneb rok premiéry divadelní hry R.U.R.)

Konzultace

  • pravidelné konzultace probíhaly během semestru každé pondělí 19:30-20:30
  • od ukončení semestru probíhají konzultace na požádání, pokud máte zájem o konzultaci, ozvěte se mi e-mailem!
    • stejný Zoom odkaz jako na cvičení
    • netřeba se předem hlásit, prostě se přippjte, pokud se chcete na něco zeptat nebo s něčím pomoct (k domácím úkolům, ke cvičení, k přednášce...)
  • cvičení budou doplňovat interaktivní konzultace
  • konzultace je pro vás, je to ideální příležitost, když s něčím potřebujete poradit nebo pomoct, například:
    • napsal jsem tenhle kus kódu a nefunguje to, proč?
    • něčemu jsem na cvičení nerozuměl a chtěl bych to vysvětlit znova a lépe
    • mám dotaz k něčemu ze cvičení nebo z přednášky
    • mám dotaz k něčemu co nebylo na cvičení ani přednášce
    • nerozumím zadání domácího úkolu
    • rozumím zadání domácího úkolu, ale potřebuju poradit, jak ho řešit
    • mám nějakou nejasnost/otázku/problém týkající se mého studia (ne nutně předmětu Programování 1)
    • atd.
  • jednak budu vyhlašovat hromadné konzultace, které se můžete účastnit všichni
  • jednak si budeme dle potřeby domlouvat soukromé konzultace
    • napište mi mail, pokud se chcete domluvit na konzultaci
    • některým z vás občas nabídnu konzultace i sám, třeba když si všimnu, že zjevně máte nějaké problémy -- ale raději se ozvěte sami, ne vždy si ne všeho všimnu

Cvičení 2020/2021

29.9.

  • Hello world
  • programování v Pythonu přímo v prohlížeči snadno a rychle
  • pár jednoduchých věcí na úvod 
    • 5+6
    • 3*7
    • 8-2
    • 1/3
    • 5*"ptakopysk"
    • "ptakopysk" + "podivný"
    • a=5
    • b=6
    • a+b
    • zvire="ptakopysk"
    • zvire=input()
  • vzájemné seznámení
  • Visual Studio Code: https://code.visualstudio.com/
  • podmínky na zápočet: domácí úkoly, závěrečný test, zápočtový program
  • konzultace
  • komunikační kanály
  • Recodex

6.10.

  • na přednášce bylo: print, input, int, float, if-elif-else, while; operace s čísly; krokování
  • umocňovadlo: zeptá se uživatele na (celé) číslo, vypíše jeho druhou mocninu
    • úprava: pro kladné číslo vypíše jeho druhou mocninu, pro záporné číslo vypíše jeho třetí mocninu
  • jiný program: uživatele se na nic neptá, vypíše druhé mocniny čísel od 1 do 20
  • Collatz conjecture
  • hra: počítač si myslí číslo, uživatel ho hádá 
    • import random
    • cislo = random.randint(0, 20)
    • uživatel hádá, dokud se netrefí, jinak program řekne, jestli to bylo moc nebo málo
  • moje zdrojáky ze cvičení

13.10.

  • znovu a pořádně: while, if, proměnné
    • přiřazení do proměnné
      • KAM = CO
      • a = 5
      • b = 10
      • a = b
    • if podmínka: 
      • if a > 5, if a == 5, if a != 5
      • totéž i se stringy
      • kód se provede (1x), pokud podmínka platí
    • while podmínka: 
      • while a > 5, while a != 5 ...
      • kód se opakovaně provádí, pokud podmínka platí (klidně 0x, klidně ∞x)
      • tj. cyklus skončí, jakmile podmínka přestane platit
      • tj. "skonči až a bude rovno -1" znamená "prováděj dokud a není rovno -1"
  • cvičení s cykly: inventura v zoo
    • každý řádek vstupu (každý input() ) je zvíře, např::
      • tygr
      • lev
      • luskoun
      • lenochod
      • tygr
      • lev
      • orangutan
      • bobr
      • tygr
      • kanec
      • ptakopysk
      • konec
    • vstup končí slovem "konec"
    • postupně několik úloh (všichni by měli zvládnout aspoň úlohy 1-6, podle času i víc až všechny)
      1. Čtěte vstup, pro každé zvíře vypište "V zoo je zvíře"
        • tj. například pokud je na vstupu ondatra, vypište "V zoo je ondatra"
      2. Je v zoo tygr?
      3. Kolik je v zoo kusů zvířat?
      4. Kolik je v zoo tygrů?
      5. Kolik je v zoo tygrů a kolik lvů?
      6. Porovnávání zvířat trapně
        • Vždy po dvě po sobě jdoucí zvířata A B vypište "A je lepší než B"
        • např. "orangutan je lepší než bobr"
        • tj. musíte si vždy pamatovat, které zvíře máte teď i které zvíře jste měli minule (a to co máte teď se stane pro další otočku cyklu zvířetem minulým)
        • a taky pro první zvíře ještě nemůžete nic říct, nejdřív musíte načíst dvě zvířata...
        • Tip: vyřešení této úložky vám pomůže při řešení domácího úkolu.
      7. Jak je dlouhý tygr? Tygr je dlouhý 4. A ptakopysk je dlouhý 9. 
        • len("ptakopysk")
        • Vypište postupně každé zvíře v zoo a jeho délku.
      8. Jaká je celková délka všech zvířat v zoo?
      9. Jak dlouhé je nejdelší zvíře?
      10. A které to je?
      11. Porovnávání zvířat podle délek
        • Pro každá dvě po sobě jdoucí zvířata vypište, které je delší než které:
        • lev je kratší než oragnutan
        • orangutan je delší než bobr
        • bobr je stejně dlouhý jako tygr
  • pozor na Recodex, je přísný!
  • na přednášce bylo:
    • string, slices, list, in, .count(), for, range
    • print(a, b, c, sep='_', end=' ')
    • tohle jsme na cvičení moc nestihli, pověnujeme se tomu pořádně příště

20.10.

  • pořádně to co se minule nestihlo: string, list, for, range
  • moje zdrojáky ze cvičení
  • inventura v zoo pomocí listu a for-cyklu, další úlohy (měli byste stihnout aspoň 1-11)
    To jsme minule moc nestihli takže se na to koukneme pořádně až teď.
    1. Vytvořte si seznam zvířat v zoo jako list (s opakováním, některé zvíře může být víckrát).
    2. Vypište všechna zvířata.
    3. Kolik je v zoo tygrů?
    4. Vypište třetí zvíře.
    5. Vypište předposlední zvíře.
    6. Vypište prvních 10 zvířat.
    7. Vypište posledních 5 zvířat.
    8. Vypište každé druhé zvíře.
    9. Vypište všechna zvířata začínající na L.
    10. Vytvořte seznam všech zvířat začínajících na L (a nějak ho vypište).
      • Do seznamu se přídává pomocí seznam.append(zvire)
    11. Počet po sobě jdoucích zvířat od L.
      • Nechť občas po sobě následuje několik zvířat, která všechna začínají na L.
      • Meziúloha: pro každou sekvenci po sobě jdoucích zvířat od L vypište její délku.
      • Úloha: jaký je maximální počet po sobě jdoucích zvířat od L?
      • Aneb jaká je maximální délka souvislé posloupnosti zvířat začínajících na L?
      • Návodné myšlenky:
        • pokud jsem teprve začal, tak dosavadní maximální délka je 0
        • pokud aktuální zvíře nezačíná na L, tak aktuální délka posloupnosti zvířat na L je 0
        • pokud aktuální zvíře začíná na L, tak aktuální délka posloupnosti zvířat na L je o 1 vyšší než byla v předchozím kroku
        • je aktuální délka posloupnosti zvířat na L vyšší než dosavadní maximum?
        • v této úloze není nutné si pamatovat tu samotnou posloupnost zvířat, stačí si pamatovat její délku
      • Tip: vyřešení této úložky vám pomůže při řešení domácího úkolu.
    12. Vypište zvířata v maximální souvislé posloupnosti zvířat na L.
    13. Maximální počet po sobě jdoucích zvířat začínajících stejným písmenem.
    14. Vypište postupně všechna zvířata začínající na jednotlivá písmena slova dikobraz
      • ​​Pro procházení všech písmen slova můžete slovo nejdřív převést na seznam list("dikobraz")
      • Ale ani to není nutné, přes string jde i přímo iterovat for cyklem, takže stačí přímo použít 
        • for pismeno in "dikobraz":
    15. Vypište nejdřív všechna zvířata začínající na a, pak všechna začínající na b, a tak dále, až po všechna začínající na z
    16. Z důvodu koronaviru Pražská zoo zkrachovala a všechna zvířata se přesunou do Plzeňské zoo.
      • Udělejte si dva seznamy zvířat, jeden pro Prahu a jeden pro Plzeň.
      • Spojte seznamy dohromady.
    17. Vzniká nová zoo na Kladně!
      • Vezměte zase seznam zvířat v Plzni a v Praze.
      • Na Kladno půjde první třetina zvířat z Prahy a poslední třetina zvířat z Plzně.
      • Délku seznamu zjistíte len(seznam)
    18. Křížení zvířat
      • Zkřižte zvířata, která jsou vedle sebe
      • Dvě zvířata zkřížíte tak, že vezmete první půlku prvního zvířete a druhou půlku druhého zvířete
      • Např. ovce+tygr = ovgr, kapybara+velbloud = kapyloud...
    19. Obrácená úloha: pro křížence najděte jeho rodiče

27.10.

  • stručně feedback na úkol Délka maximální souvislé rostoucí podposloupnosti
    • když vás zajímá jen délka, nemusíte si pamatovat celou posloupnost
  • procvičit ještě seznamy a stringy a for cykly
    • setřídit seznam libovolnou třídící metodou (kterou si ale napíšete sami)
      • insertion sort, selection sort, chcete-li bubble sort (heap sort ještě dnes bude později)
      • vše bylo na přednášce Algoritmizace, případně si připomeňte například zde: https://youtu.be/ROalU379l3U 
      • [78, 4, 12, 56, 2, 89, 78, 45, 1, 5]
      • ["pes", "kočka", "ptakopysk", "rajka", "jeseter", "žluna", "ježek", "liška", "triceratops", "vlk", "delfín"]
      • stringy lze porovnávat stejně jako inty, porovnání je lexikografické (tzn. abecední): "liška" > "jeseter"
      • takže vaše řešení by mělo stejně dobře fungovat pro setřídění listu intů jako pro list stringů
  • hlavní téma: funkce
    • stručně projít a ukázat to hlavní o funkcích 
      • def umocni(zaklad, exponent=2):
    vysledek = zaklad**exponent
    return vysledek

cislo = 5
cislo_na_druhou = umocni(5)
print(cislo_na_druhou)

print( umocni(10) )

        print( umocni(10, 3) )

        print( umocni(zaklad=10) )

        print( umocni(zaklad=10, exponent=4) )

        print( umocni(exponent=4, zaklad=10) )

        print( umocni(10, exponent=4) )
    • co používat opatrně
      • funkce které mění to co dostaly jako vstupní argumenty (porušuje koncept "single-entry single-exit")
        • typicky by funkce měla vstupní argumenty používat read-only
        • výstup by si měla vyrobit ve vlastní proměnné (proměnných) a tu (ty) vrátit pomocí return
        • ale pokud třeba má funkce upravovat seznam, pak je neefektivní ho kvůli tomu kopírovat
          • příklad: setrid_seznam(seznam)
        • příklad: půjčíte kamarádovi fyzikální tabulky, aby si v nich něco našel, a on vám v nich přepíše vzorečky
        • příklad: půjčíte kamarádovi sešit, aby vám do něj napsal domácí úkol
    • co pokud možno NEpoužívat (kromě případu kdy k tomu máte dobrý důvod a víte co děláte)
      • definice funkce uvnitř definice funkce
        • to je zbytečně složité a navíc je to imho k ničemu
      • funkce které využívají globální parametry
        • je snesitelné je používat read-only (ale i tak je čistší je předávat přes argumenty)
        • je vysloveně nevhodné je měnit (a tam navíc snadno hrozí že to člověk naprogramuje špatně)
        • příklad: půjčíte kamarádovi tužku a on vám během psaní ještě sní svačinu
  • zadání domácího úkolu
    • implementujte aspoň jednu metodu třídění
    • pokud jich implementujete víc, dostanete bonusové body
    • v kódu definujte a následně použijte aspoň jednu funkci!
  • procvičování funkcí (breakout rooms až do konce cvičení)
    • implementujte binární haldu (třeba min-heap) v listu
      • to je prostě jen obyčejný list
      • špička či kořen haldy (minimum) je na indexu 0
      • prvek na indexu i má děti na indexech 2i+1 a 2i+2
      • každé dítě má větší hodnotu než jeho rodič
      • platná halda je například: 
        • halda = [7, 12, 10, 20, 14, 11, 13, 30, 35, 16, 15, 22]
    • implementujte haldové metody; pozor, možná tam mám chyby, držte se toho co vás učili na Algoritmizaci (anebo třeba  tohohle: https://youtu.be/Xw2D9aJRBY4) 
      • minimum(halda)
        • vrátí minimum, nemění haldu 
      • smaz_minimum(halda)
        • vrátí minimum a smaže ho (tj. mění haldu)
        • když smažu minimum, dosadím na jeho poslední prvek v haldě
        • prvek postupně "zabublávám" dovnitř do haldy: pokud je některé z jeho dětí menší, prohodím ho s jeho nejmenším dítětem, a znova a znova, až dokud nejsou obě děti větší anebo není bezdětný 
      • zbourej_haldu(halda)

        • opakovaně volá smaz_minimum(halda) dokud není smazaná celá halda (tj. mění haldu)

        • vrátí seznam minim
        • zajímavé je, že vrácené prvky jsou vzestupně setříděné, že?
        • tohle je totiž druhý krok algoritmu heapsort (prvním krokem je vybudování haldy) 
      • vloz_prvek(halda, prvek)

        • přidá prvek do haldy (tj. mění haldu)

        • prvek je přidán na první volné místo (což fikaně zajistí obyčejný append)

        • následně prvek "bublá" haldou nahoru, dokud je menší než jeho rodič 

      • postav_haldu(seznam)
        • postaví haldu ze seznamu prvků, vrací haldu
        • lze zajistit prostě opakovaným voláním funkce vloz_prvek()
        • existuje i efektivnější způsob, viz Algoritmizace
  • na přednášce taky bylo: objekty, spojové seznamy
    • to si necháme na příště
  • Pozor, váš cvičící má problém rozlišovat pojmy funkce a metoda a volně je zaměňuje!

3.11.

  • na přednášce bylo: objekty, spojové seznamy
  • jednoduché objekty a metody
    • třída Clovek
    • má jmeno
    • má metodu rekni(text)
    • má metodu pozdrav 
    • class Clovek:
    def __init__(self, jmeno):
        self.jmeno = jmeno

    def rekni(self, text):
        reknu = self.jmeno + ': ' + text
        print(reknu)
        return reknu

    def pozdrav(self):
        self.rekni("Ahoj, jsem " + self.jmeno)

rudolf = Clovek('Rudolf')
rudolf.rekni('ptakopysk')
rudolf.pozdrav() 
  • dědičnost
    • řvoun je člověk, který řekne text NAHLAS
    • sprosťák je člověk, který promluvu končí "vole"
    • anonym je člověk, který neříká své jméno
    • zapomínáč je člověk, který zapomene první půlku toho co měl říct a řekne jen druhou půlku
    • pokémon je člověk, který umí říkat jen svoje jméno (třeba tak že místo každého slova řekne svoje jméno)
    • němý je člověk, který neříká nic
    • ... 
    • class Rvoun(Clovek):
    def rekni(self, text):
        reknu = self.jmeno + ': ' + text.upper()
        print(reknu)
        return reknu

petr = Rvoun('Petr')
petr.pozdrav()
  • tichá pošta v listu
    • dám pár lidí do listu, postupně tichá pošta 
    • zprava = "Na stropě je chleba s máslem, pošli to dál."
lidi = [...]
for clovek in lidi:
    zprava = clovek.rekni(zprava)
  • tichá pošta ve spojáku
    • lidi jsou ve spojáku, každý ví kdo je po něm
    • vytvořit (postupně)
    • projít (vypsat)
    • posílat si text (s rekurzí či bez rekurze) 
    • clovek.dalsi = ...

while clovek.dalsi != None ...

def posli_to_dal(self, zprava):
    zprava = self.rekni(zprava)
    if self.dalsi != None:
        self.dalsi.posli_to_dal(zprava)
  • můj kód ze cvičení
  • příště budou i další operace se spojáky, například
    • vkládat na specifické místo
    • mazat ze spojáku

10.11.

  • dnes: Oranžový Expres (aneb další operace se spojáky, tentokrát s vlaky)
  • na přednášce byly funkce a objekty, to beru jako že už víceméně umíme
  • připravit před cvikem: spoják vlak
    • vlak je takový dobrý příklad spojového seznamu
      • vlak má jednu mašinu a 0 až N vagonů
      • mašina ví jen co je za ní za vagon (nebo že za ní žádný vagon není)
      • vagon ví, co veze, kolik toho veze, a který vagon je za ním (nebo že za ním žádný vagon není)
      • (vagon by mohl vědět i který vagon je před ním; to by pak byl obousměrný spojový seznam, to si volitelně můžete zkusit taky -- je víc práce ho udržovat, protože se musí opravovat dvakrát tolik odkazů, ale některé operace se s ním dělají o trochu pohodlněji)
    • vyrobte si definice tříd Masina a Vagon podle popisu výše
      • u každá třídy stačí když vyrobíte metodu __init__() která nastaví příslušné datové položky (ale pokud chcete, udělejte si i další metody)
      • příklad (naznačený): 
      • class Masina:
    def __init__(self, vagon_za_mnou=None):
        self.dalsi = vagon_za_mnou

class Vagon:
    def __init__(self, naklad="brambory", mnozstvi=0, za_mnou=None):
        ...
    • vyrobte si jeden vlak ("Oranžový Expres"), který bude mít aspoň 5 vagonků vezoucích různý náklad
      • vagon může vézt například uhlí, dřevo, papír, krávy nebo zrní
      • množství můžete chápat jako číslo bez zřejmého rozměru; pro krávy má asi smysl mluvit o jejich počtu, pro zrní spíš o tunách
      • stejně jako v domácím úkolu nepoužívejte žádné listy, v nějaké proměnné si udržujte pouze mašinu, a přes tu pak budete přistupovat k vagonům (můžete samozřejmě použít nějaké dočasné proměnné při vytváření vlaku, ale ty berme skutečně jako dočasné)
         
      • například: 
      • masina = Masina()
masina.dalsi = Vagon()
masina.dalsi.dalsi = Vagon("uhlí")
masina.dalsi.dalsi.dalsi = Vagon("koťátka", 3)
...
    • tímto nám vznikl takzvaný seznam "s hlavou", tedy se speciálním prvkem (mašinou), který vždy existuje a odkazuje na první skutečný prvek seznamu (první vagon)
      • seznamy s hlavou jsou výhodné, snadněji se s nimi pracuje, neboť nemusíte tak složitě ošetřovat speciální případy jako přidání prvního vagonu, přidání vagonu na začátek, odebrání prvního vagonu (tedy prvku)...
    • to prozatím stačí, dál budeme pokračovat na cvičení
  • úlohy na cviko
    • pro každou úlohu vytvořte na mašině novou metodu
      • pokud možno parametrizovatelnou, tj. výchozí hodnota metody pridej_na_zacatek může být přidat vagon vezoucí 30 ptakopysků, ale mělo by být možné pomocí parametrů přidat i vagon vezoucí něco jiného
      • metoda teoreticky buď vytvořit vagon dle zadání, ale lepší asi je, pokud ta metoda dostane už vytvořený vagon jako parametr, to se vám bude hodit v některých cvičeních
      • pro přehlednost je vhodné, pokud každá metoda bude vypisovat, co dělá
    • některé úlohy mohou být pro vás vlak nesmyslné (třeba hledat vagony kde je množství nákladu víc než 30 pokud takové nemáte), v tom případě si buď upravte vlak anebo zadání úlohy :-)
    • jsou naznačené i bonusové úlohy, které programovat nemusíte (ale pokud chcete, tak můžete); ty jsou určené spíš pro ty, kteří jsou se standardními úlohami příliš rychle hotovi a pak se nudí (a pro ostatní případně dobrovolně na doma)
    • část 1 Nádraží: přidávání a prohledávání
      • přidejte na začátek vlaku (hned za mašinu) vagón vezoucí 30 ptakopysků
        • jakou asymptotickou složitost má tato metoda?
      • přidejte na konec vlaku (za poslední vagon) vagón vezoucí 50 bublin
        • jakou asymptotickou složitost má tato metoda?
        • jak upravíte mašinu, abyste tuhle operaci zvládli v konstantním čase?
      • vypište všechny vagony, které vezou náklad v množství aspoň 10
        • bylo by hezké, kdyby člověk mohl udělat prostě print(vagon) a Python by místo něčeho jako __main__.Vagon object at 0x7fab3d588358 vypsal třeba něco jako Vagon vezouci drevo v mnozstvi 30
        • toho lze snadno dosáhnout předefinováním metody __str__(self) kterou Python používá pro přetypování objektu daného typu na string (takže ta metoda musí vracet string!)
        • hodí se taky umět nějak kombinovat stringy a proměnné
          • na to je v Pythonu několik metod, používejte libovolnou z nich
          • Rudolf nejraději používá metodu str.format(), která ve stringu nahrazuje složené závorky {} za hodnoty proměnných dodaných jako parametry 
          • naklad = 'uhlí'
mnozstvi = 10
popis = 'Vezu {} v množství {}'.format(naklad, mnozstvi)
print(popis)
# vypíše: Vezu uhlí v množství 10.
          • má to i další možnosti jako uvnitř těch složených závorek specifikovat, který parametr tam vložit, jak ho zformátovat...
      • bonusová úloha: vypište celkové množství jednotlivých typů nákladu
        • a zkuste to zase bez listů a bez dictů (jak efektivní to bude?)
      • najděte vagon s největším nákladem
      • za vagon s největším nákladem připojte nový vagón obsahující 2 policisty
        • hledání vagonu s největším nákladem neprogramujte znova; kopírování kódu je častým zdrojem chyb (a proto se mu vyhýbáme), místo toho programujeme funkce a metody tak, abychom jednou napsaný kód mohli opakovaně využít! 
      • za vagon s policisty připojte nový vagon se zlatem
      • přidejte za mašinu vagon s uhlím
      • naložte nějaké uhlí do mašiny (snižte množství uhlí ve vagonu na polovinu)
      • a zase ten vagon odeberte
      • připojte někam vagon vezoucí vodu
      • a jedeme! (bonus)
        • to programovat nemusíte
        • ale můžete, naprogramujte třeba nějakou jednoduchou textovou animaci
        • hodit se vám asi bude Pythonová funkce, která prostě jen počká zadaný čas, například 1 sekundu: 
        • import time
print(masina)
time.sleep(1)
print(masina.dalsi)

24.11.

  • pokračujeme ve spojákách z minula
    • část 2 Banditi: odebírání a přerovnávání
      • Vytvořte nový vlak ("vlak banditů"), který obsahuje jedniný vagon a v něm 5 banditů.
      • Banditi přepadli vlak! Přepojte vagon s bandity za mašinu našeho vlaku.
      • (Bonus) Banditi běhají po střeše vlaku, takže běžně obsah vagonů neovlivňují. Jinak bychom museli umožnit, aby vagon mohl obsahovat i více druhů nákladu, a přesun banditů po vlaku realizovat tím, že se vždycky odečtou z jednoho vagonu a přičtou do následujícího... To programovat nemusíte (ale případně můžete).
      • Banditi našli vagon s policisty a zabili je!
        • Najděte vagon, ve kterém jsou policisti, a nastavte v něm množství nákladu na 0 (anebo typ nákladu na "mrtví policisti"...)
      • Banditi jdou ukrást vagon se zlatem (ale nevědí, kde je, takže ho musejí nejprve najít)
        • Najděte vagon, jehož nákladem je zlato
        • Vypojte ho z vlaku (ale vlak zase spojte zpátky dohromady)
        • Vagon napojte na vlak banditů
      • Banditi zametají stopy: přepojte vagon s mrtvými policisty před vagon s vodou
        • Opět předpokládejte, že ani o jednom banditi nevědí, kde je, takže každý z těchto vagonů je nejdřív potřeba najít
        • Pozor, v jednosměrném seznamu je připojování před konkrétní vagon složitější než připojování za konkrétní vagon. Rozmyslete si, co s tím.
      • Banditi odjíždějí... Přepojte vagon s bandity zpátky na vlak banditů.
    • část 3 Druhé nádraží (tohle už jsou spíš bonusy... ale na domácí úkol jsou některé z nich dobrou průpravou)
      • Za každý vagon s množstvím nákladu více než 30 přidejte vagon s policisty v počtu odpovídajícím desetině množství nákladu
      • Najděte vagon s vodou a zdvojte ho
      • Najděte dvojice sousedních vagonů, které vezou totéž, a přeložte to do druhého z nich, první vypojte.
      • Rozdělte vlak na dva, do jednoho vlaku dejte vagony vezoucí věci od písmen A-K, do druhého ostatní (stringy jde porovnávat nejen na rovnost, ale i na větší/menší než)
      • Najděte všechny vagony s množstvím nákladu menším než 10 a přepojte je na konec vlaku se zachováním jejich pořadí (zamyslete se nad složitostí)
      • Otočte vlak, tj. přeskládejte vagonu do jiného vlaku, kde budou v opačném pořadí
        • Jakou to bude mít složitost? Zkuste to v lineárním čase (ale pochopitelně stále bez listů a podobných struktur).
      • Seřaďte vlak podle objemu nákladu od nejnižšího k nejvyššímu
        • Aneb implementujte nějaký sort nad spojovým seznamem
        • Některé sorty jsou na to vhodnější než jiné
        • Minimálně jeden ze sortů lze pohodlně implementovat i nad jednosměrným spojovým seznamem
        • Jiné sorty zase může být o hodně pohodlnější dělat nad obousměrným spojovým seznamem

1.12.

  • dnes: čtení ze souborů a psaní do souborů; dict (příště: rekurze)
  • cvičení: výpočet BMI (volitelné součásti dělejte jen pokud chcete a jen pokud máte hotový základ)
    • část 1: interaktivní výpočet BMI
      • napište jednoduchý program (který pak budeme v dalších částech cvičení upravovat)
      • program se zeptá uživatele na vstup, a to na jeho hmotnost (v kilogramech) a výšku (v metrech)
      • volitelné: přijímejte vstup v různých formátech (například s desetinnou čárkou místo desetinné tečky)
      • vypočítejte uživatelovo BMI, dle vzorečku hmotnost / výška2
      • vypište, zda má uživatel váhu v pořádku, či zda má podváhu či nadváhu
        • normální váha je při BMI 18.5 až 25, méně je podváha, více je nadváha
        • volitelně: vypište podrobnější hodnocení
        • volitelně: řekněte uživateli, jaké je pro jeho výšku rozmezí ideální váhy (např. od 85.7 kg to 98.2 kg)
        • volitelně: se znalostí průměrné hustoty lidského těla (1000 kg/m3) odhadněte objem uživatele, a spočítejte například, jaký by měl uživatel průměr a obvod, pokud by měl stejnou výšku ale tvar válce, případně jaký by měl průměr a obvod, pokud by měl tvar koule
    • část 2: načíst vstupy ze souboru
      • vstup je teď v souboru, který má na každém řádku tři informace oddělené mezerou: jméno hmotnost výška
      • soubor si vyrobte
      • načítejte postupně data ze souboru; vyberte si jednu z možností jak pracovat se souborem:
        • drzadlo = open('vstup.txt', 'r')
          for radek in drzadlo:
              polozky = radek.split()
        • with open('vstup.txt', 'r') as drzadlo:
              for ...
      • pro každý řádek spočítejte BMI člověka a vypište hodnocení na výstup
      • volitelně: spočítejte a vypište nějaké statistiky celého souboru, například průměrnou výšku, hmotnost a bmi, směrodatné odchylky, počet lidí s jednotlivými kategoriemi dle BMI, medián BMI, modus kategorie BMI...
    • část 3: vypsat výstupy do souboru
      • hodnocení jednotlivých lidí nepište na standardní výstup, ale do souboru; vyberte si jednu z možností jak pracovat se souborem:
      • zapisovadlo = open('vysledek.txt', 'w')
        ...
        print(a, b, c, file=zapisovadlo)
        ...
        zapisovadlo.close()
      • with open('vysledek.txt', 'w') as zapisovadlo:
            ...
        (zavře se samo)
      • volitelně: uživatel má možnost si zadat jména souborů (ale pokud nezadá, použije se nějaká výchozí hodnota)
      • volitelně: vytvořte i druhý soubor, kam zapíšete souhrnné statistiky
    • část 4: načíst data ze souboru, pak interaktivně odpovídat na dotazy o jednotlivých lidech
      • data o lidech ze vstupního souboru si uložte do dictu
      • klíčem je jméno, hodnotou je BMI
      • obezity = dict()
        ...
        obezity[jmeno] = hodnoceni
      • interaktivně se ptejte uživatele na jméno člověka
      • pokud člověka znáte, vypište jeho BMI a hodnocení
      • pokud ne, oznamte to
      • if klic in muj_dict:
            hodnota = muj_dict[klic]
      • volitelně: interaktivní část je ve while cyklu, v každé obrátce odpoví na jeden uživatelův dotaz na jméno
      • +volitelně: po zadání speciálního vstupu (např. "konec") vypíše souhrnné statistiky o lidech, na které se uživatel ptal, a ukončí se
      • +volitelně: v cyklu jen uživatel zadává jména, program jen potvrzuje, po ukončení speciálním vstupem vypíše výstupy do souboru

8.12.

  • dnes: rekurze
    • poznámka: reálně málokdy skutečně programujeme rekurzivně, často to nebývá nejefektivnější řešení
  • ještě předtím: zápočtové programy
    • do 15.12. navrhněte v SISu téma!
  • domácí úkol: banka
    • pamatujete si stavy bankovních účtů, podle příkazů na vstupu stavy aktualizujete a vypisujete
    • základní varianta: řešte jakkoliv
      • snadné je to s dicty (třídění nemusíte programovat, můžete použít vestavěný sort)
      • můžete si na tom ještě procvičit spojáky (v tom případě je dobré udržovat spoják setříděný)
      • pokud implementujete obě varianty, napište mi a přidělím vám až 5 bonusových bodů
    • bonusová varianta: binární vyhledávací strom
      • pro uložení stavů použijte binární vyhledávací strom (tím si zároveň budete udržovat databázi setříděnou)
      • výpis stavů je pak cvičením na procházení BVS (rozmyslete si, jestli do hloubky nebo do šířky)
      • za variantu s BVS můžete dostat až +10 bonusových bodů (napište mi až to odevzdáte)
  • co jsme možná necvičili a dnes možná může někdo potřebovat
    • kopírování seznamů (a jiných struktur, třeba dictů) 
      • list_a = [5, 6, 7]
list_b = list_a  # kopíruje jen odkaz
list_b[0] = 10   # mění tím pádem i list_a pač je to tentýž list jen pod jiným názvem
list_a[0] == 10

list_c = list_a.copy()  # (mělká) kopie listu a
list_c[1] = 12  # mění pouze list_c, nikoli list_a
list_a[1] == 6
    • list comprehension (jak hezky například převést všechny stringy v listu na inty) 
      • a = ["5", "2", "1"]
cisla = [int(x) for x in a]
print(cisla)
  • úloha 1: faktoriál (společně)
    • vytvořte funkci faktorial(n), která pro přirozené číslo n vrací n!
    • varianta bez rekurze: for-cyklus
    • varianta s rekurzí
      • pro n = 1 rovnou vrátíme 1
      • pro n > 1 vrátíme n*faktorial(n-1)
      • tj. funkce zavolá samu sebe pro n o 1 menší, a až se vrátí výsledek, vynásobí ho n a vrátí
      • je dobré si to prokrokovat a podívat se jak se zanořují volání té funkce a pak se zase vynořují
      • dobré je i tušit, jak se to vyhodnocuje
        • když dojde na volání funkce, uloží se aktuální stav výpočtu na zásobník
        • provede se funkce
        • funkce vrátí návratovou hodnotu (return)
        • ze zásobníku se obnoví předchozí stav výpočtu, na místo volání funkce se jakoby dosadí návratová hodnota
  • úloha 2: Matfyzák v obchodě (zaplacení částky mincemi) (breakouts)
    • Matfyzák nakupuje v obchodě, má nákup za celkovou cenu N (to je tedy vstup)
    • Matfyzák má nekonečně mnoho pětikorunových, dvoukorunových a korunových mincí
    • Matfyzáka zajímá, jakými všemi způsoby může částku zaplatit
    • vypište všechny možné kombinace mincí, které dávají správný součet (na pořadí nezáleží, tj. 5+2 je totéž jako 2+5)
    • řešte to pomocí rekurze!
      • tip: chci nějak zaplatit 43 Kč, tak dám třeba 5 Kč, a tím jsem to převedl na problém jak zaplatit 38 Kč
        • anebo dám 2 Kč, a pak řeším jak zaplatit 41 Kč
      • tip: vypisovat mince průběžně sami zjistíte že není dobrý nápad
        • lepší nápad je vždycky vypsat kombinaci mincí až když dojdete k 0
        • je tedy potřeba si do vnořené funkce nějak předávat seznam již použitých mincí
        • možností jak to udělat je víc, zkuste dát dohromady nějakou fungující variantu
        • a pak se případně zamyslete/zamyslíme nad efektivitou
    • v mírně zobecněné variantě dolaďte jako dobrovolný domácí úkol za bonusové body (je zadán v Recodexu)
  • úloha 3: zaplacení částky mincemi s omezenou zásobou mincí (možná to stihneme, možná ne a bude to tedy úloha navíc)
    • úprava: mincí je omezená zásoba
    • pro účely téhle úlohy si klidně "natvrdo" vytvořte nějaký dict, ve kterém budete mít uloženo, kolik máte k dispozici kterých typů mincí (anebo si vymyslete, jak to na vstupu zadat)
    • nyní je potřeba si vždy hlídat aktuální stav zásoby mincí
      • buď při rekurzivním volání předat funkci kopii stavu zásob mincí s aktuálními hodnotami
        • to je o chlup jednodušší na naprogramování, ale méně efektivní, protože se furt něco kopíruje
      • nebo to nekopírovat, používat jen jednu globální zásobu
        • při rekurzivním volání se aktualizuje zásoba odebráním použíté mince
        • a po vynoření z rekurze se tam ta použitá mince zase musí vrátit! Backtrackujeme, aneb vracíme se po vlastních stopách do předchozího stavu, tak musíme zajistit, aby ten předchozí stav seděl se vším všudy.
        • to je o chlup náročnější na naprogramování, ale výpočetně efektivnější, protože se ušetří to kopírování
      • a třeba vymyslíte i jinou variantu

15.12.

  • Cesta králem na šachovnici (délka) -- viz Recodex
    • samostatně
    • ve dvojicích
    • ve skupinkách
    • bonus (není v Recodexu): vypište též seznam políček, po kterých má král jít
       

  • Nyní již jsou zadány všechny domácí úkoly
    • Standardní počet bodů za úkoly je 120
    • Je třeba získat aspoň 80%, tj. aspoň 96 bodů
    • K získání bodů lze využít i bonusové úlohy
    • Za body nad limit 96 bodů získáváte více času na zápočtový test, v poměru 1 minutu navíc za každý bod
      • Pokud např. na zápočtový test bude 90 minut a máte v Recodexu 117 bodů, máte na test 90+(117-96) = 111 minut
  • Jak trvale přepnout Recodex do češtiny: Nastavení -- Výchozí jazyk
  • Vybrané partie Pythonu, které jsme dosud dostatečně neprocvičili (postupně, jak to budeme stíhat, možná nestihneme všechno)
    • set 
      • mnozina = {5, 20, 10}
mnozina.add(7)  # přidá
mnozina.add(10)  # nepřidá, už tam je
if 7 in mnozina: ...
mnozina.remove(10)
mnozina.union(jina_mnozina)
mnozina.intersection(jina_mnozina)
...
    • tuple 
      • dvojice = (5, 10)
trojice = (1, 2, 3)
trojice[2] == 3  # indexy jako u listů a stringů
trojice[2] = 3  # !!nelze, narozdíl od listu nelze měnit (jako str)
muj_dict[(1, 2, 3)] = "ahoj"  # je hashable, lze použít jako klíč pro dict nebo set

def moje_funkce():
  return 5, 6, 7  # lze vrátit n-tici z funkce
a, b, c = moje_funkce()  # lze rovnou načíst do proměnných
    • list of lists (případně dict of dicts, list of dicts...) 
      • a = [ [1, 2, 3],
      [4, 5, 6],
      [7, 8, 9] ]
a[1][2] == 6
for radek in a: for cislo in radek: ...
a.append([10, 11])
a[3].append(12)

22.12.

  • úložka vhodná na procvičování:
    • banka: vkládání na účty a vybírání z účtů
      • 184310459/0600 vloz 10000
      • 15006704/0300 vyber 500
    • (jiná možnost: interaktivní kalkulačka)
  • for line in sys.stdin
    • čtení ze standardního vstupu, dokud neskončí: for cyklus přes standardní vstup (podobně jako přes soubor) 
    • for radek in sys.stdin:
  polozky = radek.split()
  print(polozky[1])
    • pokud potřebuju interaktivně vložit konec vstupu (EOF), obvykle se to dělá pomocí CtrlZ nebo CtrlD, obvykle vloženém na novém řádku
  • defaultdict 
    • pocty_slov = dict()
...
if "slovo" not in pocty_slov:
    pocty_slov["slovo"] = 1
else:
    pocty_slov["slovo"] += 1

    • from collections import defaultdict
pocty_slov = defaultdict(int)
...
pocty_slov["slovo"] += 1
# pokud klíč neexistuje, vrací pro něj výchozí hodnotu, což pro int je 0

    • seznamy_jmen = defaultdict(list)
...
seznamy_jmen["R"].append("Rudolf")
# výchozí hodnota pro list je prázdný list
  • list comprehension 
    • # klasicky
texty = ['5', '8', '10', '20']
cisla = []
for text in texty:
  cisla.append( int(text) )

    • # více Pythonovsky pomocí list comprehension
texty = ['5', '8', '10', '20']
cisla = [ int(text) for text in texty ]
    • # klasicky
mocniny_sudych = []
for cislo in cisla:
  if cislo % 2 == 0:
    mocniny_sudych.append( cislo**2 )
    • # více Pythonovsky pomocí list comprehension
mocniny_sudych = [ cislo**2 for cislo in cisla if cislo % 2 == 0 ]
    • atd., může to být i celkem složité, lze i dict comprehension, lze i něco co vypadá jako tuple comprehension ale ve skutečnosti je to líně vyhodnocovaný generátor...
    • na list (a tedy i na list comprehension) jde aplikovat např. max(muj_list), sum(muj_list), muj_list.len()
      • jak spočítáte průměr z hodnot v listu?
  • výjimky 
    • try:
  něco kde může nastat chyba
except TypOčekávanéChyby:
  nespadni ale poraď si s chybou
except TypJinéOčekávanéChyby as e:
  poraď si i s touto chybou
  print(e)
except:
  poraď si s libovolnou jinou chybou
  # ale asi nejde o očekávanou chybu, takže asi je lepší spadnout
  • assert 
    • assert epsilon > 0, "Předpokládáme, že epsilon je vždy kladné!"

5.1.

  • moduly a balíčky (packages) 
    • import collections
d = collections.defaultdict()

    • from collections import defaultdict
d = defaultdict()
    • from my_other_file import MyClass
    • if __name__ == '__main__':
    • from my_directory.my_file import *
  • testování
    • můžete testovat zcela ručně, ale lepší je to s testovacími balíčky
    • pytest je jednodušší (unittest je standardnější)
    • Jak testovat ve VS Code: https://code.visualstudio.com/docs/python/testing 
    • class Scitadlo:
    def secti(a, b):
        return a + b
    • # "Ruční" testování

from scitadlo import Scitadlo

def test_jedna_dva():
    assert Scitadlo.secti(1, 2) == 3
def test_zaporne():
    assert Scitadlo.secti(1, -2) == -1

test_jedna_dva()
test_zaporne()

    • # Pytest
# Testovací skript je skript jehož jméno začíná "test_"
# Importovat pytest obvykle ani není potřeba
import pytest
from scitadlo import Scitadlo

# Test je funkce jejíž jméno začíná "test_"
def test_jedna_dva():
    # testuje se pomocí assertů
    assert Scitadlo.secti(1, 2) == 3
def test_zaporne():
    assert Scitadlo.secti(1, -2) == -1
def test_necisla():
    # takhle se testuje vyhazování výjimek
    with pytest.raises(TypeError):
        Scitadlo.secti([], {})       

    • # Unittest
# unittest vyžaduje specifické třídy a metody a dědění
import unittest
from scitadlo import Scitadlo

class Testy(unittest.TestCase):
    def test_jedna_dva(self):
        self.assertEqual(Scitadlo.secti(1, 2), 3)
    def test_zaporne(self):
        self.assertEqual(Scitadlo.secti(1, -2), -1)
    def test_necisla(self):
        with self.assertRaises(TypeError):
            Scitadlo.secti([], {})       
unittest.main()
  • tkinter (nebo jiný balíček pro grafiku, např. Kivy) 
    • from tkinter import *
hlavni_okno = Tk()
hlavni_okno.mainloop()
    • from tkinter import *

hlavni_okno = Tk()
hlavni_okno.title("Pokusná apka")
hlavni_okno.geometry('350x200')

popisek = Label(hlavni_okno, text="Ahoj světe")
popisek.pack()

def pozdrav():
    popisek.configure(text = 'Ahoj po kliknutí')
    print('Ahoj do konzole!')

tlacitko_pozdrav = Button(hlavni_okno, text="Pozdrav!", command = pozdrav)
tlacitko_pozdrav.pack()

hlavni_okno.mainloop()
    • class Karticka:
    def __init__(self, text):
        self.text = text
        self.tlacitko = Button(hlavni_okno,
                text = "KLIKNI", command = self.klik)
        self.tlacitko.pack()

    def klik(self):
        self.tlacitko.configure(text = self.text)
    • popisek = Label(hlavni_okno, text="Ptakopysk")
popisek.grid(row=0, column=1)  # místo .pack()

 

Pokyny

  • doporučený editor: Visual Studio Code (ale používejte cokoliv chcete)
  • účast je nepovinná (ale doporučená) -- pokud zvládnete snadno dělat domácí úkoly i bez účasti na cvičení, asi Vaše účast na cvičení není nutná
  • můžete používat i vlastní notebook

Požadavky na zápočet

  • domácí úkoly: aspoň 80% bodů
  • zápočtový test: aspoň 100% bodů
    • na konci semestru nebo na začátku zkouškového období
    • 75 minut, v Recodexu
    • pokud bude prezenční výuka, pak bude test na počítači v učebně, pokud ne, tak budeme na Zoomu
    • rozsah obdobný domácímu úkolu
    • 2 opravné pokusy
  • zápočtový program
    • zadání dohodnout do 15.12.
    • odevzdání doporučeno do konce zimního zkouškového, maximálně do konce března
    • nutnost osobního předvedení (fyzicky nebo přes Zoom)

Domácí úkoly

Zápočtové programy

  • Jedním z požadavků na zápočet je, aby každý z vás samostatně stvořil větší prográmek, který bude něco dělat.
    • Zadání si v tomto případě vymýšlíte sami, může to být úplně cokoliv
    • Mělo by to být něco většího než běžný domácí úkol, tak zhruba na úrovni tří domácích úkolů v jednom.
    • Můžete využívat libovolné existující knihovny a nástroje, ale musíte tam i nějakou podstatnou část naprogramovat sami.
  • Téma je nutné se mnou předem dohodnout
    • do 15.12. v SISu navrhněte téma (klidně i dřív)
      • modul Studijní mezivýsledky
      • pole "zápočťák stručně": popište, co chcete dělat (max. 50 znaků)
      • pole "zápočťák podrobně": podrobně popište, co chcete dělat (3 až 10 vět)
    • jakmile tam něco vyplníte, SIS mi pošle mail a já na to v dohledné době kouknu
      • pokud mi zadání bude připadat dobré, tak ho rovnou v SISu schválím (pokud to máte povolené, SIS vám o tom pošle mail)
      • pokud mi zadání nebude připadat dobré, napíšu vám mail a doladíme to
    • téma si pokud možno vymyslete sami
      • to co si vymyslíte sami se vám nejlíp bude líp dělat a bude vás to víc bavit
      • pokud máte vágní nápad ale nevíte jak z toho udělat splnitelné zadání, popište mi to do mailu a já něco navrhnu
    • Holan má na webu hezky zpracované návrhy na témata
    • moje nehezky zpracované návrhy
  • Na zápočťáku začněte ve vlastní zájmu dělat co nejdříve
    • zkušenost ukazuje, že když si myslíte, že to budete mít za týden, bude to trvat spíš asi tak měsíc
    • je matfyzáckým zvykem na zápoč'ťáku dělat přes Vánoční prázdniny; ale během zkouškového na to taky asi budete mít nějaký čas
  • Zápočťák vypracujte do konce března
    • ale pokud chcete zápočet z Programování do konce února (pro účely kontroly studijních povinností), vypracujte ho nejpozději do konce zkouškového (tj. do 16.2.)
    • pokud zdrojáky zabalené v ZIPu projdou omezením na velikost v SISu, nahrajte je přímo do SISu ("zápočťák: kód (ZIP archiv)"); jinak zašlete e-mailem
  • Součástí zápočťáku je také dokumentace
    • ve zdrojových kódech používejte komentáře vysvětlující co která část kódu dělá
    • pokud to dává smysl, přiložte i testovací vstupní data
    • v SISu vyplňte položku "zápočťák: dokumentace"
      • můžete dokumentaci buď vepsat přímo v SISu ("zápočťák: dokumentace (text)")
      • anebo nahrát do SISu jako soubor ("zápočťák: dokumentace (soubor)")
    • dokumentace by měla obsahovat
      • popis řešené úlohy
      • popis vstupů, výstupů, ovládání
      • popis principu řešení
      • popis použitých datových struktur a algoritmů
      • Vaše vlastní zhodnocení kvality Vašeho řešení (pokuste se být upřímní)
    • dokumentace nemusí být zbytečně detailní
      • výše vidíte 5 bodů, co by dokumentace měla obsahovat, často tedy stačí dokumentace o 5 větách
      • dokumentace by měla zachycovat vše co je důležité či zajímavé (na co jste třeba hrdí)
      • dokumentace by se měla držet na vyšší úrovní abstrakce (popisovat některé důležité objekty a třídy užívané v programu je rozumné, popisovat každou jednotlivou proměnnou rozumné není)
    • nějaké tipy jak psát dokumentaci: https://ksvi.mff.cuni.cz/~kryl/dokumentace.htm
  • Až budete mít zápočťák hotový, napište mi mail a domluvíme se na termínu osobního předvedení
    • sejdeme se v labu
    • vy mi program předvedete
    • já si ho taky vyzkouším
    • podívám se na zdrojový kód
    • pokud budu spokojen, máte tímto zápočťák splněn
    • pokud ne, dám vám program dopracovat

Nahrávání cvičení

  • pokud máte zájem o nahrávky cvičení, kontaktujte Tomáše Holana, který nahrává jakési falešné cvičení
  • skutečné cvičení kvůli GDPR nahrávat nemůžeme

Další informace

  • kromě domácích úloh vřele doporučuji následující sbírku zejména jednodušších programovacích úloh: https://codingbat.com/python
    • podobně jako v Recodexu je kód automaticky vyhodnocen
    • narozdíl od Recodexu i vidíte správné i chybné vstupy i výstupy