Algoritmy

• algoritmy usporiadania 1x - BubbleSort 9x, QuickSort 5x, MergeSort 3x, HeapSort 2x
• teória grafov - Dijkstra 11x, Kruskal 8x, Prim 5x, BFS 4x, DFS 4x, Bellman-Ford 3x, Floyd-Warshall 2x
• backtrack 2x
• dynamické programovanie 1x
• binárne vyhľadávanie 4x
• greedy 2x

Štruktúry údajov

• Pole 6x, matica 2x, Integer/Null/Char/double/float 1x, tabuľka 1x

• LinkedList 15x, Tree 14x, Stack 10x, Heap 9x, graf 7x, Queue 5x, List 4x, Binary(Search)Tree 3x,HashMap 2x, , Map 2x, HashSet 1x, DeQueue 1x, ArrayList 1x, Dictionary (asociatívne pole) 1x

https://cs.wikipedia.org/wiki/Abstraktn%C3%AD_datov%C3%BD_typ

http://input.sk/pdf/ads.pdf

Dizajnové paradigmy programovania

Existuje viacero základných typov/druhov počítačových algoritmov :

• Simulácia (Simulation)
• Hrubá sila (Brute Force)
• Prehľadávanie s návratom (Backtrack-ing)
• Metóda vetiev a hraníc (Branch and bound)
• Rozdeľuj a panuj (Divide & Conquer, Divide et impera)
• Heuristika (Greedy)
• Algoritmy usporiadania (Sorting algorithms)
• Dynamické programovanie, memoizácia (Dynamic programming, memoization)
• Grafové algoritmy (Graph algorithms)

niektoré už poznáte (napr. z PAZ1b):

• BubbleSort, MergeSort, SelectionSort, QuickSort, HeapSort, BucketSort, RadixSort
• najkratšie cesty Dijsktra, Floyd-Warshall, Bellman-Ford
• najmešia kostra grafu Kruskal, Primov
• BFS, DFS

Hrubá sila (Brute Force)

• skúšanie všetkých možností

všetky $n$-prvkové postupnosti čísel $1..k$

n = 2 k = 4

12
23
34
41
11
22
33
44
13
41
43
21
...

$\Theta(k^n)$

n, k = 7, 5 #n=7 a k = 5
pole = [0]*n
pocet = 0

def gen(uroven):
    global pocet # pouzitie globalnej premennej vo funkcii
    if uroven == n:
        print(pole)
        pocet += 1
        return
    for hodnota in range(1, k+1):
        pole[uroven] = hodnota
        gen(uroven+1)

gen(0)
print("Pocet:", pocet)

