Cvičení 6, Pole, matice, třídění

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

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

• 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

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

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

• 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

• 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

• 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(Fraction, v)) for v in mm]

• Napište program integral.py, který načte ze standardního vstupu první řádek, který obsahuje polynom jako v příkladech s polynomy, na druhém řádku budou zadána dvě reálná čísla značící dolní a horní mez integrálu, který má program spočítat.
• Výstupem programu je hodnota určitého integrálu zadaného polynomu od dolní meze po horní mez.
• Program v souboru integral.py odevzdejte pomocí odevzdávacího systému (úloha HW06).
• Tolerance odchylky řešení od referenční hodnoty je 1e-8

Vstup:

1 2 -2
0.0 10.0

Výstup:

  -556.666666667

• Napište program odd.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 liché hodnoty. Příklad volání:

python3 odd.py rectangle.txt

• Výstupem programu je plocha nalezené oblasti, na dlaší řádce jsou souřadnice levého horního rohu a na třetí řádce souřadnice pravého dolního rohu podmatice. Na prvním řádku výstupu je pouze jedno číslo označující počet prvků nalezené podmatice, na druhé řádce je levý horní roh ve formátu řádek, sloupec, na druhém řádku pravý dolní roh. Řádky i sloupce se číslují od 0 a oddělují čárkami.
• 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.

Matice rectangle.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:

6
1, 2
3, 3