Ordung muss sein

[block35plus1]

Hi erst mal.
habe mcih gerade angemeldet. Ich hab seit einem JAhr Informatik in der Schule, wir machen eigentlich nur Delphi. Da ich im ersten Jahr garr nix verstanden habe und 5 stand will cih jetzt versuchen alles nachzuholen. :wall: ich hab auhc gemerkt dass es ein bisschen spaß macht. aber ich habe jetzt eine frage zu meinen Hausaufgaben.

Wir haben ein Lottoprogramm geschrieben, welches 6 zufällige Zahlen von 1 bis 49 zieht. als Hausaufgabe sollten wir u.a. versuchen. die Zalhen im MemoFeld zu ordnen und das keine gleichen ZTahlen vorkommen. Das habe ich bisher:

Delphi-Quellcode:

unit mLotto;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
TLottozahlen=array[1..6] of Integer;
  TForm1 = class(TForm)
    MemAusgabe: TMemo;
    btnZiehen: TButton;
    procedure btnZiehenClick(Sender: TObject);
  private
    { Private-Deklarationen}
  public
    { Public-Deklarationen}
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.BtnZiehenClick(Sender: TObject);
Var
   Lottozahlen:TLottozahlen;

   Procedure Zahlen_ermitteln(var Lottozahlen:TLottozahlen);
   var i:integer;
   begin
   randomize;
   for i:=1 to 6 do
   Lottozahlen[i]:=random(49)+1;
   end;

   procedure Zahlen_ausgeben(Lottozahlen:TLottozahlen);
   var i:integer;
   begin
   for i:=1 to 6 do
   MemAusgabe.Lines.Add(IntToStr(Lottozahlen[i]));
   end;

begin
Zahlen_ermitteln(Lottozahlen);
Zahlen_ausgeben(Lottozahlen);
end;

end.

Danke Tobias

[edit=MrSpock]Code Tags eingefügt. Mfg, MrSpock[/edit]

[Duffy]

Hallo block35plus1,
schau Dir mal diesen Beitrag an, er sollte Dir helfen
Hilfe bei nem Algorythmus
bye

[MrSpock]

Hallo Block35plus1,

wenn du auch eine Listbox benutzen darfst, sparst du dir eine Menge Arbeit.
(Ob das aber deine Informatiknote nach oben bringt, weiß ich nicht :mrgreen: )

Eine Listbox hat nämlich die Eigenschaft Sorted, die du nur auf True stellen musst.
Wichtig ist aber dann, dass du die einstelligen Zahlen mit führender Null schreiben muss.

Delphi-Quellcode:

 procedure Zahlen_ausgeben(Lottozahlen:TLottozahlen);
   var i:integer;
   begin
    { ListBox1.Sorted im OI auf True setzen. }
     for i:=1 to 6 do
       ListBox1.Items.Add(Format('%.2d', [Lottozahlen[i]]));
   end;

[block35plus1]

wo kann ich die denn genau auf null stellen und wie mach ich das genau, dass vor den einstelligen eine Null steht?

[MrSpock]

Hallo Block35plus1,

wie oben im Code gezeigt mit der Format Funktion.

[block35plus1]

:gruebel: mhh ich muss ernsthaft sagen, dass ich nur bahnhof verstehe. aber ich finde es total nett, dass ihr mir helfen wollt... :cheers:

[Christian Seehase]

Moin block35plus1,

mal eine Frage zum Zahlen_ermitteln.
Ist es gewollt, dass Zahlen doppelt gezogen werden können?

[block35plus1]

