Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

6. Složitější algoritmy

Úloha 1 - Transpozice matice

Mějme matici A reprezentovanou jako 2D pole (list listů). Vaším úkolem je danou matici transponovat.

import random
 
# funkce, která nám vygeneruje náhodnou matici
def generuj_matici(radky=4, sloupce=4):
 
  if radky > 0 and sloupce > 0:
    matice = []
    for l in range(radky):
      radek = [random.randrange(-100,100) for k in range(sloupce)]
      matice.append(radek)
  else:
    matice = None
    print('Chybny pocet radku ci sloupcu.')
 
  return matice
 
matice = generuj_matici()
print(matice)

len(matice[0])

def transponuj_matici(matice):
 
  <vas_kod>

Čtení dat ze souboru

Pro otevření souboru je možno použít funkci open() a to následujícími způsoby:

soubor = open('nazev_souboru.txt', 'r') # soubor otevřen pouze pro čtení
soubor = open('nazev_souboru.txt', 'rt') # soubor otevřen pro čtení v textovém módu (výchozí)
soubor = open('nazev_souboru.txt', 'rb') # soubor otevřen pro čtení v binárním módu

#Pozor, po čtení je potřeba soubor zavřít pomocí
soubor.close()

případně

with open('nazev_souboru.txt') as soubor:
  <operace_se_souborem>

(V tomto případě není nutné soubor zavírat.)

Pro čtení souboru je následně možné použít několik metod:

  • soubor.read()
  • soubor.readline()
  • soubor.readlines()

# čtení pomocí metody read()
 
test = open('testovaci_soubor.txt')
nacteny_soubor = test.read()
 
print(nacteny_soubor)
print(type(nacteny_soubor))
 
if '\n' in nacteny_soubor:
    print('Nacteny soubor obsahuje escape znaky!')
 
test.close()

# čtení pomocí metody readline()
 
test = open('testovaci_soubor.txt')
nacteny_soubor = test.readline()
 
print(nacteny_soubor)
print(type(nacteny_soubor))
 
if '\n' in nacteny_soubor:
    print('Nacteny soubor obsahuje escape znaky!')
 
test.close()

# čtení pomocí metody readlines()
 
test = open('testovaci_soubor.txt')
nacteny_soubor = test.readlines()
 
print(nacteny_soubor)
print(type(nacteny_soubor))
 
if '\n' in nacteny_soubor:
    print('Nacteny soubor obsahuje escape znaky!')
 
test.close()

Úloha 2 - Detekce palingramu

V přednášce k tématu rekurze jste viděli implementaci algoritmu pro detekci palindromu – slova, které se čte stejně zezadu i zepředu

def palindrom(slovo):
    if len(slovo)>1:
        return slovo == slovo[::-1]  # porovna slovo s reversed slovem
    else:
        return False

Palingram představuje kombinaci dvojic a více slov, která dohromady představují stejné posloupnosti znaků, ač jsou čteny od začátku do konce nebo obráceně: napriklad “nurses run”

Vaším úkolem je načíst z textového souboru 2of4brif.txt slovník anglických slov a vyhledat dvojice slov, která tvoří palingram

from cv06_modul import load1, load2
 
 
slovnik = load2('2of4brif.txt')
 
#print(slovnik)
 
def palingram(slovnik):
 
  <vas_kod>

Zápis do souboru

Soubor je potřeba znovu otevřít pomocí funkce open(). Následný zápis je možný pomocí metody soubor.write(), případně pomocí metody soubor.writelines()

Soubor nejprve otevevřeme pro zápis:

soubor = open('nazev_souboru.txt', 'w') # soubor otevřen pouze pro zápis
soubor = open('nazev_souboru.txt', 'wt') # soubor otevřen pro zápis v textovém módu
soubor = open('nazev_souboru.txt', 'wb') # soubor otevřen pro zápis v binárním módu

Následně do souboru něco zapíšeme

soubor.write('Text, ktery chcete do souboru zapsat.')

# zápis pomocí metody write()
 
