====== Cvičení 8, Fronta, zásobník ====== ===== náplň cvičení ===== ==== Úkol 1 Inverzní permutace ==== * Pokud pole o délce $N$, obsahuje všechna čísla od $0$ do $N-1$ právě jednou, pak toto pole kóduje permutaci tak, že první prvek se zobrazí na místo, kde se v poli nachází $0$, druhý prvek na místo, kde se v poli nachází $1$, atd. * Pole ''[0, 1, 2, 3]'' kóduje identickou, tzv. jednotkovou, permutaci o čtyřech prvcích, * Pole ''[3, 2, 1, 0]'' kóduje otočení prvků v poli. * Napište program, který načte z jednoho řádku standardního vstupu vektor reprezentující permutaci a najde a vytiskne inverzní permutaci, tj. permutaci, která převede zadanou permutaci na jednotkovou. * Inverzní permutace k permutaci ''[2, 0, 1]'', je permutace ''[1, 2, 0]'', neboť první permutace zobrazí 0->2 a druhá permutace 2->0, obdobně 1->0, druhá permutace 0->1; první 2->1 a druhá 1->2. ==== Úkol 2: třídění karet ==== Uvažujme [[ https://en.wikipedia.org/wiki/Playing_card#/media/File:Svg-cards-2.0.svg | hrací karty ]]. * Máme karty čtyř barev, každá barva má dále karty 2,3,4,5,6,7,8,9,10,J,Q,K,A * Kartu budeme reprezentovat 1D polem, kde: * první prvek je barva karty (0,1,2,3). Tento prvek bude ''int'' * druhý prvek je typu ''string'' a je to hodnota karty, tedy např. "Q" nebo "1" * Příklad karty: ''[1,"2"], [2,"A"], [0,"K"]'' * Pořadí karet v dané barvě je toto: 2,3,4,5,6,7,8,9,10,J,Q,K,A, kde * 2 má nejmenší hodnotu * A má největší hodnotu * platí že $2<3$, $3<4$, ... Q $<$ K, J $>$ 10, atd. Napište funkci, který **vzestupně** třídí karty podle jejich barvy a podle jejich hodnoty. * na vstupu je seznam (pole) karet * funkce vrátí setříděné pole tak, že na začátku budou karty barvy 0, pak karty barvy 1,atd., přičemž v každé skupině budou karty setříděny podle jejich hodnot. * Využijte bublinkové třídění, nebo Vaše oblíbené třídění z přednášky * Příklad: cards = [ [3,"A"], [3,"Q"], [0,"2"], [1,"10"] ] výsledek pro setřídění: [ [0, "2"], [1, "10"], [3, "Q"], [3, "A"] ] Seřaďte toto pole: cards = [[0, 'Q'], [2, '6'], [1, 'K'], [1, '8'], [2, '10'], [2, '4'], [3, '4'], [0, '4'], [1, '3'], [2, '5'], [0, 'K'], [3, 'A'], [1, 'J'], [0, '3'], [0, '9']] ==== Úloha 3 Dekódování zprávy ==== * Dekódujde zprávu ze standardního vstupu pomocí zásobníku: * Písmeno znamená push znaku na zásobník * Hvězdička znamená pop znaku ze zásobníku na výstup * Mezery se ignorují * Dekódujte následující vstup TE*A*QYS***SEU****NI*O** ==== Úloha 4 Flood fill ==== * Napište program, který v zadané matici nahradí souvislou oblast 0 ze zadaného bodu hodnotou 2. * Matici vezměte jako vnitřní proměnnou: m=[ [0,0,1,0,0,1,0,0,0,0], [0,0,1,0,0,1,0,0,0,0], [0,0,1,1,0,1,0,0,0,1], [0,0,1,0,0,0,1,0,1,0], [0,0,1,0,0,0,0,1,0,0], [0,0,1,1,0,1,0,0,0,0], [0,0,1,0,1,1,1,1,0,0], [0,0,1,0,0,1,0,1,1,1], [0,0,1,0,0,1,0,0,0,0], [0,0,1,0,0,1,0,0,0,0] ] * Program si načte počáteční bod ze standardního vstupu * Do zásobníku vložíte vstupní bod * Opakuje, dokud není zásobník prázdný: * pro každý bod (x,y) ze zásobníku, pokud je hodnota matice v tomto bodu 0 proveďte: * pokud jsou body (x-1,y),(x+1,y),(x,y-1),(x,y+1) v matici a jejich hodnota je 0, pak je vložte do zásobníku * Vytiskněte výslednou matici * Program otestujte pro vstupy: 4,4 a 9,9 * Co by se stalo, pokud byste na zásobník vložili i body (x-1,y-1),(x+1,y+1),(x+1,y-1),(x-1,y+1)? * Jaká je složitost tohoto algoritmu? Uměli byste tento algoritmus zefektivnit, aby nevkládal jedno pole matice do zásobníku vícekrát? ===== domácí práce ===== ==== Lehká varianta ==== * Napište program **assemble.py**, který si ze souboru se jménem zadaným jako první argumentu na příkazové řádce, přečte rozměr pole a díly, kterými má to pole zaplnit * první řádek obsahuje dvě čísla //S// //R//, kde //R// je počet řádků a //S// je počet sloupců obdélníkového pole * dále násluduje //R// řádků, kde * 0 - definují volná pole v matici, která se mají vyplnit zadanými dílky * -1 - definují obsazená pole, kam dílky nesmí zasahovat * čísla na jednom řádku jsou oddělena jednou nebo více mezerami (použijte funkci "split()" bez parametrů). * každý další řádek obsahuje popis jednoho dílku: * jedna řádka obsahuje souřadnice čtverečků (x y), ze kterých je sestaven celý dílek * souřadnice jsou uvedeny za sebou bez oddělovacích čárek a závorek * dílek může být libovolně posunut, nemusí obsahovat čtverec se souřadnicemi (0,0) * Program v souboru **assemble.py** nalezne libovolné pokrytí volných polí matice dílky, které se použijí tak, jak jsou zadány - nesmíte je natáčet ani převracet, pouze posouvat. Námi zadané příklady mají právě jedno řešení. * Výstupem programu je pokrytí matice dílky, kdy plocha prvního dílku (zadaný v souboru hned za maticí volného místa) je vyplněna číslem 1, plocha druhého dílku (na další řádce za prvním dílkem) číslem 2, atd. * Notace pro popis dílků: je to seznam x y souřadnic. * Pro T-dílek na obrázku je jeho popis: 0 0 1 0 2 0 1 1 {{:courses:b3b33alp:cviceni:blokus1.eps.png?200|}} * Pro obsah zadan0ho souboru: 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 -1 0 0 0 2 2 2 1 2 0 1 0 0 0 0 1 0 0 0 1 1 1 2 1 2 0 2 2 3 0 3 1 2 1 1 1 0 1 0 0 0 1 0 2 1 1 2 1 Příklad dílku 1: 2 2 2 1 2 0 1 0 0 0 0 1 souřadnice y 2 * 1* * 0*** 012 souřadnice x Graficky znázorněné všechny dílky 1:{{:courses:b3b33alp:cviceni:ubongo-0e.png?100|}} 2:{{:courses:b3b33alp:cviceni:ubongo-1.png?100|}} 3:{{:courses:b3b33alp:cviceni:ubongo-2e.png?100|}} 4:{{:courses:b3b33alp:cviceni:ubongo-3e.png?100|}} program vytiskne: 4 3 3 3 3 4 4 4 2 3 4 2 2 2 1 -1 2 1 2 1 -1 -1 1 1 1 Nápověda možného řešení: * Postupně se snažím vyplnit prázné místo, např odshora zleva * Na první volné políčko se snažím umístit dílek tak, že toto volné pole zaplní svou nejhořejší levou částí (protože vše nad a vlevo od volného políčka je zaplněno, viz obrázek) a rekurzivně zavolám plnění se seznamem dílků, ze kterých odstraním právě použitý dílek {{:courses:b3b33alp:fill.png?100|}} * Pokud to nevyjde a políčko nelze žádným dílkem zaplnit tak, aby tento dílek nepřekrýval jiné dílky, nebo nepřesahoval přes okraj matice), pak se vrátím z rekurze * Při návratu z rekurze, zkusím obsadit volné pole jiným dílkem * Pro správné fungování rekurze buď vytvořím nové pole s nově vloženým dílkem, nebo při návratu z rekurze musím odstranit z matice starý dílek * Pokud již nemám dílky a celá matice je obsazená - mám řešení a mohu skončit ==== Těžká varianta ==== * Napište program **three.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standarní zápis výrazů, jak jste zvyklí ze školy) do reprezentace [[https://en.wikipedia.org/wiki/Three-address_code|tří-adresného módu]]. Tento tří-adresový kód je využíván překladačem, jako mezistupeň mezi programem a strojovým jazykem. **Vstup:** * Výraz je zadán na jedné řádce standardního vstupu * Vstupní výraz může obsahovat pouze celá kladná celá čísla (záporné číslo je unární operátor - a kladné číslo), mezery, závorky (, ) a operace +,-,*,/,^. (Operace ^ je mocnina a má nejvyšší prioritu, nejnižší prioritu mají operace +,-, prostřední prioritu *,/) * Oproti lehké variantě výraz umožňuje unární + a -, tedy je správně 2 + - 3, i 2-+-3 (POZOR unární - má ještě vyšší prioritu než mocnina) **Výstup:** * Při převodu musíte otestovat správnost zadaného výrazu a pokud je formát chybný, pak vytisknete ERROR * formát výstupu: * první trojice má číslo 1, každá další trojice o jedno větší číslo * trojice tiskněte bez mezer, tak jak je uvedeno níže * unární - se přeloží jako trojice, např -5 bude tXX:=0-5 * unární + se vypustí, ve výrazu je vlastně zbytečné * výraz se vyhodnocuje zleva doprava (všechny operace i mocniny) a toto vyhodnocování určuje pořadí trojic. V příkladu níže není tedy možné nejdříve vypočítat rozdíl 1-5 a teprve potom součin 4*2 Příklad: * Vstup 3 + 4 * 2 / ( 1 - 5 ) * převede na výstup: t1:=4*2 t2:=1-5 t3:=t1/t2 t4:=3+t3 Příklad: * Vstup (1+2)*(3+4)/(5+6) * převede na výstup: t1:=1+2 t2:=3+4 t3:=t1*t2 t4:=5+6 t5:=t3/t4 Příklad: * Vstup 1+2/(*4+5) * převede na výstup: ERROR