Entwickler-Ecke

Sonstiges - ... Lottozahlen ziehen


uall@ogc - Di 10.04.07 17:09
Titel: ... Lottozahlen ziehen
user profile iconNarses hat folgendes geschrieben:
Definition

Beispiel im Detail: Lotto, 6 aus 49. Der am häufigsten verwendete Ansatz sieht vor, eine zufällige Zahl aus dem Bereich 1..49 zu bestimmen und die Auswahl zu verwerfen, wenn die Zahl bereits gezogen wurde und eine andere Zufallszahl zu bestimmen.


Wenn man dieses Verfahren ein bisschen anders implementieren würde, hätte es ein Laufzeitverhalten von O(1), wenn man nur die Auswahl betrachtet, das aufstellen der Zahlen ist ja bei beiden Verfahren O(n). Die Wahrscheinlichkeit bei den Zahlen die übrig geblieben sind wäre aber gleich. Der Speicherverbrauch wäre aber um den Bereich größer den man braucht um alle Zahlen darstellen zu können. Ebenso wäre es determinierend. Und GENAU SO funktioniert es ja in Lotto in Wirklichkeit auch. Die shcon gezogenen Zahlen interessieren ja nicht mehr! Also für einen Lottogenertator würde ich dann doch lieber folgendes nehmen:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
 
var
  ZahlPott: array of Byte;
  ZahlGezogen: array of Byte;
begin
  SetLength(ZahlPott,49);
  SetLength(ZahlGezogen,6);
  for i := low(ZahlPott) to High(ZahlPott) do
    ZahlPott[i] := i;

  for i := low(ZahlGezogen) to High(ZahlGezogen) do  // für alle Zahlen mache
  begin
    a := random(high(ZahlPott+1)-i));       // Wähle eine Zahl aus
    ZahlGezogen[i] := ZahlPott[a]+1;        // Setze die gezogene Zahl
    ZahlPott[a] := ZahlPott[high(ZahlPott-i)];  // tausche die letzte Zahl vom möglichen nächsten Zug aus
  end;
end;


Denke Fisher-Yates wird in anderen Fällen eher genommen. Beim Lotto hat man ja eben nicht immer die selbe Wahrscheinlichkeit.

Moderiert von user profile iconChristian S.: Abgeteilt von [url=http://www.delphi-library.de/viewtopic.php?t=71713]hier[/url]


Narses - Mo 24.09.07 01:38
Moin!

user profile iconuall@ogc hat folgendes geschrieben:
Wenn man dieses Verfahren ein bisschen anders implementieren würde, hätte es ein Laufzeitverhalten von O(1)

Wie user profile iconalzeimar bereits (in dem leider nach dem Aufteilen nicht mehr vorhandenen Beitrag) ausgeführt hat, ist das Laufzeitverhalten auch für deinen Ansatz im Wesentlichen O(n). ;)

user profile iconuall@ogc hat folgendes geschrieben:
Die Wahrscheinlichkeit bei den Zahlen die übrig geblieben sind wäre aber gleich.
[...]
Beim Lotto hat man ja eben nicht immer die selbe Wahrscheinlichkeit.

Ich sehe in deinem und meinem Ansatz keinen Unterschied in der Verteilung der Wahrscheinlichkeiten; schließlich ist die Lotto-Zahlenmenge eine perfekte Permutation 6 aus 49. :mahn: ;) Entscheidend ist eben, auf das Ergebnis zu schauen, und nicht auf einen einzelnen Zugvorgang! :idea:

cu
Narses


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!