patecni - N dratu

[Šerých Jakub]

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
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://list.hw.cz/pipermail/hw-list/attachments/20120817/76d1dbcf/attachment.htm>