Úlohy na procvičení
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?
Vážení kuliček
Máme 7 stejně vypadajících zlatých koulí, ale jedna z nich je vadná. Je totiž vyrobená z kočičího zlata a tedy je lehčí než ty ostatní. Naším úkolem je tuto vadnou kouli najít.
Máme k dispozici rovnoramenné váhy, kde na každou misku můžeme dát několik koulí najednou a váhy nám řeknou, která miska je lehčí. Pokud jsou obě misky stejně těžké, váhy zůstanou stát.
Jelikož nechceme váhy zbytečně opotřebit, tak hledáme způsob jak najít vadnou kouli na co nejmenší počet vážení. Zkuste také zdůvodnit, že na méně vážení lehčí kuličku najít nelze.