ne dass ist nciht gewollt. da´habe ich aber schon eine Lösung für Zahlen_ermitteln, aber die Lösung für Zahlen_ausgeben fehlt :(

Delphi-Quellcode:

var i,j,Zahl : Integer;
   begin Randomize;
   for i := 1 to 6 do
   begin
   zahl := random (49)+1;
   j := 1;
   while j<i do
   begin
   if Lottozahlen[j] = zahl
   then begin
   zahl := random (49)+1;
   j:=0;
   end;
   j:=1+1;
   end;
   Lottozahlen[i]:=zahl;
   end;
   end;

[edit=Christian Seehase]Delphi-Tags hinzugefügt. Bitte künftig selber machen. Danke. Mfg, Christian Seehase[/edit]

[Christian Seehase]

Moin block35plus1,

Mal eine Variante dazu. Ist aber ungetestet.

Delphi-Quellcode:

Procedure Zahlen_ermittelnOHNEDoppelte(var Lottozahlen:TLottozahlen);
var
  i       : integer;
  iZahl   : integer;
  iCount  : integer;
  fExists : boolean;

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

[MrSpock]

Hallo Block35plus1,

zum Thema Bahnhof :mrgreen: :

Die Funktion Format ermöglicht das Formatieren von Zahlen oder Strings für die Ausgabe. Schau dir dazu vielleicht einmal die Onlinehilfe an.
Der Code oben:

Delphi-Quellcode:

Format('%.2d', [Lottozahlen[index]])

gibt einen String zurück, der die Zahl (Lottozahl[index]) immer zweistellig zurück gibt.

[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 :cheers:
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 :-D :oops:
Ich hab' das jetzt vorerst mal experimentell überprüft.
Für eine genaue Analyse ist es mir jetzt denn doch zu spät. :mrgreen:

[Sharky]

Hai,

ich bekomme zwar auch eine 5 weil ich die Kugel wieder zurück werfe; aber eventuell ist es für einen Anfänger trotzdem leichter zu verstehen ;-)

Delphi-Quellcode:

const
 kugeln = 49;
 ziehungen = 6;

type
  Tzahlen = Array[1..kugeln] Of Char;

procedure Lotto (Var zahlen : TZahlen) ;
var
 ndx,
 gezogen : Integer;
 neueZahl    : Boolean;
begin
 Randomize;
 FillChar(zahlen,kugeln,Ord(' '));
 for ndx := 1 to ziehungen do
  begin
   neueZahl := False;
   Repeat
    gezogen :=  Random(kugeln)+1;
    if(zahlen[gezogen] <> 'X') then
     begin
      neueZahl := True;
      zahlen[gezogen] := 'X';
     end;
   Until (neueZahl)
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
 ndx : Integer;
 gezogen : TZahlen;
begin
 Lotto (gezogen);
 memo1.Clear;
 for ndx := 1 to kugeln do
  begin
   if (gezogen[ndx]) ='X' then
    begin
     Memo1.Lines.Add (IntToStr (ndx));
    end;
  end;
end;

Zitat:

Zitat von negaH

..... Um die Sache schön Speichereffizient zu machen verzichten wir auf ein Array[0..48] of Boolean o.ä.....

Hai Hagen,
wiedersprichst Du dir da nicht? Du benutzt doch selber zwei Array in deiner Funktion.
Aber Matematisch und Logisch gesehen ist dein Code der optimale.

[negaH]

Zitat:

Hai Hagen,
wiedersprichst Du dir da nicht? Du benutzt doch selber zwei Array in deiner Funktion.

Warum ? Wenn du 5 aus 1000 ziehen möchtest dann gibt es drei Wege:
1.) eine Liste mit 1000 Zahlen von 1 bis 1000
2.) eine Liste mit 1000 Bits, jedes Bit steht dafür ob die Zahl noch in der Urne ist
3.) eine Liste mit 5 Zahlen, die die gezogenen Zahlen enthalten

So wie 3. funktioniert mein Algorithmus. Aber, um die Lotto() procedure flexibel zu machen habe ich die gezogenen Zahlen in eine sortierte und unsortierte Liste gespeichert. Man benötigt aber nur die sortierte Liste damit der Algo funktioniert.

Somit benötigt man entweder viel Speicher mit 1000 Zahlen oder wenig mit nur 5 Zahlen. Ich meine schon das dies Speichereffizient ist.

