Autor Beitrag
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5285
Erhaltene Danke: 29

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Mo 19.03.07 19:34 
hi, mir ist gerade der gedanke gekommen, wie man es wohl am besten anstellt, wenn man ein array hat, sagen wir mal mit 10 elementen und jetzt jedes dieser elemente eine unterschiedlich hohe wahrscheinlichkeit hat, und jetzt ein element unter einbezug dieser wahrscheinlichkeit ziehen möchte, beispiel:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
type
  TIrgendwas = record
    value: integer;
    wahrscheinlichkeit: single;
  end;

var
  Iarray: array [1..10] of TIrgendwas;


wie stellt man das am besten an ? random is klar, nur wie ? die wahrscheinlichkeiten wären dann im bereich 0-1 wobei man natürlich sicherstellen müsste, dass die summe der wahrscheinlichkeiten genau 1 ist, da das ganze sonst nicht funktioniert.


mfg
Kroko
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1284

W98 W2k WXP
Turbo D
BeitragVerfasst: Mo 19.03.07 19:56 
2. Idee (ungetestet)
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
var
  I,H1,H2: Integer;
  S,A: Double;
begin
  for I := 0 to 9 do Feld[I] := 0.1;
  for I := 0 to 99 do
  begin
    H1 := Random(10);
    repeat
      H2 := Random(10);
    until H2<>H1;
    case Random(3) do
      0: A := 0.1;
      1: A := 0.01;
      2: A  := 0.001;
    end;
    if (Feld[H1]>A) and (Feld[H2]+A<=1.0) then
      begin
        Feld[H1] := Feld[A1]-A;
        Feld[H2] := Feld[A2]-A; 
      end
    else
      begin
        if (Feld[H2]>A) and (Feld[H1]+A<1.0) then
          begin
            Feld[H2] := Feld[H2]-A;
            Feld[H1] := Feld[H1]+A; 
          end;
      end; 
end;


[EDIT] 1.Idee war M... :oops:

_________________
Die F1-Taste steht nicht unter Naturschutz und darf somit regelmäßig und oft benutzt werden! oder Wer lesen kann, ist klar im Vorteil!
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 19.03.07 20:34 
Sei V eine Liste von Werten und W die Liste der Warscheinlichtkeiten, sodaß der Wert V[i] mit der Wahrscheinlichtkeit W[i] gezogen werden soll.

Wir wählen eine zufällige Zahl Z zwischen 0 und (Summe aller W).
Ist Z < W[0], dann wird V[0] gezogen, wenn Z<W[0]+W[1], wird V[1] gezogen etc.

Beispiel: W = (1,2,3), Die Summe ist 6. Es ist klar, das in der Hälfte aller Fälle (wenn nämlich Z zwischen 3 und 6 ist), die 3.Zahl gezogen wird , in 40% der Fälle (wenn Z zwischen 1 und 2.9999 liegt) die 2.Zahl und sonst die 1.

So gehts:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
Function GewichteteWahrscheinlichkeit (W,V : Array Of Double) : Double;
Var
  i : Integer;
  Z, SummeW : Double;

Begin
  SummeW := 0;
  For i:=Low(W) to High (W) do 
    SummeW := SummeW+W[i];
  Z := Random*SummeW;
  For i:=Low(W) to High (W) do 
    If Z<W[i] Then Begin
      Result := V[i]
      Exit;
    End
    Else
      Z:=Z-W[i]
End;


Ungetestet, sollte aber stimmen.

_________________
Na denn, dann. Bis dann, denn.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mo 19.03.07 21:00 
Hallo,

Nach etwas experimentieren mit der Binären Suche:

Du bildest die Summenwarscheinlichkeit und unterteilst diese dann.
w(N) sind deine Wahrscheinlichkeiten (rel.Anteil vom Gesamten( wäre besser, dann muss die Sumee S(N) auch nicht 1 ergeben, man kann dann aber mit 1/s(n) normieren))
S(i) := s(i-1)+w(n);//s(0) = 0,i=(1..n)
Jetzt fehlt noch ein Feld 1..n für die Anzahl der tatsächlichen Ziehung und schon kannst Du mit Binäre Suche den Wert in der Liste finden.

So getestet ;-) mit TMT-Pascal, dauert immer ein wenig....
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
const
  N_Max = 10;
  Ziehungen = 100000;
var
  un,ob,mit,
  n : integer;
  Sn,x : double;
  Wahrscheinlich,
  FeldSumme : array[0..n_max] of double;
  Haeufigkeit: array[0..n_max] of integer;
begin
  randomize;

  For n := 0 to N_max do
    Haeufigkeit[n]:= 0;

  For n := 1 to N_max do
    Wahrscheinlich[n] := random;

  Sn := 0.0;
  FeldSumme[n] := 0.0;
  For n := 1 to N_max do
    begin
    Sn := Sn+Wahrscheinlich[n];
    FeldSumme[n] := Sn;
    writeln(n:10,Sn:10:7);
    end;

  //Sn ist jetzt die Summe aller Anteile
  //jetzt die Ziehungen
  For n := 1 to Ziehungen do
    begin
    x := Sn*random;//Ein Wert aus [0..Sn[
    //Suchen
    un := 0;
    ob := N_Max;
    repeat
      mit := (un+ob) div 2;
      If FeldSumme[mit+1]<X then
        un := mit+1
      else
        begin
        If FeldSumme[mit]>X then
          ob := mit
        else
          break;
        end;
    until False;
    //writeln(x/Sn,' ',mit);
    inc(Haeufigkeit[mit]);
    end;

  For n := 0 to n_Max+1 do
    writeln(n:5,Haeufigkeit[n]:10,Wahrscheinlich[n]/Sn*Ziehungen:15:5,FeldSumme[n]/Sn:10:7);
end.

Man muss nur aufpassen, ob die Haeufigkeit[n] auf den Bereich n-1 bis n bezieht, sonst ändert man eben inc(Haeufigkeit[mit]); in inc(Haeufigkeit[mit+1]);

Gruß Horst
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 19.03.07 21:46 
Horst_h, Du musst auch immer noch eins drauflegen :wink:

Super! Die lineare Suche hat mir auch nicht gepasst, aber den Baum vor lauter Wald hab ich auch nicht gesehen. :flehan:

_________________
Na denn, dann. Bis dann, denn.