[1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 1, 1, 3]
...
[5, 5, 4, 5, 5, 4, 5]
[5, 5, 4, 5, 5, 5, 1]
[5, 5, 4, 5, 5, 5, 2]
[5, 5, 4, 5, 5, 5, 3]
[5, 5, 4, 5, 5, 5, 4]
[5, 5, 4, 5, 5, 5, 5]
[5, 5, 5, 1, 1, 1, 1]
[5, 5, 5, 1, 1, 1, 2]
[5, 5, 5, 1, 1, 1, 3]
[5, 5, 5, 1, 1, 1, 4]
[5, 5, 5, 1, 1, 1, 5]
[5, 5, 5, 1, 1, 2, 1]
[5, 5, 5, 1, 1, 2, 2]
[5, 5, 5, 1, 1, 2, 3]
[5, 5, 5, 1, 1, 2, 4]
[5, 5, 5, 1, 1, 2, 5]
[5, 5, 5, 1, 1, 3, 1]
[5, 5, 5, 1, 1, 3, 2]
[5, 5, 5, 1, 1, 3, 3]
[5, 5, 5, 1, 1, 3, 4]
[5, 5, 5, 1, 1, 3, 5]
[5, 5, 5, 1, 1, 4, 1]
[5, 5, 5, 1, 1, 4, 2]
[5, 5, 5, 1, 1, 4, 3]
[5, 5, 5, 1, 1, 4, 4]
[5, 5, 5, 1, 1, 4, 5]
[5, 5, 5, 1, 1, 5, 1]
[5, 5, 5, 1, 1, 5, 2]
[5, 5, 5, 1, 1, 5, 3]
[5, 5, 5, 1, 1, 5, 4]
[5, 5, 5, 1, 1, 5, 5]
[5, 5, 5, 1, 2, 1, 1]
[5, 5, 5, 1, 2, 1, 2]
[5, 5, 5, 1, 2, 1, 3]
[5, 5, 5, 1, 2, 1, 4]
[5, 5, 5, 1, 2, 1, 5]
[5, 5, 5, 1, 2, 2, 1]
[5, 5, 5, 1, 2, 2, 2]
[5, 5, 5, 1, 2, 2, 3]
[5, 5, 5, 1, 2, 2, 4]
[5, 5, 5, 1, 2, 2, 5]
[5, 5, 5, 1, 2, 3, 1]
[5, 5, 5, 1, 2, 3, 2]
[5, 5, 5, 1, 2, 3, 3]
[5, 5, 5, 1, 2, 3, 4]
[5, 5, 5, 1, 2, 3, 5]
[5, 5, 5, 1, 2, 4, 1]
[5, 5, 5, 1, 2, 4, 2]
[5, 5, 5, 1, 2, 4, 3]
[5, 5, 5, 1, 2, 4, 4]
[5, 5, 5, 1, 2, 4, 5]
[5, 5, 5, 1, 2, 5, 1]
[5, 5, 5, 1, 2, 5, 2]
[5, 5, 5, 1, 2, 5, 3]
[5, 5, 5, 1, 2, 5, 4]
[5, 5, 5, 1, 2, 5, 5]
[5, 5, 5, 1, 3, 1, 1]
[5, 5, 5, 1, 3, 1, 2]
[5, 5, 5, 1, 3, 1, 3]
[5, 5, 5, 1, 3, 1, 4]
[5, 5, 5, 1, 3, 1, 5]
[5, 5, 5, 1, 3, 2, 1]
[5, 5, 5, 1, 3, 2, 2]
[5, 5, 5, 1, 3, 2, 3]
[5, 5, 5, 1, 3, 2, 4]
[5, 5, 5, 1, 3, 2, 5]
[5, 5, 5, 1, 3, 3, 1]
[5, 5, 5, 1, 3, 3, 2]
[5, 5, 5, 1, 3, 3, 3]
[5, 5, 5, 1, 3, 3, 4]
[5, 5, 5, 1, 3, 3, 5]
[5, 5, 5, 1, 3, 4, 1]
[5, 5, 5, 1, 3, 4, 2]
[5, 5, 5, 1, 3, 4, 3]
[5, 5, 5, 1, 3, 4, 4]
[5, 5, 5, 1, 3, 4, 5]
[5, 5, 5, 1, 3, 5, 1]
[5, 5, 5, 1, 3, 5, 2]
[5, 5, 5, 1, 3, 5, 3]
[5, 5, 5, 1, 3, 5, 4]
[5, 5, 5, 1, 3, 5, 5]
[5, 5, 5, 1, 4, 1, 1]
[5, 5, 5, 1, 4, 1, 2]
[5, 5, 5, 1, 4, 1, 3]
[5, 5, 5, 1, 4, 1, 4]
[5, 5, 5, 1, 4, 1, 5]
[5, 5, 5, 1, 4, 2, 1]
[5, 5, 5, 1, 4, 2, 2]
[5, 5, 5, 1, 4, 2, 3]
[5, 5, 5, 1, 4, 2, 4]
[5, 5, 5, 1, 4, 2, 5]
[5, 5, 5, 1, 4, 3, 1]
[5, 5, 5, 1, 4, 3, 2]
[5, 5, 5, 1, 4, 3, 3]
[5, 5, 5, 1, 4, 3, 4]
[5, 5, 5, 1, 4, 3, 5]
[5, 5, 5, 1, 4, 4, 1]
[5, 5, 5, 1, 4, 4, 2]
[5, 5, 5, 1, 4, 4, 3]
[5, 5, 5, 1, 4, 4, 4]
[5, 5, 5, 1, 4, 4, 5]
[5, 5, 5, 1, 4, 5, 1]
[5, 5, 5, 1, 4, 5, 2]
[5, 5, 5, 1, 4, 5, 3]
[5, 5, 5, 1, 4, 5, 4]
[5, 5, 5, 1, 4, 5, 5]
[5, 5, 5, 1, 5, 1, 1]
[5, 5, 5, 1, 5, 1, 2]
[5, 5, 5, 1, 5, 1, 3]
[5, 5, 5, 1, 5, 1, 4]
[5, 5, 5, 1, 5, 1, 5]
[5, 5, 5, 1, 5, 2, 1]
[5, 5, 5, 1, 5, 2, 2]
[5, 5, 5, 1, 5, 2, 3]
[5, 5, 5, 1, 5, 2, 4]
[5, 5, 5, 1, 5, 2, 5]
[5, 5, 5, 1, 5, 3, 1]
[5, 5, 5, 1, 5, 3, 2]
[5, 5, 5, 1, 5, 3, 3]
[5, 5, 5, 1, 5, 3, 4]
[5, 5, 5, 1, 5, 3, 5]
[5, 5, 5, 1, 5, 4, 1]
[5, 5, 5, 1, 5, 4, 2]
[5, 5, 5, 1, 5, 4, 3]
[5, 5, 5, 1, 5, 4, 4]
[5, 5, 5, 1, 5, 4, 5]
[5, 5, 5, 1, 5, 5, 1]
[5, 5, 5, 1, 5, 5, 2]
[5, 5, 5, 1, 5, 5, 3]
[5, 5, 5, 1, 5, 5, 4]
[5, 5, 5, 1, 5, 5, 5]
[5, 5, 5, 2, 1, 1, 1]
[5, 5, 5, 2, 1, 1, 2]
[5, 5, 5, 2, 1, 1, 3]
[5, 5, 5, 2, 1, 1, 4]
[5, 5, 5, 2, 1, 1, 5]
[5, 5, 5, 2, 1, 2, 1]
[5, 5, 5, 2, 1, 2, 2]
[5, 5, 5, 2, 1, 2, 3]
[5, 5, 5, 2, 1, 2, 4]
[5, 5, 5, 2, 1, 2, 5]
[5, 5, 5, 2, 1, 3, 1]
[5, 5, 5, 2, 1, 3, 2]
[5, 5, 5, 2, 1, 3, 3]
[5, 5, 5, 2, 1, 3, 4]
[5, 5, 5, 2, 1, 3, 5]
[5, 5, 5, 2, 1, 4, 1]
[5, 5, 5, 2, 1, 4, 2]
[5, 5, 5, 2, 1, 4, 3]
[5, 5, 5, 2, 1, 4, 4]
[5, 5, 5, 2, 1, 4, 5]
[5, 5, 5, 2, 1, 5, 1]
[5, 5, 5, 2, 1, 5, 2]
[5, 5, 5, 2, 1, 5, 3]
[5, 5, 5, 2, 1, 5, 4]
[5, 5, 5, 2, 1, 5, 5]
[5, 5, 5, 2, 2, 1, 1]
[5, 5, 5, 2, 2, 1, 2]
[5, 5, 5, 2, 2, 1, 3]
[5, 5, 5, 2, 2, 1, 4]
[5, 5, 5, 2, 2, 1, 5]
[5, 5, 5, 2, 2, 2, 1]
[5, 5, 5, 2, 2, 2, 2]
[5, 5, 5, 2, 2, 2, 3]
[5, 5, 5, 2, 2, 2, 4]
[5, 5, 5, 2, 2, 2, 5]
[5, 5, 5, 2, 2, 3, 1]
[5, 5, 5, 2, 2, 3, 2]
[5, 5, 5, 2, 2, 3, 3]
[5, 5, 5, 2, 2, 3, 4]
[5, 5, 5, 2, 2, 3, 5]
[5, 5, 5, 2, 2, 4, 1]
[5, 5, 5, 2, 2, 4, 2]
[5, 5, 5, 2, 2, 4, 3]
[5, 5, 5, 2, 2, 4, 4]
[5, 5, 5, 2, 2, 4, 5]
[5, 5, 5, 2, 2, 5, 1]
[5, 5, 5, 2, 2, 5, 2]
[5, 5, 5, 2, 2, 5, 3]
[5, 5, 5, 2, 2, 5, 4]
[5, 5, 5, 2, 2, 5, 5]
[5, 5, 5, 2, 3, 1, 1]
[5, 5, 5, 2, 3, 1, 2]
[5, 5, 5, 2, 3, 1, 3]
[5, 5, 5, 2, 3, 1, 4]
[5, 5, 5, 2, 3, 1, 5]
[5, 5, 5, 2, 3, 2, 1]
[5, 5, 5, 2, 3, 2, 2]
[5, 5, 5, 2, 3, 2, 3]
[5, 5, 5, 2, 3, 2, 4]
[5, 5, 5, 2, 3, 2, 5]
[5, 5, 5, 2, 3, 3, 1]
[5, 5, 5, 2, 3, 3, 2]
[5, 5, 5, 2, 3, 3, 3]
[5, 5, 5, 2, 3, 3, 4]
[5, 5, 5, 2, 3, 3, 5]
[5, 5, 5, 2, 3, 4, 1]
[5, 5, 5, 2, 3, 4, 2]
[5, 5, 5, 2, 3, 4, 3]
[5, 5, 5, 2, 3, 4, 4]
[5, 5, 5, 2, 3, 4, 5]
[5, 5, 5, 2, 3, 5, 1]
[5, 5, 5, 2, 3, 5, 2]
[5, 5, 5, 2, 3, 5, 3]
[5, 5, 5, 2, 3, 5, 4]
[5, 5, 5, 2, 3, 5, 5]
[5, 5, 5, 2, 4, 1, 1]
[5, 5, 5, 2, 4, 1, 2]
[5, 5, 5, 2, 4, 1, 3]
[5, 5, 5, 2, 4, 1, 4]
[5, 5, 5, 2, 4, 1, 5]
[5, 5, 5, 2, 4, 2, 1]
[5, 5, 5, 2, 4, 2, 2]
[5, 5, 5, 2, 4, 2, 3]
[5, 5, 5, 2, 4, 2, 4]
[5, 5, 5, 2, 4, 2, 5]
[5, 5, 5, 2, 4, 3, 1]
[5, 5, 5, 2, 4, 3, 2]
[5, 5, 5, 2, 4, 3, 3]
[5, 5, 5, 2, 4, 3, 4]
[5, 5, 5, 2, 4, 3, 5]
[5, 5, 5, 2, 4, 4, 1]
[5, 5, 5, 2, 4, 4, 2]
[5, 5, 5, 2, 4, 4, 3]
[5, 5, 5, 2, 4, 4, 4]
[5, 5, 5, 2, 4, 4, 5]
[5, 5, 5, 2, 4, 5, 1]
[5, 5, 5, 2, 4, 5, 2]
[5, 5, 5, 2, 4, 5, 3]
[5, 5, 5, 2, 4, 5, 4]
[5, 5, 5, 2, 4, 5, 5]
[5, 5, 5, 2, 5, 1, 1]
[5, 5, 5, 2, 5, 1, 2]
[5, 5, 5, 2, 5, 1, 3]
[5, 5, 5, 2, 5, 1, 4]
[5, 5, 5, 2, 5, 1, 5]
[5, 5, 5, 2, 5, 2, 1]
[5, 5, 5, 2, 5, 2, 2]
[5, 5, 5, 2, 5, 2, 3]
[5, 5, 5, 2, 5, 2, 4]
[5, 5, 5, 2, 5, 2, 5]
[5, 5, 5, 2, 5, 3, 1]
[5, 5, 5, 2, 5, 3, 2]
[5, 5, 5, 2, 5, 3, 3]
[5, 5, 5, 2, 5, 3, 4]
[5, 5, 5, 2, 5, 3, 5]
[5, 5, 5, 2, 5, 4, 1]
[5, 5, 5, 2, 5, 4, 2]
[5, 5, 5, 2, 5, 4, 3]
[5, 5, 5, 2, 5, 4, 4]
[5, 5, 5, 2, 5, 4, 5]
[5, 5, 5, 2, 5, 5, 1]
[5, 5, 5, 2, 5, 5, 2]
[5, 5, 5, 2, 5, 5, 3]
[5, 5, 5, 2, 5, 5, 4]
[5, 5, 5, 2, 5, 5, 5]
[5, 5, 5, 3, 1, 1, 1]
[5, 5, 5, 3, 1, 1, 2]
[5, 5, 5, 3, 1, 1, 3]
[5, 5, 5, 3, 1, 1, 4]
[5, 5, 5, 3, 1, 1, 5]
[5, 5, 5, 3, 1, 2, 1]
[5, 5, 5, 3, 1, 2, 2]
[5, 5, 5, 3, 1, 2, 3]
[5, 5, 5, 3, 1, 2, 4]
[5, 5, 5, 3, 1, 2, 5]
[5, 5, 5, 3, 1, 3, 1]
[5, 5, 5, 3, 1, 3, 2]
[5, 5, 5, 3, 1, 3, 3]
[5, 5, 5, 3, 1, 3, 4]
[5, 5, 5, 3, 1, 3, 5]
[5, 5, 5, 3, 1, 4, 1]
[5, 5, 5, 3, 1, 4, 2]
[5, 5, 5, 3, 1, 4, 3]
[5, 5, 5, 3, 1, 4, 4]
[5, 5, 5, 3, 1, 4, 5]
[5, 5, 5, 3, 1, 5, 1]
[5, 5, 5, 3, 1, 5, 2]
[5, 5, 5, 3, 1, 5, 3]
[5, 5, 5, 3, 1, 5, 4]
[5, 5, 5, 3, 1, 5, 5]
[5, 5, 5, 3, 2, 1, 1]
[5, 5, 5, 3, 2, 1, 2]
[5, 5, 5, 3, 2, 1, 3]
[5, 5, 5, 3, 2, 1, 4]
[5, 5, 5, 3, 2, 1, 5]
[5, 5, 5, 3, 2, 2, 1]
[5, 5, 5, 3, 2, 2, 2]
[5, 5, 5, 3, 2, 2, 3]
[5, 5, 5, 3, 2, 2, 4]
[5, 5, 5, 3, 2, 2, 5]
[5, 5, 5, 3, 2, 3, 1]
[5, 5, 5, 3, 2, 3, 2]
[5, 5, 5, 3, 2, 3, 3]
[5, 5, 5, 3, 2, 3, 4]
[5, 5, 5, 3, 2, 3, 5]
[5, 5, 5, 3, 2, 4, 1]
[5, 5, 5, 3, 2, 4, 2]
[5, 5, 5, 3, 2, 4, 3]
[5, 5, 5, 3, 2, 4, 4]
[5, 5, 5, 3, 2, 4, 5]
[5, 5, 5, 3, 2, 5, 1]
[5, 5, 5, 3, 2, 5, 2]
[5, 5, 5, 3, 2, 5, 3]
[5, 5, 5, 3, 2, 5, 4]
[5, 5, 5, 3, 2, 5, 5]
[5, 5, 5, 3, 3, 1, 1]
[5, 5, 5, 3, 3, 1, 2]
[5, 5, 5, 3, 3, 1, 3]
[5, 5, 5, 3, 3, 1, 4]
[5, 5, 5, 3, 3, 1, 5]
[5, 5, 5, 3, 3, 2, 1]
[5, 5, 5, 3, 3, 2, 2]
[5, 5, 5, 3, 3, 2, 3]
[5, 5, 5, 3, 3, 2, 4]
[5, 5, 5, 3, 3, 2, 5]
[5, 5, 5, 3, 3, 3, 1]
[5, 5, 5, 3, 3, 3, 2]
[5, 5, 5, 3, 3, 3, 3]
[5, 5, 5, 3, 3, 3, 4]
[5, 5, 5, 3, 3, 3, 5]
[5, 5, 5, 3, 3, 4, 1]
[5, 5, 5, 3, 3, 4, 2]
[5, 5, 5, 3, 3, 4, 3]
[5, 5, 5, 3, 3, 4, 4]
[5, 5, 5, 3, 3, 4, 5]
[5, 5, 5, 3, 3, 5, 1]
[5, 5, 5, 3, 3, 5, 2]
[5, 5, 5, 3, 3, 5, 3]
[5, 5, 5, 3, 3, 5, 4]
[5, 5, 5, 3, 3, 5, 5]
[5, 5, 5, 3, 4, 1, 1]
[5, 5, 5, 3, 4, 1, 2]
[5, 5, 5, 3, 4, 1, 3]
[5, 5, 5, 3, 4, 1, 4]
[5, 5, 5, 3, 4, 1, 5]
[5, 5, 5, 3, 4, 2, 1]
[5, 5, 5, 3, 4, 2, 2]
[5, 5, 5, 3, 4, 2, 3]
[5, 5, 5, 3, 4, 2, 4]
[5, 5, 5, 3, 4, 2, 5]
[5, 5, 5, 3, 4, 3, 1]
[5, 5, 5, 3, 4, 3, 2]
[5, 5, 5, 3, 4, 3, 3]
[5, 5, 5, 3, 4, 3, 4]
[5, 5, 5, 3, 4, 3, 5]
[5, 5, 5, 3, 4, 4, 1]
[5, 5, 5, 3, 4, 4, 2]
[5, 5, 5, 3, 4, 4, 3]
[5, 5, 5, 3, 4, 4, 4]
[5, 5, 5, 3, 4, 4, 5]
[5, 5, 5, 3, 4, 5, 1]
[5, 5, 5, 3, 4, 5, 2]
[5, 5, 5, 3, 4, 5, 3]
[5, 5, 5, 3, 4, 5, 4]
[5, 5, 5, 3, 4, 5, 5]
[5, 5, 5, 3, 5, 1, 1]
[5, 5, 5, 3, 5, 1, 2]
[5, 5, 5, 3, 5, 1, 3]
[5, 5, 5, 3, 5, 1, 4]
[5, 5, 5, 3, 5, 1, 5]
[5, 5, 5, 3, 5, 2, 1]
[5, 5, 5, 3, 5, 2, 2]
[5, 5, 5, 3, 5, 2, 3]
[5, 5, 5, 3, 5, 2, 4]
[5, 5, 5, 3, 5, 2, 5]
[5, 5, 5, 3, 5, 3, 1]
[5, 5, 5, 3, 5, 3, 2]
[5, 5, 5, 3, 5, 3, 3]
[5, 5, 5, 3, 5, 3, 4]
[5, 5, 5, 3, 5, 3, 5]
[5, 5, 5, 3, 5, 4, 1]
[5, 5, 5, 3, 5, 4, 2]
[5, 5, 5, 3, 5, 4, 3]
[5, 5, 5, 3, 5, 4, 4]
[5, 5, 5, 3, 5, 4, 5]
[5, 5, 5, 3, 5, 5, 1]
[5, 5, 5, 3, 5, 5, 2]
[5, 5, 5, 3, 5, 5, 3]
[5, 5, 5, 3, 5, 5, 4]
[5, 5, 5, 3, 5, 5, 5]
[5, 5, 5, 4, 1, 1, 1]
[5, 5, 5, 4, 1, 1, 2]
[5, 5, 5, 4, 1, 1, 3]
[5, 5, 5, 4, 1, 1, 4]
[5, 5, 5, 4, 1, 1, 5]
[5, 5, 5, 4, 1, 2, 1]
[5, 5, 5, 4, 1, 2, 2]
[5, 5, 5, 4, 1, 2, 3]
[5, 5, 5, 4, 1, 2, 4]
[5, 5, 5, 4, 1, 2, 5]
[5, 5, 5, 4, 1, 3, 1]
[5, 5, 5, 4, 1, 3, 2]
[5, 5, 5, 4, 1, 3, 3]
[5, 5, 5, 4, 1, 3, 4]
[5, 5, 5, 4, 1, 3, 5]
[5, 5, 5, 4, 1, 4, 1]
[5, 5, 5, 4, 1, 4, 2]
[5, 5, 5, 4, 1, 4, 3]
[5, 5, 5, 4, 1, 4, 4]
[5, 5, 5, 4, 1, 4, 5]
[5, 5, 5, 4, 1, 5, 1]
[5, 5, 5, 4, 1, 5, 2]
[5, 5, 5, 4, 1, 5, 3]
[5, 5, 5, 4, 1, 5, 4]
[5, 5, 5, 4, 1, 5, 5]
[5, 5, 5, 4, 2, 1, 1]
[5, 5, 5, 4, 2, 1, 2]
[5, 5, 5, 4, 2, 1, 3]
[5, 5, 5, 4, 2, 1, 4]
[5, 5, 5, 4, 2, 1, 5]
[5, 5, 5, 4, 2, 2, 1]
[5, 5, 5, 4, 2, 2, 2]
[5, 5, 5, 4, 2, 2, 3]
[5, 5, 5, 4, 2, 2, 4]
[5, 5, 5, 4, 2, 2, 5]
[5, 5, 5, 4, 2, 3, 1]
[5, 5, 5, 4, 2, 3, 2]
[5, 5, 5, 4, 2, 3, 3]
[5, 5, 5, 4, 2, 3, 4]
[5, 5, 5, 4, 2, 3, 5]
[5, 5, 5, 4, 2, 4, 1]
[5, 5, 5, 4, 2, 4, 2]
[5, 5, 5, 4, 2, 4, 3]
[5, 5, 5, 4, 2, 4, 4]
[5, 5, 5, 4, 2, 4, 5]
[5, 5, 5, 4, 2, 5, 1]
[5, 5, 5, 4, 2, 5, 2]
[5, 5, 5, 4, 2, 5, 3]
[5, 5, 5, 4, 2, 5, 4]
[5, 5, 5, 4, 2, 5, 5]
[5, 5, 5, 4, 3, 1, 1]
[5, 5, 5, 4, 3, 1, 2]
[5, 5, 5, 4, 3, 1, 3]
[5, 5, 5, 4, 3, 1, 4]
[5, 5, 5, 4, 3, 1, 5]
[5, 5, 5, 4, 3, 2, 1]
[5, 5, 5, 4, 3, 2, 2]
[5, 5, 5, 4, 3, 2, 3]
[5, 5, 5, 4, 3, 2, 4]
[5, 5, 5, 4, 3, 2, 5]
[5, 5, 5, 4, 3, 3, 1]
[5, 5, 5, 4, 3, 3, 2]
[5, 5, 5, 4, 3, 3, 3]
[5, 5, 5, 4, 3, 3, 4]
[5, 5, 5, 4, 3, 3, 5]
[5, 5, 5, 4, 3, 4, 1]
[5, 5, 5, 4, 3, 4, 2]
[5, 5, 5, 4, 3, 4, 3]
[5, 5, 5, 4, 3, 4, 4]
[5, 5, 5, 4, 3, 4, 5]
[5, 5, 5, 4, 3, 5, 1]
[5, 5, 5, 4, 3, 5, 2]
[5, 5, 5, 4, 3, 5, 3]
[5, 5, 5, 4, 3, 5, 4]
[5, 5, 5, 4, 3, 5, 5]
[5, 5, 5, 4, 4, 1, 1]
[5, 5, 5, 4, 4, 1, 2]
[5, 5, 5, 4, 4, 1, 3]
[5, 5, 5, 4, 4, 1, 4]
[5, 5, 5, 4, 4, 1, 5]
[5, 5, 5, 4, 4, 2, 1]
[5, 5, 5, 4, 4, 2, 2]
[5, 5, 5, 4, 4, 2, 3]
[5, 5, 5, 4, 4, 2, 4]
[5, 5, 5, 4, 4, 2, 5]
[5, 5, 5, 4, 4, 3, 1]
[5, 5, 5, 4, 4, 3, 2]
[5, 5, 5, 4, 4, 3, 3]
[5, 5, 5, 4, 4, 3, 4]
[5, 5, 5, 4, 4, 3, 5]
[5, 5, 5, 4, 4, 4, 1]
[5, 5, 5, 4, 4, 4, 2]
[5, 5, 5, 4, 4, 4, 3]
[5, 5, 5, 4, 4, 4, 4]
[5, 5, 5, 4, 4, 4, 5]
[5, 5, 5, 4, 4, 5, 1]
[5, 5, 5, 4, 4, 5, 2]
[5, 5, 5, 4, 4, 5, 3]
[5, 5, 5, 4, 4, 5, 4]
[5, 5, 5, 4, 4, 5, 5]
[5, 5, 5, 4, 5, 1, 1]
[5, 5, 5, 4, 5, 1, 2]
[5, 5, 5, 4, 5, 1, 3]
[5, 5, 5, 4, 5, 1, 4]
[5, 5, 5, 4, 5, 1, 5]
[5, 5, 5, 4, 5, 2, 1]
[5, 5, 5, 4, 5, 2, 2]
[5, 5, 5, 4, 5, 2, 3]
[5, 5, 5, 4, 5, 2, 4]
[5, 5, 5, 4, 5, 2, 5]
[5, 5, 5, 4, 5, 3, 1]
[5, 5, 5, 4, 5, 3, 2]
[5, 5, 5, 4, 5, 3, 3]
[5, 5, 5, 4, 5, 3, 4]
[5, 5, 5, 4, 5, 3, 5]
[5, 5, 5, 4, 5, 4, 1]
[5, 5, 5, 4, 5, 4, 2]
[5, 5, 5, 4, 5, 4, 3]
[5, 5, 5, 4, 5, 4, 4]
[5, 5, 5, 4, 5, 4, 5]
[5, 5, 5, 4, 5, 5, 1]
[5, 5, 5, 4, 5, 5, 2]
[5, 5, 5, 4, 5, 5, 3]
[5, 5, 5, 4, 5, 5, 4]
[5, 5, 5, 4, 5, 5, 5]
[5, 5, 5, 5, 1, 1, 1]
[5, 5, 5, 5, 1, 1, 2]
[5, 5, 5, 5, 1, 1, 3]
[5, 5, 5, 5, 1, 1, 4]
[5, 5, 5, 5, 1, 1, 5]
[5, 5, 5, 5, 1, 2, 1]
[5, 5, 5, 5, 1, 2, 2]
[5, 5, 5, 5, 1, 2, 3]
[5, 5, 5, 5, 1, 2, 4]
[5, 5, 5, 5, 1, 2, 5]
[5, 5, 5, 5, 1, 3, 1]
[5, 5, 5, 5, 1, 3, 2]
[5, 5, 5, 5, 1, 3, 3]
[5, 5, 5, 5, 1, 3, 4]
[5, 5, 5, 5, 1, 3, 5]
[5, 5, 5, 5, 1, 4, 1]
[5, 5, 5, 5, 1, 4, 2]
[5, 5, 5, 5, 1, 4, 3]
[5, 5, 5, 5, 1, 4, 4]
[5, 5, 5, 5, 1, 4, 5]
[5, 5, 5, 5, 1, 5, 1]
[5, 5, 5, 5, 1, 5, 2]
[5, 5, 5, 5, 1, 5, 3]
[5, 5, 5, 5, 1, 5, 4]
[5, 5, 5, 5, 1, 5, 5]
[5, 5, 5, 5, 2, 1, 1]
[5, 5, 5, 5, 2, 1, 2]
[5, 5, 5, 5, 2, 1, 3]
[5, 5, 5, 5, 2, 1, 4]
[5, 5, 5, 5, 2, 1, 5]
[5, 5, 5, 5, 2, 2, 1]
[5, 5, 5, 5, 2, 2, 2]
[5, 5, 5, 5, 2, 2, 3]
[5, 5, 5, 5, 2, 2, 4]
[5, 5, 5, 5, 2, 2, 5]
[5, 5, 5, 5, 2, 3, 1]
[5, 5, 5, 5, 2, 3, 2]
[5, 5, 5, 5, 2, 3, 3]
[5, 5, 5, 5, 2, 3, 4]
[5, 5, 5, 5, 2, 3, 5]
[5, 5, 5, 5, 2, 4, 1]
[5, 5, 5, 5, 2, 4, 2]
[5, 5, 5, 5, 2, 4, 3]
[5, 5, 5, 5, 2, 4, 4]
[5, 5, 5, 5, 2, 4, 5]
[5, 5, 5, 5, 2, 5, 1]
[5, 5, 5, 5, 2, 5, 2]
[5, 5, 5, 5, 2, 5, 3]
[5, 5, 5, 5, 2, 5, 4]
[5, 5, 5, 5, 2, 5, 5]
[5, 5, 5, 5, 3, 1, 1]
[5, 5, 5, 5, 3, 1, 2]
[5, 5, 5, 5, 3, 1, 3]
[5, 5, 5, 5, 3, 1, 4]
[5, 5, 5, 5, 3, 1, 5]
[5, 5, 5, 5, 3, 2, 1]
[5, 5, 5, 5, 3, 2, 2]
[5, 5, 5, 5, 3, 2, 3]
[5, 5, 5, 5, 3, 2, 4]
[5, 5, 5, 5, 3, 2, 5]
[5, 5, 5, 5, 3, 3, 1]
[5, 5, 5, 5, 3, 3, 2]
[5, 5, 5, 5, 3, 3, 3]
[5, 5, 5, 5, 3, 3, 4]
[5, 5, 5, 5, 3, 3, 5]
[5, 5, 5, 5, 3, 4, 1]
[5, 5, 5, 5, 3, 4, 2]
[5, 5, 5, 5, 3, 4, 3]
[5, 5, 5, 5, 3, 4, 4]
[5, 5, 5, 5, 3, 4, 5]
[5, 5, 5, 5, 3, 5, 1]
[5, 5, 5, 5, 3, 5, 2]
[5, 5, 5, 5, 3, 5, 3]
[5, 5, 5, 5, 3, 5, 4]
[5, 5, 5, 5, 3, 5, 5]
[5, 5, 5, 5, 4, 1, 1]
[5, 5, 5, 5, 4, 1, 2]
[5, 5, 5, 5, 4, 1, 3]
[5, 5, 5, 5, 4, 1, 4]
[5, 5, 5, 5, 4, 1, 5]
[5, 5, 5, 5, 4, 2, 1]
[5, 5, 5, 5, 4, 2, 2]
[5, 5, 5, 5, 4, 2, 3]
[5, 5, 5, 5, 4, 2, 4]
[5, 5, 5, 5, 4, 2, 5]
[5, 5, 5, 5, 4, 3, 1]
[5, 5, 5, 5, 4, 3, 2]
[5, 5, 5, 5, 4, 3, 3]
[5, 5, 5, 5, 4, 3, 4]
[5, 5, 5, 5, 4, 3, 5]
[5, 5, 5, 5, 4, 4, 1]
[5, 5, 5, 5, 4, 4, 2]
[5, 5, 5, 5, 4, 4, 3]
[5, 5, 5, 5, 4, 4, 4]
[5, 5, 5, 5, 4, 4, 5]
[5, 5, 5, 5, 4, 5, 1]
[5, 5, 5, 5, 4, 5, 2]
[5, 5, 5, 5, 4, 5, 3]
[5, 5, 5, 5, 4, 5, 4]
[5, 5, 5, 5, 4, 5, 5]
[5, 5, 5, 5, 5, 1, 1]
[5, 5, 5, 5, 5, 1, 2]
[5, 5, 5, 5, 5, 1, 3]
[5, 5, 5, 5, 5, 1, 4]
[5, 5, 5, 5, 5, 1, 5]
[5, 5, 5, 5, 5, 2, 1]
[5, 5, 5, 5, 5, 2, 2]
[5, 5, 5, 5, 5, 2, 3]
[5, 5, 5, 5, 5, 2, 4]
[5, 5, 5, 5, 5, 2, 5]
[5, 5, 5, 5, 5, 3, 1]
[5, 5, 5, 5, 5, 3, 2]
[5, 5, 5, 5, 5, 3, 3]
[5, 5, 5, 5, 5, 3, 4]
[5, 5, 5, 5, 5, 3, 5]
[5, 5, 5, 5, 5, 4, 1]
[5, 5, 5, 5, 5, 4, 2]
[5, 5, 5, 5, 5, 4, 3]
[5, 5, 5, 5, 5, 4, 4]
[5, 5, 5, 5, 5, 4, 5]
[5, 5, 5, 5, 5, 5, 1]
[5, 5, 5, 5, 5, 5, 2]
[5, 5, 5, 5, 5, 5, 3]
[5, 5, 5, 5, 5, 5, 4]
[5, 5, 5, 5, 5, 5, 5]
Pocet: 78125

