OT: patecni - N dratu

[Ales Prochaska]

Je slozitost ukolu log2(N)?

Ales Prochaska

> Sice tu uz bylo pekne patecni (ctvrtecni) vlakno, ale neodpustim si
> vzpominku na skolu, kde jsem vystudoval a zverejnim tu jednu tamni peknou
> elektrikarskou ulohu:

>  

> -          predstavte si, ze jste elektrikar ve vyskove budove (desitky
> pater)

> -          nejde proud, asi i proto, ze se rozbil hlavni kabelovy svazek,
> citajici N vodicu (budeme jim dale rikat draty)

> -          kabelovy svazek N dratu vede z prizemi az do posledniho patra

> -          v poslednim patre muzete delat libovolne zkraty (napriklad spojit
> dva vodice, nebo treba vsechny)

> -          v prizemi muzete merit, ktere vodice jsou spojeny

> -          vytah nejezdi, proto je cilem minimalizovat pocet cest nahoru a
> dolu

>  

> Ukolem je najit nejlepsi algoritmus k identifikaci dratu tak, aby je slo
> oznacit od 1 do N v prizemi i v poslednim patre.

>  

> JM