0 dní v řadě · 0 bodů

Rozhodování a cykly · 20 min

Vnořené cykly

Cyklus v cyklu krok za krokem. Tabulky, obrazce, hledání dvojic a jak z vnořených cyklů vyskočit.

Hloubka
Úkoly
Lidsky řečeno

Uvaděč v kině kontroluje sál. Vezme první řadu a projde v ní všechna sedadla. Pak se posune na druhou řadu a znovu projde všechna sedadla. Řady jsou vnější cyklus, sedadla vnitřní. Stejně fungují hodiny: než se hodinová ručička pohne o dílek, minutová oběhne celý kruh.

Cyklus uvnitř cyklu

Tělo cyklu může obsahovat cokoli, tedy i další cyklus. Pravidlo je jediné: vnitřní cyklus proběhne celý v každém kole vnějšího.

for rada in range(1, 3):
    for sedadlo in range(1, 4):
        print("řada", rada, "sedadlo", sedadlo)
Výstup
řada 1 sedadlo 1
řada 1 sedadlo 2
řada 1 sedadlo 3
řada 2 sedadlo 1
řada 2 sedadlo 2
řada 2 sedadlo 3

Sleduj, která proměnná se mění rychle a která pomalu:

krokradasedadloco se děje
111vnitřní cyklus začíná
212
313vnitřní cyklus končí
421vnější se posunul, vnitřní začíná znovu
522
623vnitřní končí, vnější taky

Dvě řady krát tři sedadla je šest průchodů. Obecně se počty násobí.

Na místě odsazení záleží. Řádek odsazený jen o jednu úroveň patří do vnějšího cyklu a provede se jednou za řadu.

for rada in range(1, 3):
    print("Začínám řadu", rada)
    for sedadlo in range(1, 3):
        print("  sedadlo", sedadlo)
    print("Hotovo s řadou", rada)
print("Sál zkontrolován")
Výstup
Začínám řadu 1
  sedadlo 1
  sedadlo 2
Hotovo s řadou 1
Začínám řadu 2
  sedadlo 1
  sedadlo 2
Hotovo s řadou 2
Sál zkontrolován

Vnější i vnitřní cyklus můžou procházet cokoli, třeba varianty zboží v e-shopu:

for barva in ["černá", "bílá"]:
    for velikost in ["M", "L", "XL"]:
        print(barva, velikost)
Výstup
černá M
černá L
černá XL
bílá M
bílá L
bílá XL
Kvíz

Kolikrát se provede print v kódu for a in range(3): a uvnitř for b in range(4): print(a, b)?

Úkol

Dvě kostky

Házíš dvěma šestistěnnými kostkami. Projdi všechny kombinace hodů. Do proměnné celkem ulož počet všech kombinací a do proměnné devitky počet těch, kde je součet 9.

celkem = 0
devitky = 0
# doplň dva vnořené cykly
Výstup

Obrazce a tabulky

Výstup po řádcích je přirozené místo pro vnořený cyklus. Vnější cyklus řídí řádky, vnitřní to, co je na řádku. Parametr end="" zabrání přechodu na nový řádek a prázdné print() řádek ukončí.

for radek in range(1, 4):
    for sloupec in range(1, 5):
        print(f"{radek * sloupec:3}", end="")
    print()
Výstup
  1  2  3  4
  2  4  6  8
  3  6  9 12

Zápis :3 v f-stringu dá číslu šířku tři znaky, takže sloupce drží pod sebou.

Zajímavější je, když vnitřní cyklus závisí na vnějším. Tady má každý řádek tolik znaků, kolik je jeho číslo.

for radek in range(1, 5):
    for _ in range(radek):
        print("#", end="")
    print()
Výstup
#
##
###
####
radekvnitřní řadakol vnitřního cykluřádek výstupu
1range(1)1#
2range(2)2##
3range(3)3###
4range(4)4####

Celkem 1 + 2 + 3 + 4 = 10 průchodů, tedy méně než plných 4 krát 4.

Úkol

Číselný trojúhelník

Pro n = 4 vypiš čtyři řádky: 1, 12, 123 a 1234, každý zvlášť a čísla bez mezer. Použij dva vnořené cykly a proměnnou n.

n = 4
# doplň
Výstup

Každý s každým

Turnaj čtyř hráčů, každý hraje s každým jednou. Kdyby vnitřní cyklus začínal vždy od jedničky, dostaneš zápas hráče se sebou samým i oba zápasy 1 proti 2 a 2 proti 1. Řešení je začít vnitřní cyklus až za aktuálním hráčem.

zapasy = 0
for prvni in range(1, 5):
    for druhy in range(prvni + 1, 5):
        print(prvni, "proti", druhy)
        zapasy += 1
print("Zápasů:", zapasy)
Výstup
1 proti 2
1 proti 3
1 proti 4
2 proti 3
2 proti 4
3 proti 4
Zápasů: 6
prvnivnitřní řadasoupeři
1range(2, 5)2, 3, 4
2range(3, 5)3, 4
3range(4, 5)4
4range(5, 5)nikdo, řada je prázdná

