Ordung muss sein

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