Úlohy na procvičení
Kuličky
V nádobě jsou černé a bílé kuličky. Je tam Č černých a B bílých. Kuličky budeme z nádoby postupně odebírat. Vždy vytáhneme dvě kuličky a místo nich jednu jinou vrátíme do nádoby podle následujících pravidel:
- ⚪⚪ ⮕ ⚪ (když vytáhneme dvě bílé, vrátíme bílou)
- ⚪⚫ ⮕ ⚫ (když vytáhneme bílou a černou, vrátíme černou)
- ⚫⚫ ⮕ ⚪ (když vytáhneme dvě černé, vrátíme bílou)
Jakou barvu bude mít poslední kulička co v nádobě zbyde (v závislosti na Č a B)?
Známky
Mějme poštovní známky o hodnotách čtyři a pět korun. Dopis stojí v závislosti na jeho váze 12 a více korun (zaokrouhleno na celá čísla). Můžeme pomocí těchto poštovních známek zaplatit dopis o libovolné váze?
Nejtěžší mince
Mějme \(N\) různě těžkých mincí. K dispozici máme rovnoramenné váhy, na kterých můžeme porovnat dvě mince a zjistit, která z nich je těžší.
-
Navrhněte algoritmus, který na co nejméně vážení najde nejtěžší minci. Kolik vážení na to potřebujeme? Zdůvodněte, že na méně vážení to nejde.
-
Navrhněte algoritmus, který na co nejméně vážení najde nejtěžší i nejlehčí minci. Kolik vážení na to potřebujeme?
-
🦉 Bonus: Navrhněte algoritmus, který na co nejméně vážení najde druhou nejtěžší minci. Kolik vážení na to potřebujeme?