OT: patecni - N dratu

[Ladislav Vaiz]

Ahoj,
napred me napadlo take binarni deleni, ale pak me pod vlivem dalsich 
prispevku napadlo neco jineho. Nahore se spoji postupne jeden (ten se 
necha byt), dva, tri ctyri... az vsechny dojdou. Dole se vezme jeden a k 
nemu se prozvoni vsechny ostatni. Ty, ktere pipaji, se spoji do skupiny 
a dale se hleda jen mezi zbytkem. Tim dole identifikujeme samostatny 
drat, dvojici, trojici atd.
V kazde skupine pak pokracujeme rekurzivne, ale uz muzeme projit vsechny 
skupiny zaroven na jednu cestu nahoru a dolu.
Nakonec zbydou dvojice, ktere prozvonime proti prvnimu samostatnemu dratu.

Priklad pro N=21:

1. krok: (1) (23) (456) (789A) (BCDEF) (GHIJKL)
2. krok: (1) (23) (4) (56) (7) (89A) (BC) (DEF) (G) (HI) (JKL)
3. krok: (1) (23) (4) (56) (7) (8) (9A) (BC) (D) (EF) (G) (HI) (J) (KL)
4. krok  (1259BEHK) (3) (6) (A) (C) (F) (I) (L)

Je to tedy na 4 kroky a to bude lepsi nez puleni intervalu.

Pro jina N nez je soucet rady prirozenych cisel by se musely brat vetsi 
skupiny, aby zbytek nekolidoval s uz existujici skupinou stejne velikosti:

(1) (23) (45)   -> nelze, jednoznacne je (12) (345), kde ale naroste 
slozitost o jeden krok. Tech 21 jsem zvolil, protoze vychazi pekne.

Snad jsem neudelal nejakou botu. Doufam, ze se mi ted povede vypnout 
hlavu a usnout :-)

Lada


On 17.8.2012 16:16, Jaroslav Meduna wrote:
>
> 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
>    
------------- dal?í ?ást ---------------
HTML p?íloha byla odstran?na...
URL: <http://list.hw.cz/pipermail/hw-list/attachments/20120817/e9d17d5b/attachment.htm>