pole = [1, 2, 1, 0, 5]
bola_zhoda = False
for i in range(len(pole)):
for j in range(i+1, len(pole)): #zacneme j=i+1 (kedze j>i)
print(i, j)
if pole[i] == pole[j]:
bola_zhoda = True
break
else: #else patriace k foru, vykona sa ak cyklus nebol preruseny
continue
break
print(bola_zhoda)
0 1 0 2 True
%%time
n = 8
k = 10
pole=[0]*n #vytvori pole nul danej velkosti
pocet = 0
def neobsahuje_rovnake(zoznam): #vrati True, ak su navzajom rozne, inac False
for i in range(len(zoznam)):
for j in range(i+1, len(zoznam)): #zacneme j=i+1 (kedze j>i)
if zoznam[i] == zoznam[j]:
return False
return True
def generuj(uroven): #generuj vsetky moznosti na danej urovni (indexe)
#uz mame uroven cisel vyplnenych
global pocet #chceme pocitat celkovo, teda globalne za cely program / nie v kazdom volani zvlast
#ukoncenie ... ak mame vsetky potrebne cisla
if uroven == n:
if neobsahuje_rovnake(pole):
pocet += 1 #pocet = pocet+1
return #uz rekurzivne nepokracujeme
for hodnota in range(1, k+1):
pole[uroven] = hodnota
generuj(uroven+1) #rekurzivne volanie pre dalsiu poziciu
generuj(0) #spustime s tym, ze este nemame ziadny prvok, teda mame 0 prvkov
pocet
Wall time: 2min 8s
1814400
priebežne nepokračujeme vetvami, ktoré už zjavne nie sú správne (teda číslo sa už opakuje)
%%time
n = 8
k = 10
pole=[0]*n #vytvori pole nul danej velkosti
pocet = 0
def generuj(uroven): #generuj vsetky moznosti na danej urovni (indexe)
#uz mame uroven cisel vyplnenych
global pocet #chceme pocitat celkovo, teda globalne za cely program / nie v kazdom volani zvlast
#ukoncenie ... ak mame vsetky potrebne cisla
if uroven == n:
pocet += 1 #pocet = pocet+1
return #uz rekurzivne nepokracujeme
for hodnota in range(1, k+1):
#iba ak sa tato hodnota este nevyskytla
if not hodnota in pole[:uroven]: #návrat, ak uz je zhoda hodnot
pole[uroven] = hodnota
generuj(uroven+1) #rekurzivne volanie pre dalsiu poziciu
generuj(0) #spustime s tym, ze este nemame ziadny prvok, teda mame 0 prvkov
pocet
Wall time: 1.85 s
1814400
%%time
n = 8
k = 10
pole=[0]*n #vytvori pole nul danej velkosti
pocet = 0
nepouzite = [True]*(k+1) #pole s indexami 0 az k
def generuj(uroven): #generuj vsetky moznosti na danej urovni (indexe)
#uz mame uroven cisel vyplnenych
global pocet #chceme pocitat celkovo, teda globalne za cely program / nie v kazdom volani zvlast
#ukoncenie ... ak mame vsetky potrebne cisla
if uroven == n:
pocet += 1 #pocet = pocet+1
return #uz rekurzivne nepokracujeme
for hodnota in range(1, k+1):
#iba ak sa tato hodnota este nevyskytla
if nepouzite[hodnota]:
pole[uroven] = hodnota
nepouzite[hodnota] = False #poznacime si, ze sme pouzili
generuj(uroven+1) #rekurzivne volanie pre dalsiu poziciu
nepouzite[hodnota] = True #uvolnena, moze sa zase pouzit
generuj(0) #spustime s tym, ze este nemame ziadny prvok, teda mame 0 prvkov
pocet
Wall time: 1.1 s
1814400
from itertools import product, combinations, permutations
print(*product(range(3), repeat=2))
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2)
print(*combinations(range(5), r=2))
(0, 1) (0, 2) (0, 3) (0, 4) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
print(*combinations('AHOJ', r=2))
('A', 'H') ('A', 'O') ('A', 'J') ('H', 'O') ('H', 'J') ('O', 'J')
print(*permutations('AHOJ', r=2))
('A', 'H') ('A', 'O') ('A', 'J') ('H', 'A') ('H', 'O') ('H', 'J') ('O', 'A') ('O', 'H') ('O', 'J') ('J', 'A') ('J', 'H') ('J', 'O')
dynamické programovanie zhora nadol
def fib(n):
if n < 2:
return n
return fib(n-1)+fib(n-2)
%%time
fib(40)
Wall time: 31 s
102334155
Problém (časový) sú opakujúce sa výpočty ... riešením je pamätať si medzdivýsledky.
memoizacia[]
pri kazdom pristupe zistime, ci sme to uz pocitali
- ak ano, pouzijeme zapamatanu hodnotu
- ak nie, vypocitame a zapamatame si ju
F = [None]*100 #medzivysledky
def fib_mem(n):
if F[n] is None: #este sme nepocitali
if n < 2:
hodnota = n
else:
hodnota = fib_mem(n-1)+fib_mem(n-2)
F[n] = hodnota
return F[n]
%%time
fib_mem(40)
Wall time: 0 ns
102334155
F = [None]*100 #medzivysledky
F[0] = 0
F[1] = 1
def fib_mem(n):
if F[n] is None: #este sme nepocitali
F[n] = fib_mem(n-1)+fib_mem(n-2)
return F[n]
%%time
fib_mem(40)
Wall time: 0 ns
102334155
fib_mem(99)
218922995834555169026
from functools import cache #memoizacia zabudovania priamo v jazyku Python
@cache #dekorator funkcie, t.j. fib_cache = cache(fib_cache)
def fib_cache(n):
if n < 2:
return n
return fib_cache(n-1)+fib_cache(n-2)
fib_cache(100)
354224848179261915075
Dynamické programovanie (zdola nahor) - počítame tak, že vždz všetky hodnoty, ktoré potrebujeme do výpočtu už určite máme vypočítané.
n = 100
F = [None]*(n+1) #medzivysledky
F[0] = 0
F[1] = 1
for i in range(2, n+1):
F[i] = F[i-1]+F[i-2]
F[n]
354224848179261915075
Máme rýchle riešenie, na úkor pamäte $O(n)$
n = 100
a, b = 0, 1
for i in range(n):
a, b = b, a+b #python najprv vypocita vsetky hodnoty na pravej strane a potom priradi
print(b)
573147844013817084101
n = 100
a, b = 0, 1
for i in range(n-1): #uz dve cisla mame na zaciatku, tak len (n-1) suctov
a, b = b, a+b #python najprv vypocita vsetky hodnoty na pravej strane a potom priradi
print(b)
354224848179261915075
n = 0 # nespravna hodnota
a, b = 0, 1
for i in range(n-1): #uz dve cisla mame na zaciatku, tak len (n-1) suctov
a, b = b, a+b #python najprv vypocita vsetky hodnoty na pravej strane a potom priradi
print(b)
1
n = 0
a, b = 0, 1
for i in range(n): #uz dve cisla mame na zaciatku, tak len (n-1) suctov
a, b = b, a+b #python najprv vypocita vsetky hodnoty na pravej strane a potom priradi
print(a)
0
$\{1,2,3\}$:
$\emptyset$ ? $\{\}$
$\{1\},\{2\},\{3\}$
$\{1, 2\},\{1,3\},\{2,3\}$
$\{1,2,3\}$
Vieme dvojice rôznych čísel ... ako urobiť aby to bolo množinovo iba raz [2, 3] == [3, 2]
%%time
n = 2
k = 3
pole=[0]*n #vytvori pole nul danej velkosti
pocet = 0
nepouzite = [True]*(k+1) #pole s indexami 0 az k
def generuj(uroven): #generuj vsetky moznosti na danej urovni (indexe)
#uz mame uroven cisel vyplnenych
global pocet #chceme pocitat celkovo, teda globalne za cely program / nie v kazdom volani zvlast
#ukoncenie ... ak mame vsetky potrebne cisla
if uroven == n:
print(pole)
pocet += 1 #pocet = pocet+1
return #uz rekurzivne nepokracujeme
for hodnota in range(1, k+1):
#iba ak sa tato hodnota este nevyskytla
if nepouzite[hodnota]:
pole[uroven] = hodnota
nepouzite[hodnota] = False #poznacime si, ze sme pouzili
generuj(uroven+1) #rekurzivne volanie pre dalsiu poziciu
nepouzite[hodnota] = True #uvolnena, moze sa zase pouzit
generuj(0) #spustime s tym, ze este nemame ziadny prvok, teda mame 0 prvkov
pocet
[1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] Wall time: 0 ns
6
Stačia nám iba rastúce postupnosti: {1,2},{1,3},{2,3}
%%time
n = 2
k = 3
pole=[0]*n #vytvori pole nul danej velkosti
pocet = 0
def generuj(uroven): #generuj vsetky moznosti na danej urovni (indexe)
#uz mame uroven cisel vyplnenych
global pocet #chceme pocitat celkovo, teda globalne za cely program / nie v kazdom volani zvlast
#ukoncenie ... ak mame vsetky potrebne cisla
if uroven == n:
print(pole)
pocet += 1 #pocet = pocet+1
return #uz rekurzivne nepokracujeme
if uroven == 0:
zaciatok = 1
else:
zaciatok = pole[uroven-1]+1
#zaciatok = 1 if uroven == 0 else pole[uroven-1]+1
for hodnota in range(zaciatok, k+1):
#iba ak sa tato hodnota este nevyskytla
pole[uroven] = hodnota
generuj(uroven+1) #rekurzivne volanie pre dalsiu poziciu
generuj(0) #spustime s tym, ze este nemame ziadny prvok, teda mame 0 prvkov
pocet
[1, 2] [1, 3] [2, 3] Wall time: 1 ms
3
%%time
n = 2
k = 3
pole=[0]*n
pocet = 0
def generuj(uroven):
global pocet
if uroven == n:
print(pole)
pocet += 1
return
for hodnota in range(1 if uroven == 0 else pole[uroven-1]+1, k+1):
pole[uroven] = hodnota
generuj(uroven+1)
generuj(0)
pocet
[1, 2] [1, 3] [2, 3] Wall time: 0 ns
3
k = 5
pocet = 0
for n in range(k+1):
pole=[0]*n
generuj(0)
print(pocet)
[] [1] [2] [3] [4] [5] [1, 2] [1, 3] [1, 4] [1, 5] [2, 3] [2, 4] [2, 5] [3, 4] [3, 5] [4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5] [1, 2, 3, 4] [1, 2, 3, 5] [1, 2, 4, 5] [1, 3, 4, 5] [2, 3, 4, 5] [1, 2, 3, 4, 5] 32
print(f'{7:b}')
111
print(f'{7:8b}')
111
print(f'{7:08b}')
00000111
n = 6
print(f'{7:0{n}b}')
000111
n = 5
for i in range(2**n):
print(f'{i:0{n}b}')
00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111