5**7

78125

def bez_opakovania(pole):
    n = len(pole)
    for i in range(n):
        for j in range(n):
            if pole[i] == pole[j]:
                return False
    return True

bez_opakovania([1,2,3]) #nefunguje

False

def bez_opakovania(pole):
    n = len(pole)
    for i in range(n):
        for j in range(n):
            if i != j and pole[i] == pole[j]: #iba rozne indexy
                return False
    return True

bez_opakovania([1,2,3])

True

všetky $n$-prvkové postupnosti čísel $1..k$ bez opakovania

hrubou silou ... všetky aj s opakovaním a pred výpisom skontrolujeme či sa neopakujú $O(k^n \cdot n^2)$

backtrack ... pri vnáraní do rekurzie kontrolujeme či už dané číslo je použité v doteraz vygenerovaj časti

backtrack2 ... pamätáme si použité čísla a vnárame iba ak ešte nebolo použité ... $O(k \cdot (k-1) \cdot \dots \cdot(k-n+1)) \in O\left(\frac{k!}{(k-n)!}\right) \subset O(k!) \subset O(k^n)$

%%time
#kontrola pri vypisovani

n, k = 9, 10
pole = [0]*n #vytvorime n-prvkove pole
pocet = 0

def opakuje():
    for i in range(len(pole)-1): # 0 <= i < len(pole)
        for j in range(i+1, len(pole)): # i < j
            if pole[i] == pole[j]:
                return True
    return False

