====== Cvičení 6, Pole, matice ====== ==== Opakování ==== Projdeme si inicializaci a kopírování 1D a více-D polí. Spusťte následující kód a na konci si vytiskněte jednotlivá pole. Co pozorujeme? # Inicializace pole a = [0] * 5 # Jak správně zkopírovat pole? b = a c = a[:] d = list(a) a[3] = 3 b[0] = -5 c[4] = 4 Nyní spusťte následující kód a opět si na konci vypište jednotlivá pole. # Inicializace 2D pole přímo a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # Inicializace po řádcích f = [] for i in range(3): f.append([i] * 3) # Inicializace po řádcích ve zkráceném zápisu g = [[i] * 3 for i in range(3)] # Jak správně zkopírovat pole? b = a c = a[:] d = list(b) e = [ r[:] for r in a ] f = [ list(a[i]) for i in range(len(a))] a[0][0] = -1 b[0][1] = -2 c[0],c[1]=c[1],c[0] d[1][0] = -3 e[1][1] = -4 Pokud chceme opravdovou kopii vícedimenzionálního pole, tvz. //deep copy//, můžeme použít modul ''copy'' a funkci ''deepcopy''. Doplňte import a kopírování do předchozí ukázky a porovnejte výsledky. import copy d = copy.deepcopy(b) ==== Úkol 1 Life ==== * Hru [[https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life|Life]] navrhl v roce 1970 matematik John Horton Conway. * Pravidla hry jsou jednoduchá: * pokud jsou v okolí jedné buňky živé právě 3 buňky, pak v této buňce život vznikne (nebo zůstane) * pokud je buňka živá a v jejím okolí jsou právě 2 živé buňky, pak tato buňka bude žít i nadále * v ostatních případech buňka zahyne buď na osamění, nebo přemnoženost * Uvažujte osmiokolí: 8 sousedních buněk. * Uvažujte uzavřený svět, tedy sousední políčko pro první pole řádku je poslední pole řádku, sousední pole pro první řádek je poslední řádek * Napište program, který bude simulovat 40 kroků hry life pro toto počáteční pole: a = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ] * Vygenerování prázdného pole [[0]*len(a[0]) for i in a] * Využití funkce modulo (%) Vám pomůže implementovat uzavřený svět * Pro lepší zobrazení udělejte po každém kroku pauzu import time time.sleep(0.5) * Také můžete vylepšit zobrazení tak, že místo 1 budete tisknout X a místo 0 mezeru ''.join('X' if i!=0 else ' ' for i in x)) ==== Úkol 2 Prohození řádků matice ==== * Napište program, který načte matici a následně permutaci, která definuje prohození řádků zadané matice. Na výstup program vytiskne matici s řádky prohozenými podle zadané permutace. ==== Úkol 3 Gaussova eliminační metoda ==== * Gaussova eliminační metoda je metodou řešení soustavy lineárních algebraických rovnic. GEM lze využít pro výpočet inverzní matice nebo determinantu matice. === Úkol 3a Nalezení největšího prvku ve sloupci === * Napište funkci ''maximum(M, i)'', která pro zadanou matici **M** a index (číslo) **i** najde takový index řádku **j** v rozsahu ''range(i, len(M))'' jehož absolutní hodnota **M[j][i]** je maximální. Využijte vestavěnou funkci ''abs''. === Úkol 3b Prohození řádku === * Napište funkci ''swap_rows(M, i)'', která prohodí řádek **i** a řádek s indexem ''j = maximum(M, i)'', pokud ''i != j''. === Úkol 3c Úprava řádku === * Napište funkci ''do_line(M, i)'', která zavolá funkci ''swap_rows(M, i)'' a pokud: * ''M[i][i] != 0'': * celý řádek **i** matice **M** vydělí hodnotou **M[i][i]** * od všech řádků **r** v rozsahu ''range(i + 1, len(M))'' odečte **M[r][i]**-násobek řádku **i** * vrátí hodnotu ''True'' * jinak vrátí ''False'' === Úkol 3d Gausova eliminace === * Napište funkci ''GEM(M)'', která pro všechna **i** z rozsahu ''range(len(m))'' zavolá funkci **do_line(M, i)** * Pokud je návratová hodnota funkce ''do_line()'' alespoň 1x False, metoda ''Gauss_elim()'' vrací ''False''. V opačném případě vrací ''True''. === Příklad === * Spusťte funkci ''GEM()'' pro matici: m=[[12,-7,3, 26], [4 ,5,-6, -5], [-7 ,8,9, 21]] ==== Úkol 4 ==== Využijte ve výpočtu úkolu 3 zlomků namísto reálných čísel. K tomu využijte Python modul **fraction** (''from fractions import Fraction'') pomocí kterého přemapujte prvky matice **M** na typ Fraction (zlomek): M_fr = [list(map(Fraction, v)) for v in M] GEM(M_fr) Výsledek GEM lze transformovat zpět na reálná čísla pomocí: result = [list(map(float, v)) for v in M_fr] ===== Domácí úkol ===== ==== Lehká varianta ==== * Napište a odevzdejte program **tic_tac_toe.py**, který načte hrací pole piškvorek a určí souřadnice vítězného tahu hráče na řadě * **Vstup** * Přes příkazovou řádku bude programu předána cesta k souboru s hracím polem (použijte ''sys.argv[1]'') * Soubor obsahuje znaky ''.'', ''x'' a ''o'' značící prázdné pole ''.'', křížek ''x'' a kolečko ''o''. * Znaky na řádce jsou oddělené mezerou. Jiné znaky než (mezera, ''.'', ''x'', ''o'') se v souborech nevyskytují. Pole nemusí být čtvercové. * Hráč s ''o'' vždy začíná. Pro určení hráče na tahu tedy platí * pokud je v poli stejný počet ''x'' a ''o'', pak je na tahu ''o'' * pokud je ''x'' o jednu méně, než ''o'', pak hraje ''x'' * Příklad vstupního souboru o . . o o o o x o . x x . x x . o . . x o o x o x o o x x . . x x . . * **Výstup** * dvě celá čísla oddělená mezerou, která určují indexy souřadnic v hracím poli (2D pole po řádcích) 0 2 * V poli je stejný počet ''o'' a ''x'' (12), na tahu je tedy ''o'' * Hráč ''o'' hru vyhrává, když hraje na první řádek do třetího sloupce, tj. index v poli ''0 2'' === Příklady === **Vstup:** o . o x o o o . . . x x . . x . o o x . . o o . o x . x . . x x o x x Na tahu je hráč ''o'', vítězná řada je v diagonále z levého horního rohu. **Výstup:** ''1 1'' **Vstup:** x . . o o . . . . . o . x o . o . x . . o x x x o . o x . . Na tahu je hráč ''x'', doplnit může řadu ve třetím sloupci **Výstup:** ''1 2'' **Vstup:** x x . . . . x o . o . . x o o x o . . o o . o x o . x x o . . x . . x . **Výstup:** ''0 4'' **Vstup:** . o o . . o . . x o . x x . . . . . o x . . . . o . . . x . . o x o x o . o . x . x x o . o o . . . x o . o x . . x x . x . . o **Výstup:** ''3 2'' ==== Těžká varianta ==== * Napište program **rectangle.py**, který v matici celých čísel zadané na příkazové řádce (''sys.argv[1]'') najde největší souvislou podmatici libovolného rozměru, která obsahuje pouze záporné hodnoty. Příklad volání: python3 rectangle.py matice.txt * Výstupem programu jsou souřadnice levého horního rohu a pravého dolního rohu podmatice. Na prvním řádku výstupu je levý horní roh ve formátu řádek sloupec, na druhém řádku pravý dolní roh. Řádky i sloupce se číslují od 0. * Velikost podmatice je určena jejím počtem prvků. * Snažte se, aby Váš program byl co nejefektivnější, ideálně, aby jeho časová složitost odpovídala velikosti matice. Bodové ohodnocení této úlohy bude záviset na efektivnosti (rychlosti) Vašeho algoritmu. * Pokud existuje více řešení, vypište libovolné z nich. * Nastudujte si nejrychlejší způsob nalezení maximálního obdélníku pod histogramem [[https://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/|Část 1]] a [[https://www.geeksforgeeks.org/largest-rectangle-under-histogram/ | Část 2]] * Timeout na výpočet je: 50 sekund. Toto platí i pro velké matice, které si můžete stáhnout níže. Na nich je dobře patrný rozdíl mezi lineárním algoritmem $O(n)$, algoritmem $O(n \cdot \log(n))$ a $O(n^2)$, kde n je počet prvků matice. === Příklad === Matice {{courses:b3b33alp:rectangle.txt|matice.txt}}: 1 -9 -2 8 6 1 8 -1 -11 -7 6 4 10 12 -1 -9 -12 14 8 10 -3 -5 17 8 6 4 10 -13 -16 19 Výstup: 1 2 3 3 Obrovské testovací matice {{courses:b3b33alp:matice.tgz|matice.tgz}} (i ty je nutné spočítat do 50s).