Du solltest auch berücksichtigen das das letzte Posting von mir eine Demonstration zur Beweisführung ist. Gehe drei Postings zurück und du findest den richtigen Algorithmus.

Aber du hast natürlich recht, ich wieder-spreche mich sehr oft, denn ich labere und quatsche sehr gerne :) Allerdings, wider-sprochen habe ich mich bis jetzt nicht.

So nun zum eigentlichen Problem was ich persönlich damit habe.
Wenn der Programmierer eine Aufgabe gestellt bekommt, dann ist es NICHT unwichtig ob die Lösung des Problemes zwar funktioniert aber denoch NICHT der Aufgabenstellung entspricht. Dieses Denken bei vielen Programmieren empfinde ich als enorm unprofessionell, auch wenn es nur Hobby ist. Denn wenn ich ein finanzielles Problem habe, dann erwarte ich das der Mann von der Bank mein finanzielles Problem auch richtig erfassen kann. Oder, wenn mein Auto ne Macke hat, dann reicht es mir NICHT wenn der Mechaniker mit'n Vorschlaghammer zweimal auf den Motoblock hämmert und das Quietschen dann weg ist. Genau das gleiche gilt für uns Programierer, meiner Meinung nach.


Gruß Hagen

[Brüggendiek]

Hallo!

Vor einiger Zeit hatte ich mal zum Thema Lotto was gepostet - hier die Wiederholung:

Ein Stringlist mit den möglichen Werten füllen, hier also 1 bis 49 in aufsteigender Reihenfolge.
Dann in einer Ziehungsschleife: eine Zufallszahl von 0 bis Anzahl der Elemente ziehen, den Wert als Index für die Liste nehmen, Wert auslesen und löschen!

Damit baut man die Ziehungstrommel nach und kann z.B. auch eine Anzahl Werte in zufälliger Reihenfolge bringen.
Bei 6 (bzw. mit Zusatzzahl 7) aus 49 ist die Wahrscheinlichkeit, eine schon gezogene Zahl zu treffen, relativ klein und mit "verwerfen, wenn schon gezogen" kann man auch zum Ziel kommen. Soll ich aber die Zahlen von 1 bis 100 in zufällige Reihenfolge bringen (also 100 aus 100 losen), wird der Aufwand gegen Ende sehr groß, weil nur noch 2 Werte übrig sind und damit 98% Wahrscheinlichkeit für Fehltreffer besteht. Da hilft die Listenmethode definitiv weiter, da garantiert eine noch nicht gezogene Zahl kommt.
Das Ganze läßt sich z.B. auch auf Spielkarten aller Art übertragen.

Gruß

Dietmar Brüggendiek

[Leuselator]

hmm - is vielleicht methodisch nicht so brilliant, tut's aber
(so 1 x alle 2 Jahre spiel ich auch :oops: , und dann sollte es ein bisserl Zufall sein :wink: )

PS: ich weiß, mein Codierstil is nicht standardkonform - sorry

[Hansa]

Hagen ist mal wieder der Algorithmen-König. :lol: Wenn ich jetzt nichts überlesen habe, geht es doch lediglich um 49 Zahlen. Diese Zahl ist also bekannt und übersichtlich. Deshalb ist mir die Lösung mit Zeigern in diesem Fall zu kompliziert, zumindest für einen Anfänger, obwohl sie richtig ist, wegen Speicher usw. Die Arrays haben andere Nachteile. Und wo bleibt jetzt das:

Delphi-Quellcode:

Lottozahlen : SET OF byte;

Dieses erst mal bestücken von 1 bis 49. Mit random (49) usw. eine Zahl ziehen,

Delphi-Quellcode:

LottoZahlen := LottoZahlen - [gezogene]

und dann mit random (48) weitermachen ? Wobei sich die 49,48 usw. auf die ord des Sets bezieht. 8)

@Mods: Wie schreibe ich eigentlich random (48 noch mit einer abschließenden Klammer, statt eines 8) ?