def gen(uroven): #uroven - ktory index ideme generovat =  kolko prkov uz mame vygenerovanych
    global pocet
    if uroven == n:
        if not opakuje():
            pocet += 1
        return
    for i in range(1, k+1):
        pole[uroven] = i
        gen(uroven+1)
    
gen(0)
print(pocet)

3628800
Wall time: 22min 29s

%%time
#kontrola pri generovani

n, k = 9, 10
pole = [0]*n #vytvorime n-prvkove pole
pocet = 0

def gen(uroven): #uroven - ktory index ideme generovat =  kolko prkov uz mame vygenerovanych
    global pocet
    if uroven == n:
        pocet += 1
        return
    for i in range(1, k+1):
        if not i in pole[:uroven]: #ak este i nebolo
            pole[uroven] = i
            gen(uroven+1)
    
gen(0)
print(pocet)

3628800
Wall time: 9.23 s

%%time
#pametanie si pouzitych cisel

n, k = 9, 10
pole = [0]*n #vytvorime n-prvkove pole
bolo = [False]*(k+1) #False - este nebolo pouzite
pocet = 0

def gen(uroven): #uroven - ktory index ideme generovat =  kolko prkov uz mame vygenerovanych
    global pocet
    if uroven == n:
        pocet += 1
        return
    for i in range(1, k+1):
        if not bolo[i]: #ak este i nebolo
            pole[uroven] = i
            bolo[i] = True
            gen(uroven+1)
            bolo[i] = False
    
