Stachu 'Dozzie' K.
4/7/2007 11:48:00 AM
On 07.04.2007, sebastian.wajrych@gmail.com <sebastian.wajrych@gmail.com> wrote:
> Rozwi?zanie, które zosta3o mi zaproponowane (przedstawie z przyk3adem
> dla 3atwiejszego zobrazowania):
> Dane wej?ciowe:
> Zbiór nazwisk w woj. 3ódzkim z atrybutem okre?laj?cym liczbe wyst?pien
> np.
> 1. Nowak 6880
> 2. Kowalczyk 5742
> 3. Wo?niak 4284
> ...
> 100. Kapusta 3
>
> Dane wyj?ciowe:
> Zbiór nazwisk spe3niaj?cy podane wagi
>
> Algorytm:
>
> 1. okre?l minimalna wage (min=3)
>
> 2. okre?l maksymalna wage (max=6880)
>
> 3. wylosuj liczbe (pseudolosow?) z rozk3adem jednostajnym z przedzia3u
> okre?lonego na podstawie pkt. 1 i 2. (los=6000)
>
> 4. wybierz nazwisko, którego waga jest najwieksza i nie wieksza lub
> równa ni? wylosowana waga (w tym wypadku pada na Kowalczyk, bo ma
> 5742)
>
> 5. je?eli wystepuj? dwie takie same wagi np. Kowalczyk 5742 i
> Kapu?cinski 5742 to wylosuj z tak ograniczonego zbioru z rozk3adem
> jednostajnym (bo jeden jak i drugi powinien miea takie same szanse
> wyst?pienia)
>
> Algorytm ma pewna wade wynikaj?c? z nieci?g3o?ci przedzia3ów wag.
> Poniewa? dla warto?ci wylosowanej wagi miedzy Nowak minus jeden czyli
> 6879 do 5742 zawsze zostanie wybrany Kowalczyk, a tylko gdy wylosujemy
> 6880 zostanie wybrany Nowak. Czyli widzimy ?e skoro losujemy z
> przedzia3u 3-6880 z rozk3adem jednostajnym to powiedzmy tylko 1%
> przedzia3u pokrywa Nowak mimo ?e wyst?pien Nowaka jest a? o ponad
> tysi?c wiecej a Kowalczyk pokryje za3ó?my 10% przedzia3u co zaburza
> dzia3anie ca3ego algorytmu gdy? Kowalczyków w wynikach bedzie wiecej
> ni? Nowaków.
>
> Prosze Was o ustosunkowanie sie do tego rozwi?zanie i powiem szczerze,
> ?e liczbe na lepsze rozwi?zanie.
Nie chce mi sie analizowaa tego algorytmu. IMO jest zbyt skomplikowany.
U?yj czego? takiego:
- ka?demu nazwisku przydziel jak?? wage (minimum 1)
- s = suma warto?ci wag
- nazwisku i przypisz przedzia3 [k_{i - 1}, k_{i - 1} + waga_i), gdzie
k_i = k_{i - 1} + waga_{i}
- wylosuj z rozk3adem jednostajnym liczbe z zakresu [1, s]
- sprawd?, do którego przedzia3u nale?y wylosowana liczba.
--
Secunia non olet.
Stanislaw Klekot