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']]
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ý:
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.
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