test = open('novy_soubor.txt','w')
veta_na_zapis = 'Zapiseme jednu vetu do noveho souboru!'
test.write(veta_na_zapis)
 
test.close()
 
test = open('novy_soubor.txt','r')
test.read()
 
test.close()

# zápis pomocí metody writelines() - možno zapsat list
 
test = open('novy_soubor.txt','w')
vety_na_zapis = ['Tohle je prvni veta!', 'Tohle je druha veta!']
test.writelines(vety_na_zapis)
 
test.close()
 
test = open('novy_soubor.txt','r')
test.readlines()
 
test.close()

# zápis pomocí metody writelines() - možno zapsat list
vety_na_zapis = ['Tohle je prvni veta!', 'Tohle je druha veta!']
 
with open('novy_soubor.txt','w') as test:
    test.write('\n'.join(vety_na_zapis))
    test.write('\n')
 
with open('novy_soubor.txt','w') as test:
  test.write('\n'.join(str(veta) for veta in vety_na_zapis))

Úloha 3 - Lyžování

Představte si, že jdete lyžovat, ale u lanovky zjistíte, že nemáte dost peněz na celodenní vstupenku. Máte ale dost na to, abyste se alespoň jednou vyvezli na horu. Vyjedete lanovkou nahoru na horu a vidíte, že Vám majitelé areálu připravili hned několik možných sjezdovek, které se navíc různě kříží. Jelikož to bude Vaše jediná jízda dolů, chcete jet tou nejdelší trasou. Na mapě je naštěstí napsaná délka jednotlivých úseků. Již na začátku máte na vybranou: Pojedete doprava či doleva? Toto rozhodnutí (zda-li jet doprava či doleva) budete muset opakovat po sjezdu každého úseku. Najděte takovou posloupnost čísel (viz níže) odpovídající nejdelší možné trase. Výsledek zapište do souboru (zápis nemusí být v rámci funkce).

   /3/
  \7\ 4 
 2 \4\ 6 
8 5 \9\ 3

Nejdelší možná trase je pro tento případ dlouhá 3+7+4+9 = 23

Vstupem funkce je list listů (např. [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]), výstupem je celé číslo odpovídající nejdelší trase (např. 23).

Pro přiložené soubory sjezdovka_01.txt je výsledek 2487, pro sjezdovka_02.txt je výsledek 7273.

sjezdovka = [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]

# funkce pro nacteni hodnot ze souboru - pro overeni Vasi funkce
 
from cv06_modul import nacti_sjezdovku
 
sjezdovka = nacti_sjezdovku('sjezdovka_01.txt')

def nejdelsi_trasa(sjezdovka):
 
  <vase_implementace>

Příklady na procvičení ve zbytku cvičení nebo doma

Úloha 4 - Bludiště (nejkratší cesta)

Mějme matici čísel o velikosti NxN. Najděte nejkratší cestu (definováno jako nejmenší součet cest) v případě, že se chceme dostat z levého horního rohu matice do pravého dolního rohu matice. V matici se můžeme pohybovat pouze posunem o políčko dolů nebo o políčko vpravo (viz Projekt Euler / úloha 81).

Pro matici A

[ 95, 74,  6]
[101, 45, 65]
[ 17, 25, 34]

je nejkratší cesta rovna součtu 95+101+17+25+34=272

Pro matici B

[ 95, 74,  6]
[101, 45, 65]
[ 19, 25, 34]

je nejkratší cesta rovna součtu 95+74+45+25+34=273

Pro matici C

[ 95, 74,  6]
[101, 47, 65]
[ 19, 25, 34]

je nejkratší cesta rovna součtu 95+74+6+65+34=274

Pro matici uloženou v textovém souboru (matice.txt - načtení pomocí funkce nacti_matici() uloženou v souboru cv06_modul.py) je výsledek 427337.

def nejkratsi_cesta(matice):
 
  <vas_kod>

courses/bab37zpr/tutorials/lab06.txt · Last modified: 2022/10/24 16:32 by zizieada