Algoritmizace – 2. cvičení

Hra s mincemi

Na stole leží 15 mincí. Dva hráči se střídají, každý vždy může ze stolu odebrat jednu, dvě, nebo tři mince. Vyhrává ten, kdo odebere poslední minci.

  1. Kolik mincí musí v prvním kole odebrat první hráč, aby vždy vyhrál, bez ohledu na strategii protihráče.

  2. Určete, při jakém počtu mincí na stole vždy vyhraje druhý hráč (v případě, že oba hráči hrají optimální strategii).

Složitost (O\mathcal{O})

Definice

Nechť f,g:N→R+f, g: \mathbb{N} \to \mathbb{R}^+.

Úlohy

Nechť f,g:N→R+f, g: \mathbb{N} \to \mathbb{R}^+. Dokažte nebo vyvraťte tato tvrzení:

  1. n2∈O(n3)n^2 \in \mathcal{O}(n^3),
  2. n3∈O(n2)n^3 \in \mathcal{O}(n^2)
  3. f∈O(g)  ⟹  g∈O(f)f \in \mathcal{O}(g) \implies g \in \mathcal{O}(f),
  4. f∈O(g)  ⟹  g∈Ω(f)f \in \mathcal{O}(g) \implies g \in \mathcal{\Omega}(f),
  5. f∈Θ(g)  ⟹  g∈O(f)f \in \mathcal{\Theta}(g) \implies g \in \mathcal{O}(f),
  6. f∈O(g)  ⟹  1f∈O(g)f \in \mathcal{O}(g) \implies \frac1f \in \mathcal{O}(g),
  7. f∈O(g)  ⟹  1f∈O(1g)f \in \mathcal{O}(g) \implies \frac1f \in \mathcal{O}\left(\frac1g\right),
  8. f∈O(g)∨g∈O(f)f \in \mathcal{O}(g) \vee g \in \mathcal{O}(f),
  9. f1∈O(g)∧f2∈O(g)  ⟹  f1+f2∈O(g)f_1 \in \mathcal{O}(g) \wedge f_2 \in \mathcal{O}(g) \implies f_1 + f_2 \in \mathcal{O}(g).

Moje poznámky (ne úplně vzorové řešení, ale všechny hlavní myšlenky by tam měly být).