gen(0)
print(pocet)

3628800
Wall time: 5.06 s

Rozdeľuj a panuj

Metóda založená na rozdelení problému na menšie podproblémy, pričom riešenia týchto menších podproblémov sa nájdu ľahšie a pomocou nich bude možné poskladať riešenie pôvodného problému. Spoločnými troma krokmi týchto algoritmov je:

• Rozdelenie na niekoľko menších a nezávislých podproblémov,
• Rekurzívne vypočítanie každého menšieho podproblému a
• Zlúčenie riešení podproblémov do celkového riešenia.

• merge sort (usporiadanie spájaním)
• binárne vyhľadávanie pole[n] ... stred=n//2, pole[:stred], pole[stred:]
• quick sort (rýchle usporiadanie) v optimálnom prípade

Pre vám známe algoritmy platí:

Algoritmus	Rozdelenie	Rekurzia	Zlúčenie	Rekurentný vzťah
Binárne vyhľadávanie (BinarySearch)	$$O\left(1\right)$$	$$T\left(\frac{n}{2}\right)$$	$$O\left(1\right)$$	$$T\left(n\right) = T\left(\frac{n}{2}\right)+1$$
Usporiadanie spájaním (MergeSort)	$$O\left(1\right)$$	$$2\cdot T\left(\frac{n}{2}\right)$$	$$O\left(n\right)$$	$$T\left(n\right) = 2\cdot T\left(\frac{n}{2}\right)+n$$
Rýchle usporiadanie (QuickSort) v optimálnom prípade	$$O\left(n\right)$$	$$2\cdot T\left(\frac{n}{2}\right)$$	$$O(1)$$	$$T\left(n\right) = 2\cdot T\left(\frac{n}{2}\right)+n$$

