# Programování II pro matematiky ## Teoretické cvičení 14 **2. 6. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Řešení domácích úkolů - Poslední domácí úkol - Příklady --- ### Opakování - dynamické programování - Úlohu si rozdělíme na menší úlohy -> řešení menších úloh nám pomůže při řešení původní úlohy **Příklad:** ```python def fib(n: int) -> int: if n == 0: return 0 if n == 1: return 1 return fib(n − 1) + fib(n − 2) ``` Pomocí principu dynamického programování... ```python vysledky = {0: 0, 1: 1} def fib(n: int) -> int: if n not in vyledky: vysledky[n] = fib(n − 1) + fib(n − 2) return vysledky[n] ``` --- - bez dynamického programování
- Top-down přístup
- Bottom-up přístup --- ### Poslední domácí úkol viz zadání v [The Postal Owlu](https://kam.mff.cuni.cz/owl/c/p2m-mmr/08-last/)... --- ### Řešení domácího úkolu Chceme vypsat všechna korektní uzávorkování pomocí $N$ párů závorek. ... --- ### Obecné poznámky k domácím úkolům - Důvěra v Internet - Obecně je nutné hledat důvěryhodné zdroje (i mezi ostatními studenty) -- - Elektronická forma řešení bývá lepší (zápočtová dokumentace by měla být elektronicky) - Věci fungují lépe, když nejsou dělány na poslední chvíli. - Pokud něco umíte napsat krátce, tak to udělejte. Není dobré používat dopředné odkazy na další text ani psát detektivky. --- ### Příklady - Máme v řadě $N$ lahví. U každé lahve známe její objem. Chceme vypít, co nejvíce, ale nechceme pít ze dvou sousedních lahví. - Máme posloupnost $N$ čísel. Chceme vybrat čísla s minimálním součtem tak, že z každé trojice po sobě jdoucích čísel musí být vybráno alespoň jedno. - Editační vzdálenost řetězců: Chceme určit minimální počet operací potřebných k převodu jednoho zadaného znakového řetězce na druhý; povolené operace: vložení znaku, vynechání znaku, záměna znaku.
---