Autor |
Beitrag |
Hiprog
      
Beiträge: 25
WIN XP Professional(SP2)
Delphi 7 Enterprise
|
Verfasst: So 15.04.07 21:16
Hi.
Gibt es eine Möglichkeit bei Delphi eine Zahl aus dem Random Befehl zu entfernen?
Damit meine ich, dass wenn man um Beispiel aus random(30) die Zahl 3 bekommt, dass diese nicht wieder benutzt wird?
Und gibt es danach eine Möglichkeit die Zahl dann wieder anzeigen zu lassen?
Vielen Dank schon mal im voraus.
|
|
Marc.
      
Beiträge: 1876
Erhaltene Danke: 129
Win 8.1, Xubuntu 15.10
|
Verfasst: So 15.04.07 21:50
Das Thema hatte wir hier schon oft, aber nun gut:
Ein Variante wäre folgende:
• Du speicherst deine Zahlen in einem Array
• überprüfst dann in einer (For-)Schleife, ob die neue Zufallszahl darin vorkommt,
• wenn ja dann lass ihn mit "repeat until" oder mit einer "while"-Schleife so lange würfeln, bist die Zahl nicht mehr in diesem Array vorkommt.
im Grunde recht simpel. 
|
|
Karlson
      
Beiträge: 2088
|
Verfasst: So 15.04.07 21:58
Kann ich absolut nicht empfehlen diesen Weg. Viel Spass wenn 5000 Zahlen mit diesem Weg erzeugt werden sollen...
Das geht eleganter über folgenden Weg:
1.) Bei x Zufallszahlen ein dyn. Array der Länge x.
2.) Dieses Array mit einer einfachen For-Schleife fortlaufend mit den Zahlen 1 bis x füllen.
3.) Mit Random(high(Array)) auf ein Element zugreifen.
4.) Den Wert des Arrays in die Zahlenliste eintragen.
5.) Das Array-Element löschen und die Grösse des Arrays auf Grösse-1 setzen.
|
|
Marc.
      
Beiträge: 1876
Erhaltene Danke: 129
Win 8.1, Xubuntu 15.10
|
Verfasst: So 15.04.07 22:02
Für 5000 Zahlen braucht er nur ein paar Zehntel-Sekunden.
Ab 50.000 mehere Sekunden. Aber ich geb dir recht, deine ist die absolut schnellere Variante. 
|
|
Karlson
      
Beiträge: 2088
|
Verfasst: So 15.04.07 22:50
Jo im Normalfall braucht man solche Berechnungen ja nicht unbedingt performant. Trotzdem sollte man schon sparen wo's geht.
|
|
Hiprog 
      
Beiträge: 25
WIN XP Professional(SP2)
Delphi 7 Enterprise
|
Verfasst: Mo 16.04.07 05:17
Danke erstmal.
Das sollte für ein Sudoku Programm sein und ich hab das so wie im ersten Priznzip vorgeschlagen ine twa gemacht. Das dauert bei mir dann in etwa3-4 Minuten das Spiel zu erzeugen und es hat Fehler (Zahlen kommen doppelt vor...).
Wie ist das mit dem random(high(array)) gemeint? Ist das ein besonderer Befehl oder so?
|
|
Karlson
      
Beiträge: 2088
|
Verfasst: Mo 16.04.07 05:34
Zeig mal wie du das umgesetzt hast (anhand von Code).
|
|
Karlson
      
