6. Binární vyhledávání, testování, typy¶

6.1.1. Doplnění typů¶

Otypujte následující funkce. Funkce dice_max(count) vrací nejvyšší číslo, které padlo na kostce.

from random import randint

def dice():
    return randint(1, 6)

def dice_max(count):
    maximum = dice()
    for _ in range(count-1):
        roll = dice()
        if roll > maximum:
            maximum = roll
    return maximum

6.1.2. Doplnění assertu¶

Doplňte do předchozího kódu assert tak, aby funkce dice_max přijímala pouze count >= 1.

Assert napište na první řádek funkce. Bezprostředně za začátek funkce se často píší asserty, které udávají vstupní podmínky.

6.1.3. Pokročilejší doplnění typů¶

Upravte funkci dice_max z předchozího příkladu tak, aby umožňovala count == 0 a v takovém případě vrátila None. Upravte typy tak, aby mypy prošlo! Upravte assert a ponechte jej na začátku funkce.

6.1.4. Testování¶

Napište smysluplné testy (asserty) na funkci palindrom a opravte na základě testů její chyby.

def palindrom(text):
    length = len(text)
    for i in range((length-1)//2):
        if text[i] != text[length - 1 - i]:
            return False
    return True

def palindrom_test():
    assert palindrom('aa')
    assert not palindrom('abc')
    # Sem přidejte další případy

palindrom_test()

6.2.1. Hádání čísla člověkem¶

Napište funkci guess_number_human(upper_bound), která umožňuje hrát s počítačem hru na hádání čísla: počítač si myslí číslo (celé číslo v intervalu [1, upper_bound]), hráč se ho snaží uhodnout. Po každém pokusu dostane hráč od počítače informaci, zda je hledané číslo menší nebo větší než to, které si tipnul. Hru si můžete vyzkoušet zde (klikejte na čísla v pravé části).

from random import randint

def guess_number_human(upper_bound: int) -> None:
    pass

# --- pokus c. 1 ---
# Zadej svuj tip: 5
# Moje cislo je mensi.
# --- pokus c. 2 ---
# Zadej svuj tip: 3
# Moje cislo je vetsi.
# --- pokus c. 3 ---
# Zadej svuj tip: 4
# Jo, to je ono!
guess_number_human(10)

6.2.2. Hádání čísla počítačem¶

Napište funkci guess_number_pc(upper_bound), která umožňuje hrát s počítačem hru na hádání čísla, tentokrát si však číslo myslí uživatel a počítač hádá. Po každém pokusu si počítač vyžádá od uživatele informaci, zda je myšlené číslo větší nebo menší než to, které si počítač tipnul.

def guess_number_pc(upper_bound: int) -> None:
    pass

# Mysli si cislo od 1 do 10.
# Je cislo 5 mensi (0), rovno (1), nebo vetsi (2) nez tvoje cislo?
# 2
# Je cislo 2 mensi (0), rovno (1), nebo vetsi (2) nez tvoje cislo?
# 2
# Tvoje cislo je 1.
guess_number_pc(10)

6.2.3. Hádání čísla: počítač vs. počítač¶

Napište funkci guess_number_pc_pc(upper_bound), která vykoná hru v hádání myšleného čísla počítače proti počítači. Na závěr vypíše počet pokusů potřebných k uhádnutí čísla.

from random import randint

def guess_number_pc_pc(upper_bound: int) -> None:
    pass

# A: Myslim si cislo od 1 do 10
# --- pokus c. 1 ---
# B: Tipuji 5
# A: Moje cislo je mensi.
# --- pokus c. 2 ---
# B: Tipuji 2
# A: Moje cislo je vetsi.
# --- pokus c. 3 ---
# B: Tipuji 3
# A: Jo, to je ono!
# Uhadnuto na 3 pokusu
guess_number_pc_pc(10)

6.2.4. Binární vyhledávání¶

Napište funkci binary_search(needle, haystack), která zjistí, zda se hodnota needle nachází ve vzestupně uspořádaném seznamu haystack. Funkce musí mít logaritmickou časovou složitost.

def binary_search(needle: int, haystack: List[int]) -> bool:
    pass

def test_binary_search_basic() -> None:
    assert binary_search(5, [1, 2, 5, 8])
    assert not binary_search(4, [1, 2, 5, 8])

6.2.5. Otestování binárního vyhledávání¶

Napište funkci test_binary_search_extended a vložte do ní alespoň 5 testů předchozí funkce binary_search.

6.2.6. Binární vyhledávání pozice¶

Vylepšete předchozí funkci tak, aby vracela index pozice, kde se hledaný prvek nachází. Pokud prvek v seznamu není, vraťte -1.

def binary_search_position(needle: int, haystack: List[int]) -> int:
    pass

def test_binary_search_position() -> None:
    assert binary_search_position(5, [1, 2, 5, 8]) == 2
    assert binary_search_position(4, [1, 2, 5, 8]) == -1

6.2.7. Binární vyhledávání seznamu pozic¶

Vylepšete předchozí funkci tak, aby vracela seznam indexů pozic, na kterých se hledaný prvek vyskytuje. Pokud prvek v seznamu není ani jednou, vrátíte prázdný seznam.

def binary_search_position_list(needle: int, haystack: List[int]) -> List[int]:
    pass

def test_binary_search_position_list() -> None:
    assert binary_search_position_list(5, [1, 2, 3, 3, 5, 5, 5, 8]) == [4, 5, 6]
    assert binary_search_position_list(4, [1, 2, 5, 8]) == []

6.2.8. Umocňování¶

Napište funkci super_power(base, exp), která umocní dané číslo base na daný exponent exp. Funkce musí mít logaritmickou časovou složitost vzhledem k hodnotě exponentu.

def super_power(base: int, exp: int) -> int:
    pass

def test_super_power() -> None:
    assert super_power(2, 7) == 128
    assert super_power(5, 15) == 30517578125