Ordung muss sein

[negaH]

Zitat:

also wenn ich jetzt nicht irgendwas wesentliches übersehen habe ist Deine Lösung aber auch nicht ganz richtig.
Wenn ich das mal genau nehme, ist Deine Ziehung sogar manipuliert.

Bei Dir steht zwar je Ziehung immer eine Zahl weniger zur Verfügung, aber nicht die, die gezogen wurde, ausser in der ersten Ziehung war es zufällig eine 49, in der zweiten die 48 usw.

Schau dir den Source noch mal ganz genau an Und nein, der Algorithmus ist absolut richtig.

Wichtig ist es zu begreifen das N nicht die tatsächlich gezogene Zahl ist, sondern ein Index in das Set der verbleibenden Zahlen in der Urne. Man könnte es auch anders umschreiben indem man eine Liste aller Zahlen von 1 bis 49 erzeugt. Nun wird mit Random( 49 ) der Index in diese Liste erzeugt und die Zahl an Index N in dieser Liste entfernt. Im nächsten Schritt wird mit Random( 48 ) ein neuer Index N erzeugt, da ja nun die Liste nur noch 48 Zahlen enthält. Wieder entfernt man die Zahl an Index N aus der Liste. Dies macht man insgesammt 6 mal.

Nicht anders arbeitet obiger Algortihmus, nur das er eben nicht die große Liste aller 49 Zahlen benötigt. Sondern die List in Sorted[] ist die Menge der gezogenen Zahlen. N als solches ist also ein Index und er muß an Hand der schon gezogenen Zahlen in Sorted[] abgeglichen werden. Effektiv entsteht aus dem Index dann die gezogene Zahl.

Du kannst es mir glauben, meine Informatiklehrer wollten es auch nicht glauben, bekam dann trotzdem meine 1

Mein Beweis war relativ einfach. Ich habe einfach den Algo. um diese Liste mit 49 Zahlen erweitert. Dann habe ich parallel zum Algo. das Element an Index N aus der Liste gestrichen. Das Resultat ist exakt identisch.

Der Vorteil des Algos. ist sein Speicherverbrauch und das er die Zahlen auch schon sortiert erzeugt.
Besonders wenn man z.b. 5 aus 5 Millionen berechnen will ist er wesentlich effizienter als der mit der Liste. Beide Verfahren sind korrekt.

Vielleicht hilft die folgender Gedanke weiter:
Was sind aufeinanderfolgende Zahlen ? sprich 1,2,3,4,5,6,7,8...49 ?
Der Index von 1 ist 1, der Index von 2 ist 2, der Index von 3 ist 3. Wenn wir nun die 5 schon entfernt haben, wie groß ist der Index von 7 ? Wenn wir unter der Annahme das 5 entfernt wurde und den Index = 6 haben wie kommen wir dann auf die Zahl 7 ?

Gruß Hagen

Delphi-Quellcode:

procedure Lotto(var Sortiert,Gezogene: TZahlen; Ziehungen: Integer = 6; Elemente: Integer = 49);
var
  I,J,K,N,M: Integer;
  List: TZahlen;
begin
  Sortiert := nil;  // stellt sicher das Sortiert <> Gezogene ist
  Gezogene := nil;

  if Ziehungen > Elemente then
    raise Exception.Create('Man kann nicht mehr Kugeln ziehen als in der Urne sind');

// Liste mit allen Zahlen erzeugen
  SetLength(List, Elemente);
  for I := 0 to Elemente -1 do List[I] := I +1;

  SetLength(Sortiert, Ziehungen);
  SetLength(Gezogene, Ziehungen);

  for I := 0 to Ziehungen -1 do
  begin
    K := 0;
    N := Random(Elemente - I);

 // aus Liste die gezogene Zahl holen und Zahl entfernen
    M := List[N];
    for J := N to Elemente -2 do
      List[J] := List[J +1];

    Inc(N);  // in 1 basierten Index umwandeln
    for J := 0 to I -1 do
      if N >= Sortiert[J] then
      begin
        Inc(N);
        Inc(K);
      end else Break;
    for J := I downto K +1 do
      Sortiert[J] := Sortiert[J -1];
    Sortiert[K] := N;
    Gezogene[I] := N;

// hier ist immer N = M
    WriteLn( N:5, M:5);
  end;
end;