Cvičení 8, Fronta, zásobník

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

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

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

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

* 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

• 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