[flomei]

Zitat:

Zitat von Hansa

@Mods: Wie schreibe ich eigentlich random (48 noch mit einer abschließenden Klammer, statt eines 8) ?

:mrgreen: (48 ) ?!?

MfG Florian :hi:

[Hansa]

typisch Weichei. Aber trotzdem richtig. :shock: Ich habe aber extra @Mods geschrieben. :P @flomei: was hast du zu der Sache mit dem Set zu sagen ? Nichts ? :mrgreen:

[flomei]

Zitat:

Zitat von Hansa

typisch Weichei.

WO??? :roll:

Zitat:

Zitat von Hansa

Aber trotzdem richtig. :shock:

Na klar! Glaubst du ich gebe falsche Antworten? :?

Zitat:

Zitat von Hansa

Ich habe aber extra @Mods geschrieben. :P

Sei ruhig, sonst zöger ich das nächste DP-Update noch nen Jahr raus! :P

Zitat:

Zitat von Hansa

@flomei: was hast du zu der Sache mit dem Set zu sagen ? Nichts ? :mrgreen:

:roll: Du gibst doch wohl hoffentlich auch nur korrekte Antworten! Also: Was willst du jetzt hören??? :P :P

MfG Florian :)

[EDIT] 1 : 0 für flomei! :mrgreen: [/EDIT]

[negaH]

Set's wären das gleiche wie TBits usw. Das Problem mit Sets verschärft sich im Gegensatz mit der obigen "Bewisführung" über eine List: array[] of Zahl. Denn bei Sets entsteht trotzdem das Problem das dieses immer 49 Elemente enthält und nur die Frage klären kann welche Zahl schon herausgenommen wurde. Sets vereinfachen algorithmisch also nicht die Frage wie man aus 49 Zahlen, aber nur noch 46 Zahlen in der Urne die nächste Zahl herausnimmt. Die Elementezahl der Urne = Set, ist unveränderlich, wir benötigen aber eine Urne die nach jeder gezogenen Zahl die Anzhal der Elemente in der Urne dekrementiert. Nur dann wäre ein Sets algorithmisch gesehen effizienter als mein Algo. Es sei denn man schreibt meinen Algo so um das er nur mit dem Set der schon gezogenen Zahlen arbeitet. Dann würde er bei 6 aus 49 das Set der gezogenen Zahlen aus 49 Bits = Int64 = 8 Bytes bestehen. Meine Liste der gezogenen Zahlen benötigt dagegen 24 Bytes.
Aber, Bitoperationen sind auf 32Bit CPU's die vorwiegend sehr schnell mit Cardinals arbeiten, wesentlich langsammer als ein Tabellenlookup. Diese Lookups sind in meinem Algo. ebenfalls optimal codiert, da sie auf sortierten Arrays[] die neuen Elemente sortiert einfügen. Das dafür verwendete Verfahren nennt man Insertion Sort und ist mit kleinen Arrays[] effizienter als zB. Quicksort.
Zudem ermittelt mein Algo. in einem Schritt die Sortierung und die korrekte gezogene Zahl.
Für einen Lottozahlen Algorithmus ist mein Vorschlag eines der optimiertesten Verfahren überhaupt, wenn nicht sogar das beste wenn man auch die Universalität berücksichtigt.

Gruß Hagen

[Hansa]

Das mit dem Set hat mir jetzt doch keine Ruhe gelassen. Gut, gebe zu, daß das jetzt ein halbes Holzhammer-Programm ist :wink: :

Delphi-Quellcode:

