Warning
This page is located in archive.

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 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

  • 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 prefixové notace do 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)
courses/b3b33alp/cviceni/t08.txt · Last modified: 2019/11/18 09:14 by stepan