... Lottozahlen ziehen

uall@ogc · Verfasst: Di 10.04.07 17:09

Narses 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:

markieren

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 Christian S.: Abgeteilt von [url=www.delphi-library.d...p?t=71713]hier[/url]

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit

Narses · Verfasst: Mo 24.09.07 01:38

Moin!

uall@ogc hat folgendes geschrieben:

Wenn man dieses Verfahren ein bisschen anders implementieren würde, hätte es ein Laufzeitverhalten von O(1)

Wie

alzeimar 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).

uall@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

_________________
There are 10 types of people - those who understand binary and those who don´t.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme