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 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
  • Budeme uvažovat 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 pausu

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 způsob řešení soustavy lineárních rovnic, případně hledání inverzní matice, nebo i počítání determinantu

Úkol 3a Nalezení největšího prvku ve sloupci

  • Napište funkci maximum(m,i), která pro zadanou matici m a číslo i najde číslo řádku v rozsahu range(i,len(m)) takové, že prvek m[max][i] má největší absolutní hodnotu (funkce abs je v pythonu vestavěná standardně)

Úkol 3b Prohození řádku

  • Napište funkci set(m,i), která zavolá funkci maximum(m,i) a pokud je návratová hodnota rozdílná od i, prohodí řádek i a maximum(m,i)

Úkol 3c Úprava řádku

  • Napište funkci do_line(m,i), která zavolá funkci set(m,i) a pokud:
    • m[i][i] se nerovná 0 pak:
      • celý řádek i matice m vydělí hodnotou m[i][i]
      • pro všechny ostatní řádky r matice m odečte od řádku r hodnotu m[r][i] násobek řádku i
      • vrátí hodnotu True
    • jinak vrátí False

Úkol 3d Gausova eliminace

  • Napište funkci Gauss_elim(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 rovna False, pak přeruší cyklus a vrací False
  • Pokud byly všechny návratové hodnoty True, pak vrátí funkce True

Příklad

  • Spusťte funkci Gauss_elim pro matici:

m=[[12,-7,3, 26],
   [4 ,5,-6, -5],
   [-7 ,8,9, 21]]

  • Zkuste program spustit znova s použítím modulu fraction (from fractions import Fraction) a přemapováním matice na typ Fraction

mm = [list(map(Fraction, v)) for v in m]

  • a po výpočtu výsledek transformovat opět na reálná čísla

result = [list(map(float, v)) for v in mm]

Domácí úkol

Lehká varianta

  • Napište program, který řeší trojsměrku (lehčí variantu osmisměrky). Slova ve trojsměrce jsou zapsána pouze zleva doprava, shora dolů a diagonálně zleva shora doprava dolů.
  • Vstup:
    • Jména dvou souborů zadaná na příkazové řádce.
    • První soubor obsahuje 2D matici písmen
    • Druhý soubor obsahuje slova, která jsou v trojsměrce obsažena.
  • Výstup:
    • Písmena, která zbudou po vynechání všech písmen vyskytujících se v zadaných slovech (pozor slova se mohou křížit, je důležité nalezené slovo z matice nemazat)
    • Písmena tiskněte zleva doprava odshora dolů.
  • Soubor odevzdejte do BRUTE, úloha HW06, soubor wordsearch.py
  • Předpokládejte, že
    • Program je volán se jmény existujících souborů
    • Soubory jsou neprázdné a vždy obsahují správně zadané matice
    • V případě, že existuje více řešení, vypište libovolné z nich

Příklad spuštění programu:

python3 wordsearch.py osmismerka.txt slova.txt

Testovat můžete na následujícím příkladu:

'osmismerka.txt'

lnobrblalo
medvaozmfo
ovtzasbest
nznekosilo
iaajnnaoly
kludkkkzvi
ooauulaaia
'slova.txt'
nevzalo
nekosilo
bassova
letenka
vzejdu
boson
robili
zely
meioza
brblalo
moniko
asbest
kosil
saka
zadu
Výsledek Vašeho programu bude:
odfoukali

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 Část 1 a Čá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 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 matice.tgz (i ty je nutné spočítat do 50s).

courses/b3b33alp/cviceni/t06.txt · Last modified: 2021/10/25 13:58 by stepan