====== 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 **postfix.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standardní zápis výrazů, jak jste zvyklí ze školy) do postfixového zápisu (tzv. [[https://cs.wikipedia.org/wiki/Postfixov%C3%A1_notace|reverzní polské notace]]) s využitím algoritmu [[https://cs.wikipedia.org/wiki/Shunting-yard_%28algoritmus%29|shunting yard]]. * **Vstup**: * textový řetězec, přes standardní vstup * obsahuje pouze celá kladná čísla, kulaté závorky a operace '' + - * / ** '' * mezi dvěma členy je vždy právě jedna mezera * **Výstup**: * pokud je vstupní řetězec ve správném formátu, pak je výstup textový řetězec reprezentující vstupní výraz v postfixové notaci. Mezi každými dvěma členy výstupu vytiskněte právě jednu mezeru * jinak ''ERROR'' * priorita operátorů: ''**'' větší než ''*'', ''/'', větší než ''+'', ''-'' * operátor mocnění je asociativní zprava * **Příklad 1(a)**: 3 + 4 * 2 / ( 1 - 5 ) výstup 3 4 2 * 1 5 - / + * **Příklad 1(b)**: ( 3 + 4 ) * 2 / ( 1 - 5 ) výstup (všimněte si, jak se oproti předchozímu příkladu projeví přidání závorky) 3 4 + 2 * 1 5 - / * **Příklad 2** 9 * 3 ** 5 Výstup: 9 3 5 ** * * **Příklad 3**: ( 3 * ( 4 - 5 ) ) + ( 8 * ( 10 + 2 ) / 9 ) výstup 3 4 5 - * 8 10 2 + * 9 / + * **Příklady chybných vstupů** * ''2 + ( 4 ( * 5 ) )'' * ''3 - * 5'' * ''( 2 * ( 1 - 3 )'' ==== Těžká varianta ==== * Napište program **pretoin.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Prefixov%C3%A1_notace|prefixové notace]] do [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] * **Vstup** * textový řetězec přes standardní vstup * řetězec obsahuje pouze kladná celá čísla, operátory ''- + / * **'', případně mezeru mezi dvěma členy, pokud je to pro jednoznačnost výrazu nutné ( dvě hvězdičky bez mezery ''**'' je operátor mocnění, dvě hvězdičky oddělené mezerou ''* *'' jsou dvě po sobě jdoucí operace násobení), dva numerické členy jsou vždy oddělené mezerou * **Výstup** * pokud je na vstupu platný řetězec v prefixové notaci, pak řetězec převedený na infixovou notaci, vytiskněte bez mezer * jinak ''ERROR'' * Operace +,-,*,/ se vyhodnocují zleva, operace ** se vyhodnocuje zprava (stejně jako je to v Pythonu) * Složitost této úlohy je ve správném doplnění závorek, které musí zaručit správné vyhodnocení zleva doprava, ale nesmíte závorky používat zbytečně * **Příklady:** * Vstup *-4 2 3 převede na výstup: (4-2)*3 * Vstup +-4 2 3 převede na výstup: 4-2+3 * Vstup *4-2 3 převede na výstup: 4*(2-3)