procedure TForm1.FormCreate(Sender: TObject);
var i : byte;
begin
  randomize;
  BereitsGezogen := 0;
  gezogene := [];
  for i := 1 to 49 do begin
    LottoZahlen := LottoZahlen + [i];
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,kugel : byte;
begin
  if Bereitsgezogen < 6 then begin
    Repeat
      kugel := random (48) + 1;
      i := i + 1;
    until not (kugel in gezogene);
    BereitsGezogen := BereitsGezogen + 1;
    Label1.Caption := 'gezogen: '+ IntToStr (BereitsGezogen);
    Memo1.Lines.Add(IntToStr (Kugel));
    gezogene := gezogene + [Kugel];
    LottoZahlen := LottoZahlen - [kugel];
  end
  else
    ShowMessage ('Schon 6 Kugeln gezogen !');
end;

Tja, habe selbst dumm geguckt wie mickrig das ganze geworden ist. Da es aber wirklich sehr einfach zu verstehen ist, will ich das den Anfängern nicht vorenthalten. Vom Prinzip her gleicht es dem von Hagen, nur ich benutze 2 Sets, statt 2 dyn. Arrays. Optimiert ist auch nichts.

Aber :!: So programmiere ich normalerweise nicht ! Ich habe 1. keine Konstanten benutzt, sondern die Zahlen stehen mehrfach explizit im Quelltext und 2. die Repeat-Schleife, die gefällt mir nun überhaupt nicht, theoretisch könnte die ins Unendliche laufen. Also meine lieben Kinder :mrgreen: , bitte nicht einen solchen Stil überall verwenden, sonst kriegt ihr Haue von der Mami.

Hier noch die 2 Sets:

Delphi-Quellcode:

  private
    { Private declarations }
    BereitsGezogen : byte;
    gezogene,
    Lottozahlen : SET OF byte;

[negaH]

Delphi-Quellcode:

  if Bereitsgezogen < 6 then begin 
    Repeat 
      kugel := random (48) + 1; 
      i := i + 1; 
    until not (kugel in gezogene);

und genau hier ist wieder der Fehler drinnen, der diesen Algo. eben nicht identisch zu meinen macht.

Angenommen 3 Kugeln wurden schon gezogen, dann verbleiben 46 Kugeln in der Urne und somit muß es Random(46) heissen. Eine Kugel die bereits gezogen wurde KANN NICHT erneut aus der Urne gezogen werden da sie nicht mehr enthalten ist. In deinem Code ziehst du immer eine Kugel aus immer 49 ( 48 ) Kugeln und falls sie schon gezogen wurde, schmeisst du sie zurück in die Urne und zieht nochmal eine Kugel. Damit verändern sich die Wahrscheinlichkeiten pro Kugel in der Urne mit der sie gezogen werden kann. Der Algo. simuliert also ebenfalls nicht die Lotto-Realität und ist falsch.
Zudem wird mit Random( 48 ) = 0..47 + 1 = 1..48 nicht 1 aus 49 gezogen sondern 1 aus 48.

Gruß Hagen

[Hansa]

Zitat:

Zitat von negaH

...Angenommen 3 Kugeln wurden schon gezogen, dann verbleiben 46 Kugeln in der Urne und somit muß es Random(46) heissen...

Und genau da habe ich aufgehört. Ich käme dann an die 47..49 nicht mehr dran, sofern sie nicht zufällig bereits gezogen sind. Mehrfachziehung geht aber mit meinem Code trotzdem nicht. Bereits gezogene Kugeln werden einfach ignoriert und es wird neu gezogen, was bei Ziehung 48 aus 49 aber echt nicht besonders wäre. Zum Schluß hätte man dann noch 2 Kugeln und der Zufallsgenerator braucht ewig 3..49 zu durchsuchen, die auszuschließen und neu anzufangen, bis er endlich bei 1 oder 2 landet. Bei 6 aus 49 und EINER Ziehung ist es allerdings meiner Ansicht nach so machbar. Zumindest für eine 3 in der Schule. :mrgreen: Richtig machen würde ich das auch mit 2 Listen, statt 2 Sets.

Und wegen der in diesem Fall klar begrenzten und kleinen Zahlenmengen gehts wie gesagt auch mit Arrays.

[negaH]

Zitat:

