OT: patecni - N dratu

[Aleš Martinek]

Ahoj
Tímto způsobem se dá snížit počet kroků na ještě méně. Pro uvedený 
příklad N=21 vychází 3. kroky.
A to :

1. krok : (1) (23) (456) (789A) (BCDEF) (GHIJKL)  : určen drát 1 a 
ostatní kombinace
2. krok : (12) (34) (5) (67) (89) (AB) (C) (DE) (FG) (HI) (JKL) : Určen 
drát 2,3,4,5,6,7,A,B,C, F,G
3. krok : (18) (9) (2D) (E) (3H) (I) (4J) (5K) (L) (6) (7) (A) (B) (C) 
(F) (G)

Doufám že jsem neudělal chybu :

Aleš Martinek

Ladislav Vaiz napsal(a):
> 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 bywww.HW.cz
>> Hw-list na list.hw.cz
>> http://list.hw.cz/mailman/listinfo/hw-list
>>    
>
>
> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz
> Hw-list na list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list