| 06.07.2003, 22:04 |
Steve_FL |
Auf diesen Beitrag antworten » |
[Tipp]: Ein wenig Kombinatorik mit einer neuen Sprache
So. Hier kann man über meinen Tipp diskutieren.
Ich hab zwar schon einen Treff mit dieser Aufgabe im Stochastiktreff, aber ich denke Thomas oder Jama können den sicher hier reinkopieren 
mfg |
| 06.07.2003, 22:30 |
Thomas |
Auf diesen Beitrag antworten » |
| Zitat: |
Also:
Ein Land hat eine Sprache, deren Alphabet aus n Buchstaben besteht.
Die Bewohner von diesem Land bilden nun Wörter mit diesen Buchstaben. Jede Kombination von Buchstaben gilt als ein Wort, solange keine zwei gleichen Buchstaben, zwei andere gleiche Buchstaben einschliessen. Was dazwischen steht ist egal.
also sagen wir:
ABERKOL ist zulässig
ABBA ist unzulässig.
ALELA ist unzulässig, da zwei A wei L einschliessen.
BUBBAB wäre auch unzulässig, da zwei B zwei andere B einschliessen.
Aufgaben:
a) Wie lange ist das längste zulässige Wort?
b) Wieviele Wörter dieser Länge gibt es?
********************************************
Lösung:
a) Da keine zwei gleichen Buchstaben zwei gleiche Buchstaben einschliessen dürfen, wissen wir, dass kein Buchstabe 4x in einem Wort enthalten sein darf.
Das bedeutet, man kann jeden Buchstaben maximal 3* verwenden. Zum Beispiel AAABBBCCCDDDEEE...
=> Das längste Wort besteht aus 3n Buchstaben.
b) Wieviele Wörter kann man so bilden?
Da muss man sich zuerst veranschaulichen, wie diese Wörter gebildet werden. Gehn wir mal von der einfachsten Sorte aus:
AAABBBCCC...
Jetzt versuchen wir mal ein paar Buchstaben zu tauschen. Wo darf das A hin? Nicht weiter, als hinter das erste B. Das B darf nicht weiter nach vorne, als vor das letzte A und nicht weiter nach hinten, als das erste C.
Das bedeutet: AABABCBCC ist noch gültig.
Unterteilen wir das mal in Blöcke:
AAA BBB CCC
man kann immer nur die Buchstaben am Rand eines Blocks tauschen. Das bedeutet, es gibt für jeden Zwischenraum 2 Möglichkeiten, wie die Buchstaben, die an ihn angrenzen sein können.
AAA (Zwischenraum) BBB -- bei diesem Zwischenraum ist die Folge AB die zweite Möglichkeit ist BA
Ich sage jetzt Zwischenraum, weil ich die Blöcke auseinandergenommen habe. Im Prinzip ists ja ein Wort, das zusammenbleibt.
Wieviele Zwischenräume gibt es? natürlich zwischen jedem Block einen. Und es gibt für jeden Buchstaben einen Block. Also n Blöcke, daraus folgt => n-1 Zwischenräume.
Jeder Zwischenraum hat, wie gesagt zwei Möglichkeiten an den Seiten. Das bedeutet insgesamt kann man mit n Blöcken die fest geordnet sind 2^(n-1) verschiedene Kombinationen bilden.
ABER: Man kann die Blöcke noch beliebig austauschen.
Und jetzt muss man wissen wie. n Blöcke können auf n! Möglichkeiten geordnet werden, und bei jeder Ordnung gibts wieder 2^(n-1) Möglichkeiten die Zwischenräume zu belegen.
Jetzt haben wir alle Fälle, die möglich sind gehabt. Fassen wir zur Lösung zusammen:
Es gibt (n!)*(2^(n-1)) Möglichkeiten, das längste Wort zu bilden.
|
so hier nochmal reingepostet, den link werde ich gleich aktualisieren bei den tipps 
|
| 06.07.2003, 22:32 |
jama |
Auf diesen Beitrag antworten » |
zu spät, hab ich shcon gemacht :P |
| 06.07.2003, 22:34 |
Thomas |
Auf diesen Beitrag antworten » |
menno, immer bist du schneller
|
| 06.07.2003, 22:38 |
jama |
Auf diesen Beitrag antworten » |
um nicht zu spammen ... schöner eintrag in die tipps & tricks kategorie
|
| 31.08.2003, 18:22 |
Steve_FL |
Auf diesen Beitrag antworten » |
| Zitat: |
| um nicht zu spammen ... schöner eintrag in die tipps & tricks kategorie |
danke
aber könnt irgendwie doch einen leichten Hauch Spam haben...ist aber egal.
Mich würde mal interessieren, wieviele Leute diesen Tipp schon angeschaut haben.
Könnt ihr da auch Zähler einbauen, und eine Statistik erstellen, welches der beliebteste Tipp ist? Wär sicher noch interessant.
Ich schreib das mal schnell ins Verbesserungen-Board
mfg |
| 01.10.2004, 17:42 |
Que |
Auf diesen Beitrag antworten » |
BULLSHIT
AAABABBBCCC... wäre laut definiton ein zulässiges wort
und da sind 4 n drin!!! |
| 01.10.2004, 18:23 |
juergen |
Auf diesen Beitrag antworten » |
| Zitat: |
Original von Que
BULLSHIT
AAABABBBCCC... wäre laut definiton ein zulässiges wort
und da sind 4 n drin!!! |
Das wäre wohl nicht zulässig,
da sind doch zwei B von zwei B eingeschlossen
AAABABBBCCC... |
| 01.10.2004, 18:25 |
Steve_FL |
Auf diesen Beitrag antworten » |
stimmt. Da wären 4 A drin.
Das Problem ist aber, dass das erste und das letzte A, die beiden in der Mitte einschliessen, was bedeutet, dass das Wort unzulässig ist.
mfg |
Wichtig: