patecni - N dratu

[balu@home]

uz ked je ten problem tak krasne matematicky mozeme este dodat
"...a na zmeranie 4 294 967 296 dratoveho kablu nam bude stacit len 32 
ciest hore a 32 dole" :-)


On Aug/17/2012 20:27, Šerých Jakub wrote:
> Ja si myslim, ze nejuspornejsi na behani bude takove zmrsene binarni
> deleni. Nahore rozdelim draty na dve nestejne (abych je od sebe
> rozeznal) poloviny. To znamena napriklad 101 dratu na 50 a 51, nebo 102
> dratu na 50 a 52 a vsechny draty v obou polovinach vzajemne prozkratuji.
> Jdu dolu, identifikuji obe poloviny a oznacim si je nejvyssim bitem jako
> 0 a 1.
>
> Jdu nahoru, oznacim stejnym MSB horni konec a kazdou polovinu rozdelim
> podobne znova. Po dalsi ceste nahoru uz budu mit kazdy svazek oznacen 2
> bity a takhle pokracuju az k LSB (tam se bude muset nejak polaborovat s
> identifikaci samostatnych dratu, ale to uz by se nejak dovymyslelo).
>
> Jakub Serych
>
> *From:*hw-list-bounces na list.hw.cz [mailto:hw-list-bounces na list.hw.cz]
> *On Behalf Of *Jaroslav Meduna
> *Sent:* Friday, August 17, 2012 4:17 PM
> *To:* hw-list na list.hw.cz
> *Subject:* OT: patecni - N dratu
>
> 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
>
>
>
> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz
> Hw-list na list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list
>