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

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)
 
a[1][2] = -1
c[2][1] = -3

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í práce

Lehká varianta

  • Napište a odevzdejte program tic_tac_toe.py, který načte hrací pole piškvorek určí vítězného hráče
  • 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 které značí postupně prázdné pole, křížek (malé písmeno x) a kolečko (malé písmeno o).
    • Znaky na řádce jsou oddělené mezerou, jiné znaky se v souborech nevyskytují. Pole ale nemusí nutně být čtvercové
    • Příklad vstupního souboru
      . o . x x .
      . o o o . .
      o o . o . .
      x o x x o .
      . . o x . x
      . . . . x .
  • Výstup
    • x pokud hráč s křížky má 5 znaků v řadě
    • o pokud hráč s kolečky má 5 znaků v řadě
    • None pokud žádný z hráčů nemá 5 svých znaků v řadě (jako u příkladu výše)

Příklady

Vstup:

. . . x x . . .
x . . x . o . .
. . x o o x . o
. o o o o o x .
. o o . . x x .
Výstup: o

Vstup:

. . o o x . . .
. . x x x . x .
. . . o x x . .
x x o . x o . .
. o o x o . . .
. . x o . . . .
Výstup: x

Vstup:

. o x x . . . .
o o x x . . . .
. o x o x . . .
. . x . . x . .
. . . x x x . .
Výstup: None

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čet 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.
  • Timeout na výpočet je: 50 sekund.

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

Testovací matice matice.tgz

courses/b3b33alp/cviceni/t06.txt · Last modified: 2018/11/23 17:21 by stepan