Hello, Guest the thread was called4.6k times and contains 44 replays

last post from Womak at the

Zufallszahlen

  • Hallo!


    Ich möchte gerne Zahlen, z.B. von 1 bis 100, in zufälliger Reihenfolge darstellen.


    10 X = RND(-TI)
    20 X = INT(100*RND(1))+1


    Wenn ich jetzt Zeile 20 100mal durchlaufen lasse erhalte ich zwar 100 Zufallszahlen, aber es kommen Zahlen doppelt und dreifach vor, andere dagegen garnicht.
    Wie erreiche ich es, dass alle Zahlen von 1 bis 100 in zufälliger Reihenfolge dargestellt werden können?
    Daaanke!


    Ciao maibus

  • Du müßtes die Zahlen in Variabeln zwischenspeichern und jeweils abfragen, ob die schonmal dran war. Wenn Sie dran war wird eine neue Zufallszahl ermittelt. Der Durchlauf ist erst dann beendet wenn alle 100 gezogen worden sind.


    Ich weiß nur nicht, ob beim C64Basic soviele freie Variablen möglich sind.

  • kann mich erinnern im ganz alten Forum eine ähnliche Frage beantwortet zu haben, da gings darum, per Zufallsgenerrator ein virtuelles Kartenspiel zu mischen, dabei darf ja jede Karte (=Zahl) auch nur einmal vorkommen. Und ja, du mußt dabei natürlich die Zufallszahlen erzeugen, vergleichen, ob sie schon mal dran war und dann ablegen, am besten in eienem dimensionierten Feld, aus dem Stehgreif würde ich das so machen:


    10 dim a(100):z=0
    20 x=int(100*rnd(1))+1:flag=0
    30 for i=0 to z:if a(i)=x then flag=1
    40 next
    50 if flag=0then z=z+1:a(z)=x:if z<100then20
    60 goto20
    70 fori=0to99:printa(i):next


    ungetestet als Anregung...
    P.S: So etwas in BASIC ist natürlich richtig ekelhaft laaaaaaaaaangsam vor allem mit so einer Vorschlaghammermethode, es gibt bestimmt ausgeklügeltere/ optimiertere Algorithem für so etwas, viel Spass beim Knobeln

  • Hallo


    Quote

    Der Durchlauf ist erst dann beendet wenn alle 100 gezogen worden sind.


    Das funktioniert zwar, aber dürfte bei den letzten Zahlen sehr lange dauern, da für die 99. Zahl nur noch 2 Möglichkeiten vorhanden sind und für die 100. Zahl nur noch eine.
    Deshal werden gegen Ende der Erzeugung der Zufallszahlen sehr viele Durchläufe benötigt.



    Quote

    Ich weiß nur nicht, ob beim C64Basic soviele freie Variablen möglich sind.


    Das ist möglich, wenn Du ein Array verwendest.
    Die größe des Arrays ist nur durch den freien Basic-Speicher begrenzt.
    Eine Fließkommazahl belegt 5 Byte in einem Array und eine Integer 2 Byte in einem Array.


    Die Platzersparnis in Arrays ist meiner Meinung nach der einzige sinnvolle Einsatz von Intger in Basic.

  • Ich würde das ungefähr so angehen: ein Array mit 100 Zufallszahlen füllen. Die Reihenfolge 1-100 entspricht später den gezogenen Zahlen. Dann die Werte der Zufallszahlen auf- oder absteigend sortieren. Die Nummern 1-100 sind dann zufällig gemischt und kommen nur einmal vor.


    Die Kunst besteht dann eigentlich nur darin, das Sortieren möglichst schnell zu erledigen. Ich würde im Array eine Flag-Variable für jede Zufallszahl vorsehen, das anzeigt, wenn eine Zahl schon raussortiert wurde, und die gezogene Zahlen (=urprüngliche Reihenfolge im Array) in einem seperaten Array ablegen.

  • das mit dem überprüfen ist hoffnungslos. die wahrscheinlichkeit nimmt mit den schon gezogenen werten immer mehr ab, und das durchsuchen steigt linear an. wenn man also schon 75 werte hat, dann ist die wahrscheinlichkeit 25% prozent, das die zufallszahl eine noch nicht bekannte ist. man muss also im schnitt 4 zahlen ziehen um eine neue zahl zu bekommen... für jeden der vier ziehversuche müssen aber alle 75 schon gezogenen zahlen durchsucht werden.


    einfachere lösung: einen array linear mit den werten 1 bis 100 füllen. diese werte dann zufällig vertauschen.

  • @Fröhn: jupp, genau so hatte Hannenz die Routine geschrieben. Warum er jetzt was anderes gemacht hat verstehe ich nicht so ganz...


    Ich poste hier mal die "alte" Hannenz-Misch-Routine :)


    Code
    1. 1 for a=1 to 100: k(a)=a: next
    2. 2 for a=1 to 30:
    3. 3 x1=int(rnd(1)*100)+1
    4. 4 x2=int(rnd(1)*100)+1
    5. 5 a1=k(x1): a2=k(x2)
    6. 6 k(x1)=a2: k(x2)=a1: next



    Variablen eventuell anpassen. Wie Hannenz ja schon sagte war es für ein Kartenspie (Wer sich die mal ansehen will, kann beim Wusel mal im Downloadbereich schauen.) und deshalb das K wie Karte. ;)


    In Zeile 20 kannst du den Wert ruhig mal verändern, damit die Zufallszahlen auch besser "gemischt" werden.


  • besser ist es, wenn x1 einfach von 1 bis 100 durchzählt und nur x2 zufällig ist. auf diese weise ist garantiert, dass jedes element x mal angefasst wird und man kann die zweite for-schleife um einiges kleiner machen.

  • zum "kartenmischen" nimmt man am besten ein "linked-list"-system her (verkettete listen):


    mal sehn ob ich das erklären kann:


    sagen wir mal wir wollen die geordnete folge "abcd" mischen. dazu muss die liste mit sich selbst
    verkettet werden:


    p=position
    w=wert
    l=link zur position des nächsten elements


    P:1234
    w:abcd
    l:2341


    jetzt läuft man einfach von links nach rechts durch die liste. dazu errechnen wir uns einen "schritt"-wert
    per zufall...sagen wir mal 3.
    nach 3 schritten finden wir ein "c" das mit "4" verknüpft ist.
    diesen wert nehmen wir aus der liste raus, indem wir das vorherige element mit dem nachfolgenden
    verknüpfen und das "c" in unser zielarray schreiben. das ganze sieht nach dem ersten schritt so aus:


    #schritt1:
    quelle:
    P:1234
    w:abcd
    l:24*1


    ziel:
    c


    jetzt macht man das so lange bis das quellarray "leer" ist:


    #schritt2:
    quelle:
    P:1234
    w:abcd
    l:4**1


    ziel:
    cb


    #schritt3:
    quelle:
    P:1234
    w:abcd
    l:***4


    ziel:
    cba


    #schritt4:
    quelle:
    P:1234
    w:abcd
    l:****


    ziel:
    cbad



    fertig...gemischt....wenn man eine andere schrittweite nimmt, kommen natürlich andere
    "mischungen" raus. die schrittweite kann auch 100000 sein, da die liste ja "rund" ist
    (letztes element verlinkt wieder auf das erste)


    um noch wilder zu mischen kann man einfach das zielarray wieder in das quellarray
    schreiben und mit einer neuen schrittweite nochmal mischen.



    mischt wie sau und ist auch recht flott.
    wenn ihr das ganze nicht verstehen solltet (bei meiner erklärerei wäre das kein wunder),
    kann ich's auch man in basic bauen....falls interesse besteht.



    gemischte grüsse,
    tecM0

  • @ tecM0


    Habs zwar einigermaßen verstanden (glaube ich zumindest), könnte es aber nicht in Basic umsetzen. Wäre sehr lieb von dir, wenn du das mal in Basic bauen könntest!
    Thanks!!!


    Ciao maibus

  • @ hannenz


    Habe deine Anregung mit einigen kleinen Änderungen übernommen.
    Allerdings ist sie wirklich ziemlich langsam. Bei nur 100 Zahlen dauert es schon einige Minuten. Dennoch werde ich sie erstmal verwenden (müssen). Danke dir!!!


    Ciao maibus

  • holla,


    ich habe gerade versucht es in VICE zu bauen....bis auf einen nervenzusammenbruch
    habe ich nix hinbekommen ;)
    was für eine tastaturbelegung...arglll


    versuchs mal zu basteln...das system sollte 100 zahlen in ein paar sekunden
    mischen....ohne viele FOR schleifen. einfach den zähler addieren und MODULO
    der anzahl von elementen...dann loopt man immer wieder von vorne durch.



    T.

  • Hier nochmal mein Vorschlag in Basic:


    Code
    1. 1 TI$="000000"
    2. 10 DIM R(100),N(100)
    3. 20 I=RND(-TI)
    4. 30 FOR I=1 TO 100:R(I)=RND(1):NEXT
    5. 40 FOR J=1 TO 100:V=1
    6. 50 FOR I=1 TO 100:IF R(I)<V THEN V=R(I):N=I
    7. 60 NEXT:N(J)=N:R(N)=2:PRINT N:NEXT J
    8. 100 PRINT TI$


    In Zeile 30 werden 100 Zufallszahlen angelegt, in 40-60 sortiert, die zufälligen 1-100-Nummern liegen am Schluß in N(1...100).


    Berauschend schnell ist er auch nicht (etwas mehr als eine Minute). Bin gespannt, wie schnell man das mit anderen Methoden in Basic hinkriegt.

  • die linked list methode von tecmo hört sich sehr interessant an... werde auch mal versuchen, das umzusetzen...
    von sortieralgorithmen liest man ja überall, aber mischalgorithmen, das ist mal richtig interessant

  • Also wenn ich diese Listenmethode richtig verstanden habe, dann ginge das in Basic UNGEFÄHR so:


  • Hätte hier auch einen selbstgeschriebenen Misch-Vorschlag.


    Code
    1. 10 A=100:B=1:DIM A(A):DIM B(A)
    2. 20 FOR I=1 TO A:A(I)=I:NEXT I
    3. 30 R=INT(A*RND(1))+1
    4. 40 B(B)=A(R):PRINT B(B);
    5. 50 FOR I=R TO A-1:A(I)=A(I+1):NEXT I
    6. 60 A=A-1:B=B+1
    7. 70 IF A>0 GOTO 30


    Und das geht so:
    Es werden zwei Felder mit je 100 Elementen angelegt (Zeile 10). Das erste Feld wird mit den Zahlen 1 - 100 gefüllt (Zeile 20). Dann wird ein zufälliges Element R rausgepickt (Zeile 30) und der Inhalt in das erste Element des zweiten Feldes kopiert (Zeile 40). Die Elemente nach R im ersten Feld werden alle um eins nach oben gerückt (Zeile 50). Dann wird dafür gesorgt, daß im nächsten Durchgang nur noch 99 Elemente berücksichtigt werden und der nächste Wert ins zweite Element des zweiten Feldes kopiert wird (Zeile 60). Und dann geht's von vorne los, bis im ersten Feld keine Elemente mehr da sind (Zeile 70).


    Den PRINT-Befehl in Zeile 40 kann man an dieser Stelle weglassen; der ist nur da, damit man beim Ausprobieren auch sieht, wie es klappt.


    Bei dieser Methode ist es nicht nötig, zu vergleichen, ob eine Zahl schon dran war oder so'n Gedöns. Vor allem wird es von Durchgang zu Durchgang immer schneller. Das ganze dauert auf dem C64 weniger als 30 Sekunden.


    Eine weitere Möglichkeit wäre, ein Assembler-Mischprogramm mit der "READ/DATA/SYS"-Methode als Basic-Routine zu schreiben. Das Mischen geht dann auf einen Zack.


    Übrigens maibus... Immer wenn ich im Augenwinkel deinen Avatar sehe, denke ich einen Moment lang, es wäre meiner. :D


    Dr. Poke

  • Ich muss mal diesen Uralten Thread wieder rausholen, da ich gerade an einer ähnlichen Routine arbeite.
    MEINE braucht aber nur zwischen ca. 12 und 7 Sekunden um ein Deck durchzumischen!!!
    Eigentlich bin ich hier gelandet, weil ich es noch verschnellern wollte ;-)
    Meine Vorgehensweise:
    - Ich Dimensioniere/erzeuge ein Array bei dem (ja automatisch) an allen Orten der Wert "0" steht.
    - Ich erzeuge mittels einer For Next den WERT, also bei mir gerade die Zahlen von 2-99, ich spare mir somit das Vergleichen schon vorhandener WERTE.
    - dann durch Zufallszahl den ORT im Array!
    - dann prüfe ich ob an diesem ORT ein "." also eine "0" steht, wenn ja wird der WERT geschrieben und es geht mit dem nexten WERT weiter,
    wenn nein wird ein neuer ORT generiert und auf "0" geprüft...


    Hier der "Grundcode":


    Code
    1. A=98:B=1:C=2:D=99:DIMK(99)
    2. FORN=CTOD
    3. M=A*RND(B)+C:IFK(M)=.THENK(M)=N:NEXT:END
    4. GOTO3


    Ich habe inzwischen noch "übliche Beschleunigungen" mit eingebaut, wie Bildschirmabschalten und so, und eine Zeitmessung mit TI$"000000" in Sekunden.
    siehe Foto:


    Das für die Vermessung verwendete Prog ist hier:
    zufall 3.prg

  • Eigentlich bin ich hier gelandet, weil ich es noch verschnellern wollte

    Siehe Beitrag 6:

    das mit dem überprüfen ist hoffnungslos.
    [...]
    einfachere lösung: einen array linear mit den werten 1 bis 100 füllen. diese werte dann zufällig vertauschen.

    ...oder auch hier, Beiträge 51 bis 55.


    (das angehängte Programm nicht ansehen, wenn Du selber knobeln willst)