Beiträge: 2088
|
Verfasst: Mo 16.04.07 06:18
Ich hab mich gerade mal damit beschäftigt und beide Varianten ausprobiert.
Meine Variante:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29:
| procedure TForm1.Button2Click(Sender: TObject); procedure DeleteEl(arr: Array of Integer; index: integer); var i: integer; begin if index<high(arr) then begin for i:=index to high(arr)-1 do arr[i]:=arr[i+1]; end; end; var arr : Array of Integer; a : integer; i : integer; rList : Array[0..4999] of Integer; n1,n2 : integer; begin n1:=GetTickCount; setLength(arr, 5000); for i:=0 to 4999 do arr[i]:=i; for i:=0 to 4999 do begin if (i>0) then setLength(arr, length(arr)-1); a:=Random(length(arr)); rList[i]:=Arr[a]; DeleteEl(Arr, a); end; n2:=GetTickCount; showmessage(inttostr(n2-n1)); end; |
Marcs Variante:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
| procedure TForm1.Button1Click(Sender: TObject); function InArray(a:integer; sList : array of Integer):boolean; var i : integer; begin result:=true; for i:= low(slist) to high(slist) do begin if slist[i]=a then exit; if sList[i]=0 then break; end; result:=true; end; var i : integer; s : Array[0..4999] of Integer; a : Integer; n1,n2 : integer; begin n1:=GetTickCount; ZeroMemory(@s, sizeOf(s)); for i:=0 to 4999 do begin a:=random(5000)+1; while not InArray(a, s) do a:=Random(5000)+1; s[i]:=a; end; n2:=GetTickCount; end; |
Ich hab hier jetzt einfach Zufallszahlen von 1 bis 5000 produziert, so konnte ich nämlich ZeroMemory zum Initalisieren des Arrays nutzen, was wesentlich schneller als vergleichbares ist.
Hm. Meine Variante benötigt immerhin noch 47 ms, während Marcs Varianten 125 ms benötigt. Ehrlich gesagt hätte ich mir einen grösseren Unterschied vorgestellt. Wobei mehr als 75% bei grossen Datenmengen natürlich schon okay ist.
Ich müsste mal mehrere Durchlaufzeiten überprüfen. Das Problem an Marcs Algorithmus ist ja das er zeitlich zu einem gewissen Anteil auf Zufall basiert.
Das Problem an meiner Variante ist das Löschen des Array-Elements. Da geht ein Haufen Zeit verloren.
Evt. ginge es mit einer StringList statt einem Array sogar schneller. Muss ich evt. auch mal ausprobieren. Aber jetzt geh ich erstmal arbeiten. 
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 16.04.07 08:05
Was Du benötigst ist eine zufällige Permutation der Zahlen von 1..N.
Also: Array mit Zahlen füllen, per Zufall mischen (nach Fisher-Yates) und dann sind die Zahlen in einer zufälligen Reihenfolge. Dann einfach nacheinander die Zahlen aus dem Array lesen und fertig.
So mischt man ein Array A (0..Count-1) mit Fisher-Yates
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| Procedure ShuffleFisherYates (Var A : Array Of Integer; Count : Cardinal); Var I, T : Cardinal; Begin For I := 0 to Count-1 do begin J := I+random(Count-I); T := A[J]; A[J] := A[I]; A[I] := T; End; End; |
Und so bekommt man dann eindeutige Zufallszahlen (jede Zahl 1..N nur 1x):
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| Var A : Array Of Cardinal; Cnt : Integer;
Procedure MyRandomize (Count : Cardinal); Var I : Cardinal;
Begin Randomize; SetLength (A, Count); For i:=0 to Count - 1 do A[i] := I+1; ShuffleFisherYates (A, Count); Cnt := Low (A); End;
Function MyRandom : Cardinal; Begin if Cnt > High (A) Then Raise Exception.Create ('Alle Zahlen wurden gezogen'); Result := A[Cnt]; Inc (Cnt); End; |
Marc. hat folgendes geschrieben: | Das Thema hatte wir hier schon oft, aber nun gut: |
Stimmt, aber garantiert nicht mit Deiner Variante. Wenn Du nun schon so daher kommst, dann hättest Du die o.g. Variante (oder zumindest die theoretischen Grundlagen, sprich 'zufällige Permutation') erwähnen müssen. Offensichtlich liest Du nur die Fragen, aber nie die Antworten ...
Marc. hat folgendes geschrieben: |
...
im Grunde recht simpel.  |
Nein, sondern trivial. Und im Vergleich zur o.g. Methode seeeeehr langsam. Deine Variante ist vom Aufwand O(n^2), o.g. Methode vom Aufwand O(n), mithin optimal.
_________________ Na denn, dann. Bis dann, denn.
|
|
Narses
      

Beiträge: 10183
Erhaltene Danke: 1256
W10ent
TP3 .. D7pro .. D10.2CE
|
Verfasst: Mo 16.04.07 09:29
Moin!
Dazu gibt´s mittlerweile auch einen FAQ-Beitrag.
cu
Narses
_________________ There are 10 types of people - those who understand binary and those who don´t.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Mo 16.04.07 09:38
Ahoj, Narses.
Hab ich gelesen (und deine Anmerkung bezüglich des 'Miller', der offensichtlich geheiratet hat  , auch).
_________________ Na denn, dann. Bis dann, denn.
|
|
Hiprog 
      
Beiträge: 25
WIN XP Professional(SP2)
Delphi 7 Enterprise
|
Verfasst: Di 17.04.07 02:51
Ich habe so etwas im Prinzip wie Karlsson geschrieben hat gebraucht. Ich brauche auch nicht so wirklich eine Permutation, obwohl die Idee auch nicht schlecht ist. Wie gesagt ich wollte ein Sudoku Programm programmieren (Wie so viele Leute in diesem Forum) aber halt mit einer anderen Variante. Aber ich denke, dass ich es jetzt hinbekommen werde, Vielen Dank an alle, die geholfen haben. Falls es weitere Probleme gibt schreib ich sie weiter hier rein, ich lasse diesen Threat also erstmal offen, bis es fertig ist.
|
|