Složitost, implementace algoritmu

Opakování

• Podívali jsme se na jeden z problémů na doma z minula. Ukázali jsme si dva (velmi podobné) algoritmy, které jej řeší a to jak formou pseudokódu, tak formou implementace v C/Pythonu.
• Zopakovali jsme pojmy časové složitosti algoritmu v nejhorším a v průměrném příapdě. Určili jsme si časovou složitost obou algoritmů z předchozího bodu.
• Mluvili jsme o tom, že velikost vstupu může být pro různé algoritmy uvažováná různě (hodnota čísla, délka textu, kombinace velikostí více různých vstupů, …). Ukázali jsme si to i na příkladech.

Úkoly k procvičení

• Implementujte v jazyce C/Pythonu algoritmus pro sčítání dvou přirozených čísel, jak jej znáte ze ZŠ.
• Na tento úkol jste měli velkou část cvičení.
• Vždy po nějaké chvíli jsme si společně pověděli, jak to jde a co je potřeba udělat dál:
  • přístup k jednotkám v čísle x přes x % 10
  • přístup k desítkám v čísle přes ((x - x % 10) / 10 ) % 10
  • zkuste iterovat přes řády (tj jednotky, desítky, stovky, …) a zobecnit myšlenku z předchoích bodů
• Na konci hodiny jsme si společně prošli možné řešení v jazyce C i v Pythonu.