Problémy a algoritmy

Obsah cvičení

• Pojmy z přednášky: problém, instrukce, algoritmus
• Pseudokód
• Příklady problémů a algoritmů pro jejich řešení.

Opakování z přednášky

• problém?
• instrukce?
• algoritmus?

Zápis algoritmu pseudokódem

Pár základních konstrukcí, které budeme potřebovat. Další na přednášce, případně v Cormen et al.: Introduction to algorithms.

Přiřazení

“Do proměnné a ulož hodnotu b.”
a ← b

x ← 2 * y − 3/5

Podmíněný příkaz

“Pokud platí podmínka, tak udělej …, jinak udělej …”

1. if a = b then c ← 1
2.                      print(c je jedna)
3.              else c ← 2
4.                      print(c je dva)

Odsazení řádků je důležité.

Cykly

Cyklus for

Cyklus s řídící proměnnou.
“Pro i od … do … udělej …”

1. for i ← 0 to 10 do
2.    k ← i * i
3.    print(k*k)

Cyklus while-do

Cyklus opakující se dokud platí podmínka.
“Dokud platí podmínka opakuj …”

1. i ← 0
2. while (i <= 10)
3.    k ← i * i
4.    print(k*k)
5.    i++

Cyklus repeat-until

Cyklus opakující se dokud neplatí podmínka, který ale vždy proběhne alespoň jednou.
“Opakuj … dokud neplatí podmínka”

1. i ← 0
2. repeat
3.    k ← i * i
4.    print(k*k)
5.     i++
6. until (i = 11)

Existuje i cyklus do-while, který opakuje činnost, dokud podmínka platí.

• Zápis konstrukcí v jazyce C. Pokud jste to v C ještě neporbírali, nevadí, projdete si to příště.
• Zápis konstrukcí v jazyce Python. Pokud jste to v Pythonu ještě neporbírali, nevadí, projdete si to příště.

Příklady na cvičení

(tabule): Následující problémy popište pomocí možných vstupů a odpovídajících výstupů. Navrhněte a nejprve slovně a poté pseudokódem popište algoritmus pro jejich řešení.

1. Pro zadané číslo n vypište druhé mocniny všech čísel od 1 do n.
2. Pro zadané číslo n vypište “násobilku” až do hodnoty n ⋅ n.
3. Pro zadané slovo spočítejte, kolikrát obsahuje jednotlivá písmena abecedy (nerozlišujte velikost).

Úkoly k procvičení

• Následující problémy popište pomocí možných vstupů a odpovídajících výstupů. Navrhněte a nejprve slovně a poté pseudokódem popište algoritmus pro jejich řešení.
• Pokud už máte potřebné znalsoti z kurzu základů programování, zkuste algoritmy implementovat v jazyce C/Python. Pokud ne, tak si to zkuste, až v C/Pythonu základy proberete.

1. Je zadané číslo sudé nebo liché?
2. Řešení lineární rovnice a ⋅ x + b = 0.
3. Násobení dvou přirozených čísel. Zkuste navrhnout algoritmus používající z aritmetických operací pouze sčítání a odčítání.