Ich käme dann an die 47..49 nicht mehr dran, sofern sie nicht zufällig bereits gezogen sind. Mehrfachziehung geht aber mit meinem Code trotzdem nicht. Bereits gezogene Kugeln werden einfach ignoriert und es wird neu gezogen, was bei Ziehung 48 aus 49 aber echt nicht besonders wäre

Dein Code macht Mehrfachziehungen. Eine Ziehung einer Kugel ist das zufällige Auswählen einer Kugel. Stellt dein Algo. fest das dieses Auswählen eine Kugel zieht die schon gezogen wurde so wählt er erneut stattdessen ein Kugel aus. Dies ist eben falsch da nun zum Auswählen dieser Kugel schon zweimal mit 1/49 eine Kugel gewählt wurde.
Nochmal:

die Kugeln 4,34,20 wurden schon gezogen. Es sind noch 46 Kugeln in der Urne. Die nächste Kugel die gezogen wird MUSS mit einer Wahscheinlichkeit von exakt 1 aus 46 gezogen werden.

Nun dein Algo. wählt per Zufall 1 aus 49 aus, und es ist die 4 . Da die 4 schon gezogen wurde wird erneut eine Kugel aus 1 aus 49 gezogen, und es ist die 34. Da die 34 schon gezogen wurde wählt der Algo. erneut eine Kugel aus 49 aus und es ist die 20. Da die 20 schon gezogen wurde zieht er erneut und hat die 32.

So, rechne nach. Um die vierte Kugel zu ermitteln hat dein Algo 1/49 + 1/49 + 1/49 + 1/49 = 4/49 benötigt, und somit eine komplett andere Gesamtwahrscheinlichkeit pro Kugel erzeugt. Jede Kugel der 46 möglichen Kugeln im 4. Zug könnte also in diesem Beispiel mit exakt 4/49 Wahrscheinlichkeit gezogen werden. Dies ist falsch.

Da du immer aus 49 Kugeln ziehst und beim Mehrfachziehen schon gezogener Kugeln erneut eine ziehst heisst die das dein Algo. die doppelt gezogene Kugel sozusagen zurücklegt in die Urne. Würde der Algo. richtig arbeiten so dürfte er eine gezogene Kugel nicht in die Urne zurücklegen. Stattdessen entnimmet er die Kugel der Urne, und somit ist eine Kugel weniger in der Urne. Dadurch muss sich die Wahrscheinlichkeit das eine Kugel gezogen wird, von Zug zu Zug für jede Kugel erhöhen.

Gruß Hagen

[Hansa]

Jetzt muß ich doch tatsächlich noch den Kram mit der Wahrscheinlichkeitstheorie aus meinem Gehirn raussuchen. :cry: Aber da war ich gut drin. Eine richtige Lottoziehung ist das wirklich nicht. Das Gesamtergebnis Anzahl Ziehungen und Endergebnis ist nicht wie beim echten Lotto. ABER: Die Wahrscheinlichkeit für jede Zahl pro Ziehung bleibt gleich, weil ich ja die gezogenen nicht beachte. Wirkt sich das auf das Endergebnis jetzt irgendwie aus ? :gruebel: Wer es nicht weiß: ziehe ich eine Zahl aus 100 ist die Wahrscheinlichkeit 1 %. Lege ich sie wieder rein, wie hoch ist sie dann, daß genau diese Zahl bei der nächsten Ziehung wieder kommt :?: Nein, verrate ich nicht sofort.

Und gleich die nächste Preisfrage: Wie hoch ist die Wahrscheinlichkeit, daß ich gewinne mit der Wettaussage: "Jetzt kommt zweimal hintereinander die 1" ? @Hagen: Bitte nichts verraten, die Antwort steht hier fast im Thread. :lol:

[imp]

