Algoritmy kolem nás
E 3011
Jan Bóhm
RECETOX
February 21, 2024
Jan Bôhm (RECETOX)
Cvičení I
□        S> - =
February 21, 2024
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 21, 2024
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 21, 2024
vT)
5/11
Pseudokód
Algorithm 1: Collatzova domněnka
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)
Cvičení I
□ - =
February 21, 2024
6/11
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)
Cvičení I
6/11
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 > G 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 21, 2024
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 21, 2024
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)
Cvičení I
9/11
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 21, 2024
9/11
Co nás dnes čeká
o*
Jan Bohrn (RECETOX)
*
Jan Bôhm (RECETOX)
Cvičení I
□        ůP - -
February 21, 2024
11/11