Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

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

* 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

  • 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: 2: 3: 4:

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

  • 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 infixového zápisu (standarní zápis výrazů, jak jste zvyklí ze školy) do reprezentace 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

courses/b3b33alp/cviceni/t08.txt · Last modified: 2018/11/19 11:43 by stepan