## cvičení 7
## algoritmy nad seznamy
from random import randint, shuffle


# ÚLOHA 1A
# Naprogramujte funkci, která spočítá hodnoty v Pascalově trojúhelníku explicitně
# až po úroveň <level>. Funkce vrátí seznam jednotlivých pater trojúhelníku.
# Hodnoty spočítejte jako kombinační čísla.
# Navrhněte vhodné podfunkce.
def pascal_explicit(level):
    pass

# vzorový výstup:
# >>> result = pascal_explicit(5)
# >>> print(result)
# [[1], [1, 1), [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10 ,5, 1]]


# ÚLOHA 1B
# Naprogramujte funkci, která spočítá hodnoty v Pascalově trojúhelníku postupně
# z úrovní trojúhelníku.
def pascal_from_levels(level):
    pass

# vzorový výstup:
# >>> result = pascal_from_levels(5)
# >>> print(result)
# [[1], [1, 1), [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10 ,5, 1]]


# ÚLOHA 1C
# Naprogramujte funkci, která vytiskne pascalův trojúhelník z formátu, který vrací funkce z úloh 1A a 1B.
def print_pascal(level):
    pass

# vzorový výstup:
# >>> result = pascal_from_levels(5)
# >>> print_pascal(result)
#           1
#         1   1
#       1   2   1
#     1   3   3   1
#   1   4   6   4   1
# 1   5  10  10   5   1
#


# ÚLOHA 1D
# Naprogramujte funkci, která porovná časovou náročnost dvou implementací
# funkce počítající Pascalův trojúhelník.
def compare_pascal(pascal1, pascal2):
    pass


# ÚLOHA 2A
# Napište funkci, která vyhledá v setříděném seznamu <array> prvek <item>.
# Funkce buď vrátí index prvku, nebo None, pokud se prvek v seznamu nenachází.
# Seznam procházejte lineárně, nepoužívejte konstrukce <a in array> ani <array.index(a)>.
# Funkce bude čistá, nebude modifikovat zadaný seznam.
def my_search(numbers):
    pass

# vzorový výstup:
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> my_search(array, 42)
# 24
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> my_search(array, 42)
# None


# ÚLOHA 2B
# Napište funkci, která v binárně vyhledá v setříděném seznamu <array> prvek <item>.
# Funkce buď vrátí index prvku, nebo None, pokud se prvek v seznamu nenachází.
# Individálně nastudujte, jak funguje binární vyhledávání.
def binary_search(numbers):
    pass

# vzorový výstup:
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> binary_search(array, 42)
# 12
# >>> array = [randint(1, 1000) for _ in range(1000)]
# >>> array.sort()
# >>> binary_search(array, 42)
# None


# ÚLOHA 3A
# Naprogramujte funkci, která setřídí zadaný seznam. Algoritmus si zvolte sami.
# Váš algoritmus nesmí využívat funkce <sorted(array)> nebo <array.sort()>
def my_sort(numbers):
    pass


# vzorový výstup:
# >>> array = [randint(1, 100) for i in range(100)]
# >>> my_sort(array)
# [1, 2, 4, 5, 5, 7, 12, ..., 97, 99, 99]


# ÚLOHA 3B
# Naprogramujte funkci, která porovná časovou náročnost vašeho algoritmu <my_sort> a
# jedné z implementací <sorted(array)> nebo <array.sort()>
def compare_sort(array):
    pass


if __name__ == "__main__":
    # zde můžete volat implementované funkce a zkusit si, jak fungují
    pass