Uvedený rekuretný vzťah pri usporiadaní spájaním je matematicky korektný len pre n mocniny dvojky, presný zápis by bol $ T\left(n\right) = T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+T\left(\left\lceil\frac{n}{2}\right\rceil\right)+n $.

Výpočet zložitosti pre rekurentné vzťahy

Metóda Rozdeľuj a panuj zvyčajne rozdelí problém na niekoľko ($a$) menších podproblémov zlomkovej veľkosti ($b$-tiny), teda výsledný rekurentný vzťah má tvar $T\left(n\right) = a\cdot T\left(\frac{n}{b}\right)+f(n)$. Na jeho riešenie sa používa nasledujúca veta.

Hlavná veta (Master Theorem)

Rekurentný vzťah $T\left(n\right) = a\cdot T\left(\frac{n}{b}\right)+f(n)$, pričom $a ≥ 1, b > 1$ má riešenie:

• Ak pre nejakú konštantu $\epsilon > 0$ platí $f\left(n\right) = O\left(n^{\log_b (a)-\epsilon}\right)$, tak $T(n)=\Theta\left(n^{\log_b a}\right)$
• Ak pre nejakú konštantu $k ≥ 0$ platí $f\left(n\right) = \Theta\left(n^{\log_b a}\cdot\log^k n\right)$, tak $T\left(n\right)=\Theta\left(n^{\log_b a}\cdot \log^{k+1} n\right)$
• Ak pre nejakú konštantu $\epsilon > 0$ platí $f(n) = \Omega(n^{\log_b (a)+\epsilon})$