Oh weh, da ist sie wieder die bedingte Wahrscheinlichkeit. Da hatte ich schon immer meine Schwierigkeiten mit. Da ich Grundsätzlich zuerst mal die falsche Antwort gebe lasse ich es lieber sein. Aber mir fallen in diesem Zusammenhang immer zwei Fragen (Probleme) ein die zwar nicht hierhergehören (oder doch?) aber trotzdem immer wieder gut sind:
1) Ziegenproblem:
Gegeben: 3 Tore hinter denen sich zwei Ziegen und ein Auto befinden. Der Kandidat wählt ein Tor,
woraufhin der Quizmaster eines der zwei verbliebenen öffnet hinter dem sich eine Ziege befindet.
Frage: Behält man das Tor das man zuerst gewählt hat oder nimmt man das andere?
2) Geschwisterproblem:
Gegeben: Vater der zwei Kinder hat wovon eines ein Sohn ist.
Frage: Mit welcher Wahrscheinlichkeit hat der Sohn einen Bruder?

[Sharky]

Zitat:

Zitat von imp

....
2) Geschwisterproblem:
Gegeben: Vater der zwei Kinder hat wovon eines ein Sohn ist.
Frage: Mit welcher Wahrscheinlichkeit hat der Sohn einen Bruder?

Ist der geannte Sohn das ältere oder jüngere Kind?

[negaH]

Zitat:

ABER: Die Wahrscheinlichkeit für jede Zahl pro Ziehung bleibt gleich, weil ich ja die gezogenen nicht beachte.

Eben nicht. Eine Ziehung ist das erfolgreiche zufällige herausnehmen einer Kugel. Wird bei einem Zug eine Kugel gezogen die schon gezogen wurde, so muß für diese Ziehung erneut eine andere Kugel heraus genommen werden. Somit verändern sich die Wahrscheinlichkeiten für jede ziehbare Kugel pro Ziehung im gesammten, auch für die abschließend korrekt gezogenen Kugeln. So arbeitet dein Algo und das ist definitiv nicht richtig. Die Wahrscheinlichkeiten die sich auf Grund der Realitäten ergeben sind vorgegeben und unveränderlich.
Ok, meine obigen Rechnungen sind nicht ganz exakt, denn sie berücksichtigten nicht die abzuziehende Wahrscheinlichkeit für die doppelt gezogene Kugel. Allerdings spielte das zur Demonstration warum der Algo nicht korrekt ist keine wichtige Rolle.

Gruß Hagen

[Hansa]

Zitat:

Zitat von imp

2) Geschwisterproblem:
Gegeben: Vater der zwei Kinder hat wovon eines ein Sohn ist.
Frage: Mit welcher Wahrscheinlichkeit hat der Sohn einen Bruder?

Wahrscheinlich ist da ein Haken dabei, sieht zu einfach aus,mir egal. Ich sage mal 25 %. Die Wahrscheinlichkeit beim 1. Kind ist nämlich 0.5 und beim zweiten wieder 0.5. Also 25%(=0.5 * 0.5). Und es gibt ja auch nur 4 Möglichkeiten:

ww,wm,mw,mm für die 2 Kinder. Wie gesagt nach dem 1. Kind ist sie 50 % und das ändert sich mit steiegender Kinderzahl auch nicht :!:

Tja und mit meinem Algo bin ich mir noch nicht so ganz im reinen. Wird nicht durch zurücklegen der Kugel wieder die alte Wahrscheinlichkeit wiederhergestellt ? Daß der Algo an sich so nicht gut ist, ist wohl klar.

[Sharky]

Zitat:

Zitat von Hansa

... Ich sage mal 25 %. Die Wahrscheinlichkeit beim 1. Kind ist nämlich 0.5 und beim zweiten wieder 0.5. Also 25%(=0.5 * 0.5). Und es gibt ja auch nur 4 Möglichkeiten:
ww,wm,mw,mm für die 2 Kinder. Wie gesagt nach dem 1. Kind ist sie 50 % und das ändert sich mit steiegender Kinderzahl auch nicht ...

Entweder 1/3 oder 1/2

Wie Du selber sagst gibt es maximal 4 Möglichkeiten. Die Möglichkeit ww ist aber ausgeschlossen. Bleiben also 3.

