OT: patecni - N dratu

[Šerých Jakub]

> > On Fri, 17 Aug 2012, Jaroslav Meduna wrote:
> >
> >> -          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
> >
> > Co vzit nahore pulku dratu a vzajemne je zkratovat (oznacit 1), druhou
> > pulku nechat volne (oznacit 0). Dole pak promerit ktere draty nalezi
> > ke zkratovane skupine (oznacit 1) a ktere k volne skupine (oznacit 0) .
> >
> > Nasledne dole zkratovat dohromady pul dratu ze skupiny 1 a pul dratu
> > ze skupiny 0 (a oznacit vysledne skupiny 00 01 10 11). Nahore pak
> > rozpojit zkrat a merit a oznacit vysledne skupiny 00 01 10 11.
> >
> > Pak opakovat prvni krok v ramci techle ctvrtskupin - pulku v nich vzdy
> > zkratovat pulku uvolnit a dooznacit 000 az 111 a nasledne dolu
> > rozpojit zkraty a merit a dooznacovat.. A tak porad dal.
> >
> Zdravim,
>   mam obavu, ze to odporuje zadani - nahore nelze merit. Pri doslovnem
> chapani zadani nelze ani dole zkratovat :-).
>   Zdravi Pavel
> 
No tak se to bude nahore zkratovat/rozpojovat a dole merit. To pocet cest sice zvysi, ale myslim, ze uspornejsi reseni neni. Pri 256 dratech by to melo vychazet na 8 cest s navratem, coz je myslim rozumne cislo.  Jen mi porad schazi algoritmus na ten LSB.

Jakub Serych