a zároveň pre nejakú konštantu $c > 1$ a dostatočné veľké $n$ platí $a\cdot f\left(\frac{n}{b}\right) ≤ c\cdot f(n)$,

tak $T\left(n\right)=\Theta\left(f\left(n\right)\right)$

Na výpočet zložitosti teda treba rádovo porovnať $f\left(n\right)$ a $n^{\log_b a}$.

v podstate porovnáme $f(n)$ a $n^{\log_b a}$

Príklad 1

Riešme rekurentný vzťah $T(n) = 8.T\left(\frac{n}{2}\right)+1000n^2$.

a = 8
b = 2
f(n) = 1000.n^2

$n^{\log_b a} = n^{\log_2 8} = n^3$ ... vidíme, že $n^2 < n^3$, teda prvý prípad hlavnej vety

• Ak pre nejakú konštantu $\epsilon > 0$ platí $f\left(n\right) = O\left(n^{\log_b (a)-\epsilon}\right)$, tak $T(n)=\Theta\left(n^{\log_b a}\right)$

napr. pre $\epsilon = 1$

a teda $T(n)=\Theta\left(n^{\log_b a}\right) = \Theta(n^3)$ .

Príklad 2

Riešme rekurentný vzťah $T(n) = 2.T\left(\frac{n}{2}\right)+10n$.

a = 2
b = 2
f(n) = 10n

$n^{\log_b a} = n^{\log_2 2} = n^1 = n$ ... druhý prípad

• Ak pre nejakú konštantu $k ≥ 0$ platí $f\left(n\right) = \Theta\left(n^{\log_b a}\cdot\log^k n\right)$, tak $T\left(n\right)=\Theta\left(n^{\log_b a}\cdot \log^{k+1} n\right)$

pre $k = 0$, a teda $T(n)=\theta\left(n^{\log_b a}\cdot \log^{k+1} n\right) = \theta\left(n^{\log_2 2}\cdot \log^{0+1} n\right) = \Theta(n \cdot \log n)$

