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

6.1. Testování, typy

Otypování různých datových typů

seznam

List[T_e]

fronta

Deque[T_e]

množina

Set[T_e]

slovník

Dict[T_k, T_e]

union (jeden z typů)

Union[X, Y, Z, ...]

optional (buď typ nebo None)

Optional[T]

n-tice

Tuple[X, Y, Z, ...]

T_e je typ prvků T_k je typ klíče

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. Binární vyhledávání

V následující kapitole si vyzkoušíme jednoduchou techniku známou jako binární vyhledávání, na které si ilustrujeme, jak některé výpočetní úlohy mohou trvat až překvapivě krátkou dobu.

Následující úlohy budou převážně vycházet z následujícího zadání:

Hrajeme hru dvou hráčů. Jeden s hráčů si myslí číslo z předem zadaného intervalu a cílem druhého hráče je číslo uhodnout. K tomu používá otázky typu „Je číslo, které si myslíš, větší než X?“

Jaká je nejlepší strategie pro druhého hráče, aby položil co nejméně otázek?

Princip binárního vyhledávání

V případě, kdy by nás nezajímal počet otázek, které položíme, mohli bychom klást otázky postupně:

  • Je číslo, ktere si myslíš, větší než 1?

  • Je číslo, ktere si myslíš, větší než 2?

  • Je číslo, ktere si myslíš, větší než 3?

V nejhorším případě bychom položili tolik otázek, kolik je možných čísel, které si náš protihráč může myslet. Na druhou stranu bychom mohli položením otázky zkusit vyřadit, co nejvíce možností. Představme si, že si protihráč může myslet čísla od 1 do 1000. Jaká by měla být naše první otázka, aby vyřadila co nejvíce možností bez ohledu na to, jak na ni protihráč odpoví?

  • Je číslo, které si myslíš, větší než 500?

Bez ohledu na to, jak protihráč odpoví, se mi počet čísel, které musím uvažovat zmenší na polovinu. Představme si, že protihráč odpověděl na naší otázku „ANO“. Která čísla ještě připadají v úvahu? Jaká bude naše další otázka?

  • Je číslo, které si myslíš, větší než 750?

Touto otázkou se nám opět smrskne na polovinu. Když budeme v této strategii pokračovat a v každém kole se nám počet přípustných čísel zmenší na polovinu, jistě uhádneme protihráčovo číslo v nejhorším případě po desáté otázce. Obecně počet otázek v nejhorším případě odpovídá dvojkovému logaritmu počtu čísel, ze kterých se myšlené číslo vybírá.

Zkuste odhadnout, jaké budou výsledky následujících dvojkových logaritmů.

Uživatelský vstup

Abychom hru dokázali správně naimplementovat, budeme muset načítat vstup od uživatele. Na to můžeme použít již funkci input. Tato funkce umí vypsat na obrazovku danou instrukci a počkat na vstup od uživatele. Jakmile uživatel svůj vstup potvrdí, funkce vrátí řetězec obsahující to, co uživatel zadal. Pokud chceme s uživatelským vstupem dále pracovat jako jiným typem (například celé číslo), je vhodné použít přetypování.

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
Next Section - 7. Algoritmy nad seznamy