Ordung muss sein

[block35plus1]

jo das funzzt einwandfrei. Da wird mein Lehrer aber augen machen ))
aber vielen dank. aber ein frage noch. wie bekomm ich das jetzt hin. das die in Mem.Ausgabe geordnet sind?

[Christian Seehase]

Moin

such hier mal nach MinSort oder bubble and sort

Das hatten wir gerade erst.

Es wäre auf jeden Falle sinnvoll erst die Zahlenliste zu sortieren, und dann auszugeben, da Du sonst die von Mr. Spock angsprochenen Probleme bekommst, wenn die Zahlen keine führenden Nullen haben.

[MrSpock]

Hallo Block35plus1,

da musst du wohl einen kleinen Sortieralgorithmus implementieren. Du könntest zwar auch andere Komponenten nutzen, die eine Sortierfunktion mitbringen )TStringList oder so, aber der Lehrer wollte bestimmt, dass ihr euch Gedanken über verschiedene Wege macht, wie man eine Liste sortieren kann.
Such doch einfach mal im Internet nach Quicksort oder Heapsort oder allgemein nach Sortieralgorithmus.

[block35plus1]

ok dann werde ich mal mein glück probieren. ihr habt mir aber richtig geholfen vielen dank... und schönen abend und schönes wochenende noch

[MrSpock]

Danke, wirklich gerne geschehen.

Sortieralgorithmen haben mich und sicher viele andere durch das halbe Informatikstudium begleitet.
Ist aber durchaus ein wichtiges Thema. Gerade auch für schnelle Datenbankzugriffe und so. Die Arbeit, die du hier reinsteckst ist sicher nicht vergebens.

[Christian Seehase]

Moin block35plus1,

für die Auslosung ist mir gerade noch was eingefallen:

Delphi-Quellcode:

Procedure Zahlen_ermittelnOHNEDoppelte(var Lottozahlen:TLottozahlen);
var
  i      : integer;
  afList : array [1..49] of boolean;
  iCount : integer;
  iZahl  : integer;

begin
  randomize;
  for i := 1 to 6 do begin
    Lottozahlen[i] := 0;
  end;
  for i := 1 to 49 do begin
    afList[i] := false;
  end;
  iCount := 6;
  while iCount > 0 do begin
    iZahl := Random(49)+1;
    if not afList[iZahl] then begin
      Lottozahlen[iCount] := iZahl;
      afList[iZahl]       := true;
      dec(iCount);
    end;
  end;
end;

Da hast Du jetzt wenigstens schon mal ein wenig Material zum analysieren.
Dein Lehrer wird wohl sicherlich danach fragen, wie Du auf die Lösung gekommen bist, also Copy&Paste wird nicht ganz reichen

[negaH]

Ich weiß ja nicht ob der Lehrer für die bisherigen Lösungen gute Noten vergibt.

Es soll 6 aus 49 programmiert werden, richtig ? Nun wenn ich die Ziehung von 6 aus 49 mal genauer betrachte so sind am Anfang 49 Kugeln in der Urne. Dann wird eine Zahl gezogen und schupps da waren es nur noch 48. Das geht so weiter bis 6 Kugeln aus der Urne rausgenommen wurden und somit nur noch 43 in der Urne sind.

Die bisherigen Lösungsvorschläge ziehen per Random(49) +1 aber immer eine Kugel aus 49 möglichen. Wird eine Kugel gezogen die schon aus der Urne genommen wurde, was ja eigentlich gar nicht möglich sein dürfte, schmeisst der Ziehungsleiter im Fernsehen sie dann ganz still und leise zurück in die Urne ??

Setzen, 5, Thema verfehlt

D.h. bei 6 aus 49 sind die Wahrscheinlichkeiten für eine Zahl jeweils

1. Zug = 1/49
2. Zug = 1/48
3. Zug = 1/47
4. Zug = 1/46
5. Zug = 1/45
6. Zug = 1/44

Delphi-Quellcode:

type
  TZahlen = array of Integer;

procedure Lotto(var Sortiert,Gezogene: TZahlen; Ziehungen: Integer = 6; Elemente: Integer = 49);
var
  I,J,K,N: Integer;
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');

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

  for I := 0 to Ziehungen -1 do
  begin
    K := 0;
    N := Random(Elemente - I) + 1;
    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;
  end;
end;

procedure Test;

  procedure Print(const Title: String; const Zahlen: TZahlen);
  var
    I: Integer;
  begin
    Write(Title);
    for I := 0 to High(Zahlen) do Write(Zahlen[I]:4);
    WriteLn;
  end;

var
  Sortiert,Gezogene: TZahlen;
begin
  Lotto(Sortiert, Gezogene, 6, 49);

  Print('gezogene : ', Gezogene);
  Print('sortiert : ', Sortiert);
  WriteLn;
end;

Um obigen Source etwas zu erklären:
Man zieht bei 6 aus 49 jeweils aus 49,48,47,46,45,44 Zahlen eine per Random. Um die Sache schön Speichereffizient zu machen verzichten wir auf ein Array[0..48] of Boolean o.ä. Techniken und nutzen eine "Lücken-Sprung" Technik. Wir korregieren also die gezogene Zahl jeweils so das sie die schon gezogenen Zahlen mit berücksichtigt, denn eine einmal gezogene Zahl darf nicht zweimal gezogen werden.

Beispiel 5 aus 5:
1. Zug = 3 aus 5, das 3. Element aus 1,2,3,4,5 ist 3, effektive Zahl = 3, es bleiben 1,2,4,5
2. Zug = 1 aus 4, das 1. Element aus 1,2,4,5 ist 1, effektive Zahl = 1, es bleiben 2,4,5
3. Zug = 2 aus 3, das 2. Element aus 2,4,5 ist 4, effektive Zahl = 4, es bleiben 2,5
4. Zug = 1 aus 2, das 1. Element aus 2,5 ist 2, effektive Zahl = 2
5. Zug = 1 aus 1, das 1. Element aus 5 ist 5, effektive Zahl = 5

Somit haben wir 3,1,4,2,5 gezogen.

Exakt so geht obiger Algorithmus vor. Er benötigt dazu eine sortierte Liste aller bisher gezogenen Zahlen und muß N nur noch so korrigieren das es die in der Urne verbleibenden Zahlen berücksichtigt.

Somit simuliert obiger Algorithmus exakt die Realitäten und Wahscheinlichkeiten beim Lotto.
Alle anderen bisherigen Vorschläge verfälschen die Wahrscheinlichkeiten, denn wenn z.B. im 3. Zug die 5 aus 49 Kugeln gezogen wurde und die 5 schon vorher gezogen wurde dann ist die effektive Wahrscheinlichkeit 1/49 + 1/49 = 2/49 für jede Zahl gewesen. Es müsste aber exakt 1/47 sein.


Gruß Hagen

PS: falls du eine Eins bekommst schuldest du uns aber was
PPS: Übrigens, exakt diese Aufgabe habe ich immer meinen Informatik-Lehrlingen gestellt !

[Christian Seehase]

Moin Hagen,

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.

[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;

[Christian Seehase]

Moin Hagen,

hast ja recht
Ich hab' das jetzt vorerst mal experimentell überprüft.
Für eine genaue Analyse ist es mir jetzt denn doch zu spät.