 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Coxi
Anmeldungsdatum: 06.08.2007
Beiträge: 2
|
 Verfasst am: 06.08.2007, 11:05 Titel: Zuffalsausgabe |
 |
|
Hallo erstmal,
Ich hab ein Problem.
Ich will ein Programm schreiben, wo man eine Anzahl von Personen und dann deren namen eingeben kann.
Dann sollen sie in Zufälliger reihenfolge ausgegeben werden.
Mein bisheriges Programm:
| Code: |
CLS
RANDOMIZE TIMER
PRINT "Wie viele Namen";
INPUT a
DIM b$(a)
FOR i = 1 TO a
PRINT "Name "; i;
INPUT b$(i)
NEXT i
FOR c = 1 TO a
d = INT(RND * a) +1
PRINT c; ". Name:"; b$(d)
NEXT c
|
Mein Problem: Es kann sein das Namen doppelt vorkommen, und das will ich vermeiden!!!
Der letzte absatz muss irgentwie geändert werden. ich weis aber nicht wie.
könnt ihr mir helfen?
Coxi |
|
| Nach oben |
|
 |
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 06.08.2007, 11:22 Titel: |
|
|
Mein schon häufig eingesetzter Zufallsgenerator sieht so aus:
| Code: | FOR i=1 TO a
FOR k=i TO a
IF INT(RND*(a-i+1)) = 0 THEN
SWAP b$(i), b$(k)
END IF
NEXT
NEXT |
Mischt die Namen bunt durcheinander.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 06.08.2007, 13:43 Titel: |
|
|
Warum so kompliziert?
| Code: | FOR i=1 TO 100
x = INT(RND*a)+1
y = INT(RND*a)+1
SWAP b$(x), b$(y)
NEXT |
Hier wird ein Array b$ der Länge a auch gemischt. Je größer die FOR-Schleife, desto mehr Vertauschungen gibts, desto gemischter wirds.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 06.08.2007, 13:54 Titel: |
|
|
Deswegen so kompliziert, weil bei mir für jeden Namen die Wahrscheinlichkeit für jeden Platz gleich hoch ist. Also eine echte Zufallsverteilung (natürlich nur, wenn man RND als echte Zufallsgröße bezeichnen kann).
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Coxi
Anmeldungsdatum: 06.08.2007
Beiträge: 2
|
| Verfasst am: 06.08.2007, 14:41 Titel: |
|
|
| was heißt SWAP ??? |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 06.08.2007, 15:02 Titel: |
|
|
Befehlsreferenz? 
SWAP vertauscht den Wert zweier Variablen.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 06.08.2007, 15:16 Titel: |
|
|
Vielleicht bin ich zu blöd, aber irgendwie ist deine Routine komisch.
| nemored Schleifenausgabe hat Folgendes geschrieben: |
a = 4
i, k, a-i+1
1, 1, 4
1, 2, 4
1, 3, 4
1, 4, 4
2, 2, 3
2, 3, 3
2, 4, 3
3, 3, 2
3, 4, 2
4, 4, 1
|
Hab deine Schleife mal mit a = 4 laufen lassen. Man sieht, dass jedes verschiedene Paar von (i, k) einmal vorkommt (also (1,1), (1,2)..... )
ganz rechts steht dann aber immer die Wahrscheinlichkeit, dass etwas getauscht wird. (Je größer die Zahl, desto unwahrscheinlicher der Tausch.)
Bei meiner Methode gibts nichts ungerechtes auszusetzen. Es wird immer ein Paar zusammengewürfelt und vertauscht. Das kann bedeuten, das (4, 3) 3 mal getauscht wird, (2,1) aber niemals. Das ist aber wahrscheinlichkeitstechnisch immer noch gleichverteilt alles.
EDIT:
Und hier der Beweis (leider Blitzbasic):
| Code: | Graphics 800, 600, 0, 2
SeedRnd MilliSecs()
a = 20
Dim R(a)
Dim E(a)
For i = 0 To a-1: E(i) = 0: Next
For x = 1 To 1000
For i = 0 To a - 1: R(i) = i: Next
For i=0 To a-1
For k=i To a - 1
If Rand(0, a-1) = 0 Then
t = R(i)
R(i) = R(k)
R(k) = t
End If
Next
Next
For i = 0 To a-1: E(i) = E(i) + R(i): Next
Next
Print "Durschnittliche Verteilung von nemored bei 1000 Durchläufen und Arraygröße von " + Str(a)
For i = 0 To a-1: E(i) = E(i) / 1000:Print E(i): Next
For i = 0 To a-1: E(i) = 0: Next
For x = 1 To 1000
For i = 0 To a - 1: R(i) = i: Next
For i=1 To 100
p = Rand(0, a-1)
q = Rand(0, a-1)
t = R(p)
R(p) = R(q)
R(q) = t
Next
For i = 0 To a-1: E(i) = E(i) + R(i): Next
Next
Print "Durschnittliche Verteilung von SpionAtom bei 1000 Durchläufen und Arraygröße von " + Str(a)
For i = 0 To a-1: E(i) = E(i) / 1000:Print E(i): Next
WaitKey |
Mein Array hat überall den Durchschnittswert von a/2, bei nemored sieht es etwas anders aus.
(Ja ich weiß, ich hab zuviel Zeit, ich hab schließlich Semesterferien)
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
csde_rats
Anmeldungsdatum: 07.01.2007
Beiträge: 2292
Wohnort: Zwischen Sessel und Tastatur
|
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 06.08.2007, 15:42 Titel: |
|
|
| Zitat: | | Vielleicht bin ich zu blöd, aber irgendwie ist deine Routine komisch. |
Vielleicht liegt es auch daran, dass sich ein Fehler eingeschlichen hat 
| Code: | FOR i=1 TO a
FOR k=i+1 TO a
IF INT(RND*(k-i+1)) = 0 THEN
SWAP b$(i), b$(k)
END IF
NEXT
NEXT |
Zur Erklärung (Beispiel a=4):
Zuerst wird geschaut, welcher Wert an erster Stelle stehen soll.
Wahrscheinlichkeit, dass 1 wird mit 2 getauscht wird: 1/2
Wahrscheinlichkeit, dass 1 wird mit 3 getauscht wird: 1/3
Wahrscheinlichkeit, dass 1 wird mit 4 getauscht wird: 1/4
Wert 1 bleibt damit mit einer Wahrscheinlichkeit von 1/2*2/3*3/4 = 1/4 an seiner Stelle.
Wert 2 rutscht mit einer Wahrscheinlichkeit von 1/2*2/3*3/4 auf Stelle 1.
Wert 3 rutscht mit einer Wahrscheinlichkeit von 1/3*3/4 auf Stelle 1.
Wert 4 schließlich rutscht mit einer Wahrscheinlichkeit von 1/4 auf Stelle 1.
(Einfacher und deutlicher wäre es mit einem Baumdiagramm ...)
Danach ist also für jeden Wert die Wahrscheinlichkeit 1/4, dass er auf Platz 1 liegt.
Nun geht das ganze wieder von vorn los für Platz 2, selber Algorithmus; die Wahrscheinlichkeit, auf Platz 2 zu landen, liegt für jeden Wert bei 1/3.
Usw.
Bei deiner Methode ist, wie du schon sagst, die Mischqualität abhängig davon, wie lange gemischt wird.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 06.08.2007, 16:26 Titel: |
|
|
| Code: | | IF INT(RND*(k-i+1)) = 0 THEN |
Heißt ich muss nur diese Zeile ersetzen. Wenn ich das mache, ist für die erste Stelle der Durchschnittswert 0, für die zweite 1, ...., für die letzte 19. Ziemlich ungeschmischt
(Bei mir sind die Zahlen von 0..19, nicht von 1..20)
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 06.08.2007, 17:42 Titel: |
|
|
Was für einen Durschnittswert meinst du? Hast du auch berüchsichtigt, dass meine Einzelwahrscheinlichkeiten nicht gleich sind?
Damit nicht irgend jemand glaubt, ich hätte was anderes zu tun (  ), habe ich das ganze mal aufgeschlüsselt. Wieder nur mit 4 Werten, weil die Aufschlüsselung sonst ziemlich lange wird
W. steht natürlich für Wahrscheinlichkeit.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 06.08.2007, 18:50 Titel: |
|
|
Deine Tabelle ist ja rieeesig. Ich weiß noch nicht, wo dein Fehler ist, aber irgendwas stimmt hier nicht.
Mein Programm mischt nach deiner (und nach meiner) Methode. Und schreibt das gemsichte Array A in ein Speicherarray E.
Wenn A jetzt (3, 2, 1, 4) ist, wird in E (3, 2, 1, 4) gespeichert
Das ganze mach ich aber 1000 male.
Wenn als nächstes A (1, 3, 2, 4) ist, wird zu E das Array A dazuaddiert
E (3+1, 2+3, 1+2, 4+4) = (4, 5, 3,  . Am Ende der 1000 Durchläufe teile ich die Werte, die in E drinstehen durch 1000 und erhalte jeweils den Durchnittswert. Der müsste bei A/2 (in unserem Falle 2) liegen, liegts bei dir aber irgendwie nicht.
(Hoffentlich ist mein Programm jetzt nicht fehlerhaft  )
EDIT
Ok mein Programm war fehlerhaft
Deine Mischmethode funktioniert auch. Laufzeittechnisch bin ich aber etwas besser . Ist jetzt nur ein Erfahrungswert, aber wenn ich die Schleife 3*Arraylänge durchlaufen lasse, ists gut gemischt.
Nochmal sorry, dass ich an dir gezweifelt habe, aber diese Langeweile bringt mich um.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