Vnitřní cyklus může procházet i to, co mu dodal vnější. Tady má každý den svoje tržby. Všimni si, že soucet_dne se nuluje ve vnějším cyklu, aby každý den začínal od nuly.

trzby = [[120, 80], [200, 40, 60], [90]]
for den in trzby:
    soucet_dne = 0
    for castka in den:
        soucet_dne = soucet_dne + castka
    print("Tržba za den:", soucet_dne)
Výstup
Tržba za den: 200
Tržba za den: 300
Tržba za den: 90
Kvíz

Kolik řádků vypíše for a in range(3): a uvnitř for b in range(a): print(a, b)?

Jak vyskočit ven

break ukončí jen nejbližší cyklus. Vnější pokračuje, jako by se nic nestalo.

for rada in range(1, 4):
    for sedadlo in range(1, 5):
        if sedadlo == 3:
            break
        print(rada, sedadlo)
Výstup
1 1
1 2
2 1
2 2
3 1
3 2

Když chceš skončit úplně, nejsrozumitelnější je příznak: proměnná, která si pamatuje, že je hotovo. Hledáme dvě čísla, jejichž druhé mocniny dají dohromady 169.

nalezeno = False
for a in range(1, 13):
    for b in range(a, 13):
        if a * a + b * b == 169:
            print("Našel jsem:", a, b)
            nalezeno = True
            break
    if nalezeno:
        break
print("Skončil jsem u a =", a)
Výstup
Našel jsem: 5 12
Skončil jsem u a = 5

Bez druhého break by vnější cyklus zbytečně zkoušel a od 6 do 12. Až se naučíš funkce, bude to ještě jednodušší: return vyskočí ze všech cyklů najednou.

Úkol

Hledání dvojice

Najdi čísla a a b od 1 do 20, kde a <= b, jejich součet je 20 a součin 91. Ulož je do nalezene_a a nalezene_b. Do kroky počítej, kolikrát se provedlo tělo vnitřního cyklu. Po nálezu opusť oba cykly.

nalezene_a = None
nalezene_b = None
kroky = 0
for a in range(1, 21):
    for b in range(a, 21):
        kroky += 1
        # doplň
Výstup
Úkol

Prvočísla do třiceti

Vypiš všechna prvočísla od 2 do 30, každé na vlastní řádek. Vnější cyklus projde kandidáty, vnitřní hledá dělitele. Hodí se ti break a else z minulé lekce.

for cislo in range(2, 31):
    pass  # pass znamená „nedělej nic“, nahraď ho svým kódem
Výstup
Pod kapotou · složitost a jak se vnořeného cyklu zbavit

Dva vnořené cykly přes n prvků znamenají O(n²) a tři O(n³). Trojúhelníková varianta dělá n(n−1)/2 kroků, což je pořád O(n²), jen s polovičním koeficientem. Při n = 100 000 je to asi 5 miliard porovnání, tedy problém, který žádná mikrooptimalizace nespraví. Pomůže změna algoritmu. Hledání dvojice se zadaným součtem jde z O(n²) na průměrné O(n) díky množině, protože test in u ní nemusí nic procházet:

cisla = [14, 3, 9, 27, 5, 11]
cil = 16
videna = set()
for x in cisla:
    if cil - x in videna:
        print(cil - x, x)
        break
    videna.add(x)
Výstup
5 11

Pevné vnoření nahrazuje itertools. product je vnořený cyklus napsaný v C a umí hloubku určenou za běhu přes repeat, combinations odpovídá vzoru „každý s každým“. A protože je to jeden cyklus, break z něj vyskočí celý.

from itertools import product, combinations

print(sum(1 for a, b in product(range(1, 7), repeat=2) if a + b == 7))
print(list(combinations("ABC", 2)))
Výstup
6
[('A', 'B'), ('A', 'C'), ('B', 'C')]

Bez příznaku jde vyskočit idiomem else: continue. Funguje, ale čtenáře zdrží, takže v produkci obvykle vyhraje extrakce do funkce s return.

for a in range(1, 4):
    for b in range(1, 4):
        if a * b == 4:
            print(a, b)
            break
    else:
        continue
    break
Výstup
2 2

Výkon: na úrovni modulu jsou proměnné položky slovníku (LOAD_NAME, STORE_NAME), ve funkci sloty v poli (LOAD_FAST), takže stejný horký cyklus běží ve funkci rychleji. Pořadí cyklů u seznamů v Pythonu moc nerozhoduje, protože prvky jsou stejně ukazatele rozeseté po haldě. U souvislých polí NumPy naopak na pořadí průchodu vzhledem k uložení v paměti záleží kvůli cache, a ještě víc pomůže vnitřní cyklus úplně nahradit vektorovou operací.