Ist der genannte Sohn der ältere verbleibt nur noch wm und mm dann wäre es 1/2 genauso wenn bekannt ist das er der jüngere ist.

Man sieht. Wahrscheinlichkeiten kann ich von verschiedenen Gesichtspunkten aus betrachten ;-)

[negaH]

Zitat:

Wird nicht durch zurücklegen der Kugel wieder die alte Wahrscheinlichkeit wiederhergestellt ?

Nein, da eine Ziehung damit verlängert wird.
Grundsätzlich darf es garnicht vorkommen das man eine Kugel mehrmals ziehen kann. Wird im Lotto eine Kugel gezogen so ist sie nicht mehr im Spiel, eg. Urne. D.h. Wahrscheinlichkeiten ohne zurücklegen.

Ist es denoch möglich das eine Kugel mehrmals gezogen werden kann, dann ist das "Wahrscheinlichkeit mit zurücklegen". Da dies dem Lottosystem widerspricht muß dein Algo. sicherstellen das die gezogene Kugel nicht schon gezogen wurde. Aus Sicht der Lotto-Ziehung einer Kugel, als Aktion die eine fixiert Wahrscheinlichkeit besitzt, würde dein Algo. daraus eine Ziehung mit "veränderlicher Wahrscheinlichkeit" machen. Denn NICHT das Auswählen EINER Kugel aus der Urne bestimmt die Wahrscheinlichkeit sondern die Ziehung einer korrekten Kugel, bestimmt die Gesamtwahrscheinlichkeit.

Anders ausgedrückt: beim Lotto 6 aus 49 entstehen drei Wahrscheinlichkeiten:
1.) die Wahrscheinlichkeit pro Kugel aus der Urne das sie jetzt gezogen wird
2.) die Wahrscheinlichkeit pro Ziehung das eine bestimmte Kugel gezogen wird
3.) die Wahrscheinlichkeit jeder Kugel das sie innerhalb von 6 Ziehungen gezogen wird.

1. und 2. sind beim Lotto identisch, aber NICHT in deinem Algo.
1. und 2. und 3. sind feste unveränderliche Wahrscheinlichkeiten, d.h. sie dürfen sich auf grund der Art und Weise wie man die Kugeln zieht, nicht verändern.

Beim Lotto:
1.) 1/49, 1/48, 1/47, 1/46, 1/45, 1/44 jeweils nach x. Zug
2.) = 1.)
3.) 1/49 + 1/48 + 1/47 + 1/46 + 1/45 + 1/44

Bei deinem Algo
1.) 1/49, 1/49, 1/49, 1/49, 1/49, 1/49 jeweils nach x. Zug
2.) 1/49, 1/49 + (1/49) / (1/48 ) + (1/49) / (1/48 ) / (1/47) .... / (1/44), 1/49 + (2/49) / (2/48 ) .... / (2/44), ...
3.) 1/49 + (1/49 + (1/49) / (1/48 ) + (1/49) / (1/48 ) / (1/47) ...., ......

Letzendlich entsteht eine andere Wahrscheinlichkeit der gesamten Lottoziehung.

Man sieht das im Schritt 1, durch das Zurücklegen sich die Wahrscheinlichkeit pro Kugel nicht erhöht wie beim Lotto.
Im Schritt 2.) sprich die Ziehung der x. Kugel im gesamten, sieht man das durch die Möglichkeit der Mehrfachziehung die Wahscheinlichkeiten erhöhen pro Kugel gezogen zu werden.
Dies hat zur Folge das im 3.) Schritt für das gesammte Lotto von 6 aus 49 sich eine komplett andere Gesamtwahrscheinlichkeit pro Kugel ergibt.
So gesehen verändert dein Algo. die Wahrscheinlichkeiten bei mehrfach ziehbaren Kugeln, auch wenn am Ende keine Kugel doppelt vorkommt.

Gruß Hagen