Algoritmy kolem nás
E 3011
Jan Bóhm
RECETOX
February 19, 2025
Jan Bôhm (RECETOX)
Cvičení I
□        S> - =
February 19, 2025
1/11
Co nás dnes čeká
O*
o*
Jan Bóhm (RECETOX)
CU: Zadání
Utvořte dvojice.
4
Jan Bôhm (RECETOX)
Zadání
Utvořte dvojice.
Vaším úkolem je zreplikovat tajný obrázek. Jeden z dvojice se na obrázek může dívat a dává instrukce druhému členu dvojice, který jej kreslí.
Jan Bôhm (RECETOX)
Cvičení I
□        S> - =
February 19, 2025
3/11
CU: Zadání
Utvořte dvojice.
Vaším úkolem je zreplikovat tajný obrázek. Jeden z dvojice se na obrázek může dívat a dává instrukce druhému členu dvojice, který jej kreslí.
Pravidla:
• Kreslící se nesmí podívat na vzor. o Kreslící se nemůže doptávat.
Navigující se nesmí dívat na průběžně kreslený obrázek.
Jan Bôhm (RECETOX)
Co nás dnes čeká
0*
o*
Jan Bóhm (RECETOX)
ENGINEERING
FLOW CHART
USE MORE DUCT TAPE
NO PROBLEM
Jan Böhm (RECETOX)
Cvičení I
February 19, 2025
vT)
5/11
Pseudokod
Algorithm 1: Collatzova domnenka
Input: n e N while n > 1 do
if n is even then
|   n <- n -T- 2 ; else
|   n <- 3 • n + 1; end print n
end
Jan Bohm (RECETOX)
Pseudokód
Algorithm 2: Collatzova domněnka
Input: n e N while n > 1 do if n is even then
I   n <- n -i- 2 ; else
I   n <- 3 • n + 1; end print a?
end
Co je program vypíše pro n = 3, n = 21, n = 1, n = 0?
Jan Bóhm (RECETOX)
y =y*x n = n -1
y = 1 n > 0 integer x real number
No
}
Yes
-O
Yes
Initalizalion
return y
n = n/2
Jan Bohm (RECETOX)
y = 1 n > O integer x reál nu m ber
Initaliľalion
Co program vrátí pro n = 5 a x = 3? Pro n = 0 a x = —2? A pro n = 7 a x = 0.5?
Jan Bôhm (RECETOX)
Cvičení I
□        S> - =
February 19, 2025
7/11
y = 1 n > O integer x reál nu m ber
Initaliľalion
Co program vrátí pro n = 5 a x = 3? Pro n = 0 a x = —2? A pro n = 7 a x = 0.5? Co program dělá?
Jan Bôhm (RECETOX)
Cvičení I
□        S> - =
February 19, 2025
7/11
Co nás dnes čeká
O i
o*
Jan Bóhm (RECETOX)
1
%: Zadání
Máme k dispozici 2 stejná vejce a budovu o 100 patrech.
Pokud pustíme vejce z některého patra budovy a ono se rozbije, tak máme
jistotu, že se vejce rozbije i ze všech vyšších pater. Pokud se naopak
nerozbije, tak se nerozbije ani po vyhození z kteréhokoliv nižšího patra.
Naším úkolem je zjistit které je nejvyšší patro, ze kterého se vejce ještě
nerozbije.
Vymyslete postup, jak toto patro najít co nejrychleji (s co nejmenším počtem pokusů).
Jan Bôhm (RECETOX)
1
Zadání
Máme k dispozici 2 stejná vejce a budovu o 100 patrech.
Pokud pustíme vejce z některého patra budovy a ono se rozbije, tak máme
jistotu, že se vejce rozbije i ze všech vyšších pater. Pokud se naopak
nerozbije, tak se nerozbije ani po vyhození z kteréhokoliv nižšího patra.
Naším úkolem je zjistit které je nejvyšší patro, ze kterého se vejce ještě
nerozbije.
Vymyslete postup, jak toto patro najít co nejrychleji (s co nejmenším počtem pokusů).
Jak rychle toto patro najdete, pokud:
• vejce vydrží maximálně 76 pater a při 77. se rozbije?
• vejce zvládne 19 pater a v 20. se rozbije? o vejce se nerozbije nikdy?
• vejce se rozbije už v 1. patře?
Cvičení I
Jan Bôhm (RECETOX)
□        S> - =
February 19, 2025
9/11
Co nás dnes čeká
o*
Jan Bóhm (RECETOX)
*
Jan Bôhm (RECETOX)
Cvičení I
□        ůP - -
February 19, 2025
11/11