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í 6: Pole, matice

Inicializace a kopírování 2D polí

  • 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

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

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

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

Prohození řádků matice

  • Napište program, který načte matici a následně permutaci, která definuje prohození řádků matice. Na výstup program vytiskne matici s řádky prohozenými podle zadané permutace.

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.

Krok 1: 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.

Krok 2: Prohození řádku

  • Napište funkci swap_rows(M, i), která prohodí řádek i a řádek s indexem j = maximum(M, i), pokud i != j.

Krok 3: Ú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

Krok 4: 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]]

Použití modulu fraction

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 find_pic.py, který:
    1. načte vzor (matice 3×3) ze standardního vstupu,
    2. načte obraz (matice NxM) ze souboru a
    3. najde, kde se vzor vyskytuje uvnitř obrazu.
  • Vstup
    • Přes příkazovou řádku bude programu předána cesta k souboru s obrazem (použijte sys.argv[1])
      • Soubor je matice celých kladných čísel.
      • Předpokládejte, že matice je zadána korektně a že každá řádka obsahuje stejný počet celých čísel.
    • Druhým vstupem je vzor zadaný ze standardního vstupu.
      • Vzor, který bude program hledat, se skládá ze tří řádek čísel. Každá řádka obsahuje tři čísla 0 nebo 1. Příklad vzoru:

         1 0 1
         0 1 0
         1 0 1

  • Úkol
    • Vzor se v obraze vyskytuje právě jednou. Nalezněte, na které pozici se vzor v obraze vyskytuje.
    • Vzor obsahuje pouze čísla 0 a 1:
      • Číslo 0 znamená, že na tomto místě se v matici může vyskytovat libovolné číslo.
      • Číslo 1 znamená, že na této pozici se vyskytuje stejné číslo, jako na ostatních pozicích čísla 1 ve vzoru.
    • Vzor se celý musí nacházet uvnitř matice, např., nelze nalézt část vzoru na pravé straně a část vzoru na levé straně obrazu.
  • Výstup
    • Dvě celá čísla oddělená mezerou c r, kde c je číslo sloupce a r je číslo řádku levého horního rohu vzoru v matici.
      • Pozn.: Indexy řádků i sloupců začínají od 0, první řádek v souboru je řádek číslo 0.

Příklady

Vstup: Vzor ze standardního vstupu:

1 0 1
0 1 0
1 0 1
Obsah souboru:
1 2 1 2 3 
1 1 2 3 1
1 2 3 2 1
1 1 1 1 1 
Výstup: 1 0

V zadané matici lze nalézt vzor (tvar připomínající X složený z čísel 2) od řádky 0 do řádky 2 a od sloupce 1 do sloupce 3. Vzor v matici na místech 1 má 2, na místech 0 může být libovolná hodnota pro celý vzor navzájem rozdílná (v tomto případě 1 a 3).

Vstup: Vzor ze standardního vstupu:

1 1 1
1 0 1
1 1 1
Obsah souboru:
1 4 1 2 3 3 3
1 1 4 4 4 4 3
1 2 3 4 4 4 4
1 5 1 4 4 4 1
4 4 4 3 4 4 1
1 5 3 5 1 1 1
4 4 4 4 4 4 4 
Výstup: 3 1

V zadané matici lze nalézt vzor od řádky 1 do řádky 3 a od sloupce 3 do sloupce 5. Vzor v matici na místech 1 má 4, na místech 0 může být libovolná hodnota, zde je také 4.

Vstup: Vzor ze standardního vstupu:

1 0 1
0 0 0
1 0 1
Obsah souboru:
1 4 1 2 3 3 3
1 1 4 4 4 4 3
1 2 3 4 4 4 4
1 5 1 5 4 4 1
4 4 4 3 4 4 1
1 5 3 5 1 1 1
4 4 3 4 4 4 4 
Výstup: 1 3

V zadané matici lze nalézt vzor od řádky 3 do řádky 5 a od sloupce 1 do sloupce 3. Vzor v matici na místech 1 má 5, na místech 0 může být libovolná hodnota, zde hodnota 1, 3, a 4.

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 pro získání plného počtu bodů).

courses/b3b33alp/cviceni/t06.txt · Last modified: 2023/11/01 10:55 by stepan