Witam
Musze wylosować element ze zbioru elementów. Każdy element ma przypisane prawdopodobieństwo. Suma wszystkich prawdopodobieństw wynosi 1. Czy może ktoś ma pomysł jak się zabrać do tego problemu ?
0
0
Johny - widziałem ten temat. Ale mi nie chodzi o sam algorytm losowania tych elementów, nie szukam algorytmu o złożoności O(log n) i w moim przypadku prawdopodobieństwa przypisane lementem nie zmieniają się.
0
Ale masz podana nazwe algorytmu ze zlozonoscia liniowa, wiec moze skorzystasz z tego?
0
Algorytm konstruowania dystrybuanty ? Google tylko tamten temat znajduje. Koncepcje jak to zrobić mam ale wolałbym jeszcze porównać mój pomysł z innymi.
0
Poniżej jest fragment programu rysującego fraktala. W zależności od rozkładu zmiennej losowej są określone iteracje. Całość w pascalu, ale może pomoże Ci to ruszyć dalej lub zaświeci lampkę. Powodzenia. Adam.
FOR i := -50 TO 50000 DO
BEGIN
w := Random(100);
CASE w OF
00..73 : BEGIN { p = 0.74 }
x := +0.849*x+0.037*y+0.075;
y := -0.037*x+0.849*y+0.183;
END;
74..86 : BEGIN { p = 0.13 }
x := 0.197*x-0.226*y+0.400;
y := 0.226*x+0.197*y+0.049;
END;
87..97 : BEGIN { p = 0.11 }
x := -0.150*x+0.283*y+0.575;
y := +0.260*x+0.237*y-0.084;
END;
98..99 : BEGIN { p = 0.02 }
x := 0.500;
y := 0.160*y;
END;
END; { CASE }
IF i>0 THEN PutPixel(Round(x*620),Round(480-y*460), LightGreen);
END;
0
Napisałem coś takiego (Java):
public void addProduction(ConstProduction prod) throws ProbabilityException, PredeccessorException {
int r = canAdd(prod);
if(r == -1) {
throw new PredeccessorException();
}
if(r == -2) {
throw new ProbabilityException();
}
float last = distribution.get(distribution.size()-1);
distribution.add(last + prod.getProbability());
try {
prods.add(new Production(prod));
} catch(ProbabilityOutOrangeException e) {
throw new RuntimeException("Should never happen", e);
}
}
public ConstProduction randomProduction(long seed) {
if(prods.size() == 0) {
throw new IllegalStateException("Container is empty");
}
float f = new Random().nextFloat();
int index = binSearch(f);
ConstProduction r;
if(index == -1) {
r = id;
} else {
r = prods.get(index);
}
return r;
}
private int binSearch(float f) {
int low = 0, high = distribution.size()-1;
int mid, r1, r2, index = -1;
while(low <= high) {
mid = (int)Math.ceil((low + high) / 2.0f);
r1 = Utils.cmpFloat(f, distribution.get(mid));
r2 = Utils.cmpFloat(f, distribution.get(mid-1));
if(r1 == Consts.GT) {
low = mid+1;
} else if(r2 == Consts.LT) {
high = mid-1;
} else {
index = mid-1;
break;
}
}
return index;
}
Może się komuś przyda, może ktoś zauważy błąd.
Pozdro.
0
Istnieje rozwiązanie tego problemu w czasie O(1). Zostało ono wymyślone pod koniec lat osiemdziesiątych.
Miałem to w zeszłym roku, ale niestety nie pamiętam nazwy algorytmu. Jeżeli komuś bardzo zależy, to mogę poszukać w notatkach.
Algorytm był dosyć trudny koncepcyjnie(trudno było uwierzyć, że działał poprawnie). Osobie prowadzącej zajęcia zajęło z godzinę udowodnienie jego poprawności. Z drugie strony kodu nie było zbyt dużo.
0
A mógłbyś dla mnie poszukać w notatkach? [browar]
Bo nigdzie nie mogę znaleźc takiego ajnego algorytmu w O(1).
0
szukam caly czas generatora von Neumanna dla roznych funkcji prawdopodobienstawa (gestosci).
Moze ktos poradzic ??