Menej zvyčajný tvar (dôsledok)

Ak pre rekurentný vzťah $T(n) = a\cdot T\left(\frac{n}{b}\right)+f(n), a ≥ 1, b > 1$

je $\frac{a\cdot f\left(\frac{n}{b}\right)}{f(n)} = k$ konštanta, tak

• Ak $k > 1$, tak $T(n)=\Theta\left(n^{log_b a}\right)$
• Ak $k = 1$, tak $T(n)=\Theta\left(f(n)\cdot\log_b n\right)$
• Ak $k < 1$, tak $T(n)=\Theta\left(f\left(n\right)\right)$

Príklad

Majme rekuretný vzťah $T(n) = 2 \cdot T\left(\frac{n}{2}\right)+n^2$.

$a=b=2, f(n)=n^2$

$\frac{a\cdot f\left(\frac{n}{b}\right)}{f(n)} = \frac{2\cdot f\left(\frac{n}{2}\right)}{n^2}= \frac{2\cdot \frac{n^2}{4}}{n^2}= \frac{1}{2} < 1 $

teda $T(n)=\Theta\left(f\left(n\right)\right) = \Theta\left(n^2\right)$

Akra-Bazzi Theorem (zovšeobecnenie Hlavnej vety)

Na riešenie komplikovanejších rekurentných vzťahov, aj na hornú a dolnú celú časť, je možné použiť Akra-Bazziho vetu:

Nech $\displaystyle T(n)=g(n)+\sum _{{i=1}}^{k}a_{i}T\left(b_{i}n+h_{i}\left(n\right)\right)$ pre $n\geq n_{0}$, pričom

• $n_0$, $a_i > 0$, $0 < b_i < 1$ sú konštanty
• $\left|g(n)\right|\in O\left(n^{c}\right)$, kde $c$ je konštanta
• $\left|h_{i}(n)\right|\in O\left({\frac {n}{\log^2 n}}\right)$
• $\displaystyle \sum _{{i=1}}^{k}a_{i}b_{i}^{p}=1$ .

Potom platí $$\displaystyle T(n)\in \Theta \left(n^{p}\cdot\left(1+\int _{1}^{n}{\frac {g(u)}{u^{{p+1}}}}du\right)\right)$$.

Príklad

Riešením rekurentného vzťahu $ T\left(n\right) = T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+T\left(\left\lceil\frac{n}{2}\right\rceil\right)+n $ je dosadením $a_0 = a_1 = 1, b_0 = b_1 = \frac{1}{2}$, $g(n) = n$, $h_1(n) = \lfloor\frac{n}{2}\rfloor-\frac{n}{2}$, $h_2(n) = \lceil\frac{n}{2}\rceil-\frac{n}{2}$ nájdenie $p$ pre ktoré platí $\left(\frac{1}{2}\right)^p+\left(\frac{1}{2}\right)^p = 1 $, t.j. $p=1$. Asymptotická zložitosť teda je $ n^{1} \cdot \left(1+\int _{1}^{n}{\frac {u}{u^{{1+1}}}}du\right) = n\cdot\left(1+\int _{1}^{n}{\frac{1}{u}}du\right) = n\cdot\left(1+\left[\ln u\right]_{u=1}^{n}\right) = n\cdot(1+\ln n-\ln 1) = n+n\cdot\ln n$, čo znamená $T(n) \in \Theta(n \cdot \log n)$.

Rozdeľuj a panuj exponencionálne

Niekedy sa metódou Rozdeľuj a panuj podarí veľkosť zmenšiť na menší podproblém iba o nejakú konštantu. Riešením je potom exponencionálna funkcia.

Nech $T(n) = T(n-a_1)+T(n-a_2)+...+T(n-a_k)+f(n)$, pričom $a_i > 0$. Potom $T(n) \in O\left(n^y . x^n\right), y \in N, x^{n}-x^{n-a_1}-...-x^{n-a_k}=0$, pričom existuje práve jedno kladné reálne $x$ vyhovujúce tejto rovnici.

Príklad 1

Generovanie všetkých podmnožín, pričom pre daný prvok máme dve možnosti zobrať-nezobrať.

Pre rekurentný vzťah $T(n) = T(n-1)+T(n-1)$

Máme $x^n-x^{n-1}-x^{n-1}=0$, po vydelení $x^{n-1}$ dostávame $x-1-1=0$, t.j. $x=2$, $T(n) \in Ô(2^n)$, kde polynomiálnu časť zanedbávame.

Príklad 2

[ http://oi.sk/archiv/2019/sl-2019-1-zad-A.pdf ]

$T(n) = T(n-1)+T(n-3)$

$T(n) = T(n-1)+T(n-3)$, teda $x^n-x^{n-1}-x^{n-3}=0$, po vydelení $x^{n-3}$ dostávame $x^3-x^2-1=0$, t.j. $x=1.46557$, $T(n) \in Ô(1.46557^n)$

Vypočítať možeme napr. na WolframAlpha alebo pomocou programu Maxima.

import numpy as np
r = np.roots([1, -1, 0, -1])
print('Korene:', r)
r = r[np.isreal(r)]
print('Zložitosť:', max(np.real(r[r > 0])))

Korene: [ 1.46557123+0.j         -0.23278562+0.79255199j -0.23278562-0.79255199j]
Zložitosť: 1.4655712318767682

Zoraďte podľa asymptotickej zložitosti (od najmenšej):

$n.\ln n, \ln n, n^{\frac{3}{2}}, \log n, 2^{\ln n}, \ln 2^n, \sqrt{n}, \log_4 n, \log_{200} n, n, 2^n, n^5, \ln \ln n, n^2$

Súčet

n = int(input())

3

for _ in range(n):
    a, b = [int(x) for x in input().split()]
    print(a+b)

15 60
75
12345678901234567890 12345678901234567890
24691357802469135780
12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
24691357802469135780246913578024691357802469135780246913578024691357802469135780246913578024691357802469135780246913578024691357802469135780

for _ in range(int(input())):    
    print(sum(map(int, input().split())))

3
1 2
3
1 2 3 4 5 6 7 8
36
123456789012345678901234567890 123456789012345678901234567890
246913578024691357802469135780

Praktická úloha Makovnik

2 3
7
8

máme 2 makovniky, veľkosti 7 a 8. Akú najväčšiu časť môže dostať jeden človek, ak všetci traja majú dostať rovnako.

Podaci listok(Simulacia)
# Hruba sila `Brute force`
Kombinatoricke algoritmy