Gleichverteiltes Zufallswort < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:45 Do 08.11.2007 | | Autor: | Wimme |
| Aufgabe | Es soll ein 4stelliges Wort aus den Zeichen A,B,C,D,E,F,G,H generiert werden. Dabei soll jedes Zeichen nur einmal vorkommen. Jedes Wort muss mit der gleichen Wahrscheinlichkeit vorkommen können.
Die Methode Zufall.zufallszeichen(x) (generiert zufälliges, gleichverteiltes Zeichen zwischen A und x) darf dafür höchstens 4 mal benutzt werden! |
Hi!
Tja, oben genannter Teil des gewünschten Programms bereitet mir Probleme :(
Dürfte man die Methode mehr als viermal benutzen, könnte ich das Alphabet ja anfangen in Intervalle zu unterteilen, aber das geht ja so nicht.
Ich kann auch nicht doppelte Zeichen nachträglich anpassen (mit zeichen+1 oder sowas), da doch sonst die Gleichverteilung kaputt gehen würde.
Das ganze ist übrigens Java im Anfangsstadium (andere Methoden dürfen nicht benutzt werden).
Kann mir jemand unter die Arme greifen?
Dankeschön!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:08 Do 08.11.2007 | | Autor: | AndiL |
Damit die Bedingung der Gleichwarscheinlichkeit erfüllt bleibt, mußt du erst einen Buchstaben aus den 8 'ziehen', den zweiten aus den 7 verbliebenen, Nr.3 aus den restestichen 6 und Nr. 4 aus den restlichen 5 Buchstaben.
Dass die Methode Zufall.zufallszeichen(x) Buchstaben 'auswürfelt' finde ich zur veranschaulichung etwas ungünstig, stell es dir mit Zahlen vor.
ich definiere mir das mal so Zufall.zufallszahl(7) [<-soll von 0 bis 7 würfeln]
entspricht also Zufall.zufallszeichen(H)
Erster Buchstabe:
Zufall.zufallszahl(7)
Sagen wir beispielsweise ich bekomme eine 3 (also der vierte buchstabe = D)
Zweiter Buchstabe:
Mir verbleiben dann noch ABCEFGH
Zufall.zufallszahl(6)
Wenn ich nun wieder eine 3 bekomme ist das diesesmal der Buchstabe E.
Und keiner wird daran zweifeln, dass diese 7 Buchstaben alle gleichverteilt sind.
Aber genau an dieser Stelle ist das mit dem Buchstaben würfeln verwirrend, weil es einem so vorkommt, als verschiebe man das D zum E. Da ich aber mit der Buchstabenfunktion nur noch um eins weniger würfle (bis G), bleibt die Gleichwarscheinlichkeit erhalten. Wichtig dafür ist, dass ich nicht gleichzeitig ein E würfeln kann und alternativ ein D das ich zum E verschiebe (weil es dann häufiger auftreten würde als die übrigen Buchstaben). Sprich, man muß bei der Buchstabenfunktion alle Ergebnisse ab dem D, das ich schon hatte, um eins nach hinten verschieben (sonst käme ich mit Zufall.zufallszeichen(G) auch nicht bis zum H).
Alternativ kannst du auch die Buchstaben alle stehen lassen und nur die bereits weggefallennen Buchstaben ersetzen. Also in diesem Beispiel wenn du ein D würfelst, was ja schon da war, ist es dann ein H, welches du mit Zufall.zufallszeichen(G) sonst nicht bekommst.
Für die restlichen Buchstaben läuft es dann analog weiter.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:14 Do 08.11.2007 | | Autor: | Wimme |
vom Ansatz her klingt das sehr gut :)
Aber ich habe Probleme mit der Umsetzung und verstehe auch nicht, warum D beim zweiten mal H wird. Müsste es nicht E werden?
Wenn ich einen Buchstaben bereits hatte (zB D) und alle ab D eins nach hinten verschiebe ist alles gut. Doch beim nächsten Schritt (nehmen wir an diesmal wurde ein F gezogen) kriege ich das F so nicht aus der Menge raus, oder? D wird wieder zu E, E wird zu F und F zu G. Damit ist das H draußen und das F fälschlicherweise noch drinnen.
Irgendwie müsste ich es dann hinbekommen, dass die Buchstaben auf den nächst möglichen Buchstaben dahinter projiziert werden, oder?
|
|
|
| |
|
Hallo,
> vom Ansatz her klingt das sehr gut :)
Das finde ich auch.
>Aber ich habe Probleme mit der Umsetzung und verstehe auch nicht, warum D beim zweiten mal H wird. Müsste es nicht E werden? ...
Gemeint waren zwei verschiedene Methoden:
1. Sobald z.B. D aus ABCDEFGH ausgelost wurde, entsteht eine Lücke ABC_EFGH, die wir füllen, indem wir einfach die Buchstaben zusammenrücken: ABCEFGH.
2. Alternativ schließen wir die Lücke ABC_EFGH, indem wir den letzten noch gültigen Buchstaben in diese Lücke stopfen: ABCHEFG. Da uns die Reihenfolge nichts bedeutet, weil sie die Wahrscheinlichkeiten nicht verfälscht, können wir es so machen.
> Irgendwie müsste ich es dann hinbekommen, dass die Buchstaben auf den nächst möglichen Buchstaben dahinter projiziert werden, oder?
Das könnte man mit einer while-Schleife bewerkstelligen:
while (aktuelle zahl schon weg) erhöhe aktuelle zahl;
Oder man erstellt sich immer ein aktuelles Alphabet, indem man jede entstehende Lücke schließt (s. 1. Methode)
Einfacher finde ich aber den 2. Vorschlag, da man mit einem Schritt die Lücke stopft, wofür man bei der 1. Methode ggf. mehrere Schritte bräuchte.
Gruß
Martin
|
|
|
|
