Organizácia

Všetky informácie o cvičeniach nájdete na stránke O cvičeniach.

Úlohy

Mince

Dostali ste deväť na prvý pohľad rovnakých mincí, jedna z nich je však falošná - je ľahšia než všetky ostatné (ostatné vážia rovnako). Máte k dispozícii rovnoramenné váhy. Čo najmenším počtom vážení zistite, ktorá je falošná.

Rieka

Na jednom brehu stojí bača, vlk, koza, kapusta (zelí) a lodička. Vlk by rád zožral kozu, koza by rada zožrala kapustu, ale kým je s nimi na jednom brehu bača, tak si to nedovolia. Do lodičky môže bača vziať len jedno zviera alebo kapustu. Dve zvieratá alebo zviera a kapusta sa na lodičku naraz nezmestia. Koza ani vlk nevie pádlovať. Ako dostane bača vlka, kozu aj kapustu na druhú stranu tak, aby na jednom brehu nikdy nebola koza s vlkom alebo s kapustou?

Rodina

Štvorčlenná rodina potrebuje prejsť tunelom, pričom:

• tunelom sa nedá ísť potme
• otec prejde tunel za 1 minútu
• mama prejde tunel za 2 minúty
• syn prejde tunel za 4 minúty
• dcéra prejde tunel za 5 minút
• majú baterku, ktorá poskytuje svetlo pre dve osoby a vydrží svietiť 12 minút

Ako sa dostane rodina cez tunel?

Lámanie čokolády

Majme čokoládu, ktorá sa skladá z m x n štvorčekov. Chceme ju nalámať na jednotlivé štvorčeky, ale môžeme vždy lámať len jeden kus čokolády naraz, tzn. nesmieme kusy čokolády prekladať.

• Aký je najmenší počet lámaní, aby sme čokoládu rozdelili na jednotlivé štvorčeky?
• Závisí počet lámaní na konkrétnej stratégii akou budeme lámať?
• Aký je počet lámaní, ak dovolíme jednotlivé kusy čokolády pri lámaní prekladať?

Ťava (velbloud)

V púšti máme hromadu 3000 banánov a ťavu s nosnosťou 1000 banánov. Ťava má navyše spotrebu 1 banán na kilometer a v púšti si môžeme vytvárať ďaľšie dočasné hromady. Ťava taktiež zje svoj banán vždy na začiatku každého načatého kilometru svojej cesty.

Koľko banánov dokážeme pomocou tejto ťavy preniesť do 1000 kilometrov vzdialenej oázy?

Prelievanie vody

Máte dva džbány, prvý s objemom 5 litrov (v1), druhý s objemom 3 litre (v2) a neobmedzený zdroj vody. Máte dovolené nasledujúce operácie: naplniť jeden z džbánov do plna, vyliať všetku vodu z jedného džbánu a preliať vodu z jedného džbánu do druhého (dolejete ho vždy do plna).

• Dokažete odmerať 4 litre (v3)?
• Navrhnite algoritmus, ktorý úlohu vyrieši pre ľubovolné hodnoty v1, v2 a v3.
• Nájde váš algoritmus vždy postup s najmenším počtom operácii?

Domáca úloha: Zoradenie čísel

Vymyslite algoritmus (všeobecný postup) pre zotriedenie n ľubovolných navzájom rôznych celých čísel. Akýkoľvek algoritmus s ktorým prídete je OK, nemusíte ho loviť na internete. Váš algoritmus spíšte podobne, ako ste popisovali algoritmy na prednáške (minimálne tak aby som ho pochopil). Riešenie mi pošlite e-mailom alebo odovzdajte na začiatku ďaľšieho cvičenia.

Termín: do ďaľšieho cvičenia 12. 10. 2016

Do ďalšej hodiny

• Ak sa rozhodnete navštevovať moje cvičenia skontrolujte si či ste ku mne zapísaný v SIS-e, inak vám nebudem môcť udeliť zápočet.