Sei Ω ein beliebiges Alphabet und w ein Wort über dem Alphabet Ω.
Das Ziel dieses Caches ist es die Anzahl der verstreuten Teilwörter des Wortes
KLUGECACHERGANZGESCHWINDDIEDOSEFIND
zu finden.
Ein verstreutes Teilwort von w ist ein Wort, das durch Löschen
beliebig vieler Buchstaben aus w entsteht.
Die Reihenfolge der übrigen Buchstaben muss jedoch bestehen bleiben.
Zum Beispiel sind cahg (Geocaching) oder Geo (Geocaching) verstreute Teilwörter von Geocaching.
cachio ist aber kein verstreutes Teilwort von Geocaching, da die Reihnfolge der Buchstaben vertauscht wurde.
Wie viele verstreute Teilwörter hat nun das Wort
KLUGECACHERGANZGESCHWINDDIEDOSEFIND
?
A B C D E F G H I J K
Die Zahlen bitte der Reihenfolge nach auf die Striche schreiben. Die Zahl auf dem ersten Strich hat die Codierung A.
Die Koordinaten berechnen sich nun wie folgt:
N:5 0° H F. C (B-A) A
E: 0 0 I° H H. D G E
Viel Spaß beim Rätseln und Grüße aus dem Norden.
Da ich nicht weiss wohin mit dem D-Wert habe ich mal die Mitte gewählt und D3 genommen. --- Am 27.03.14 erhöht auf D5 ---.
In der Dose findet ihr ein etwas anderes Logbuch. A, B und C sind natürlich für die Treppchenplätze reserviert.
Die Cachewartung vor Ort wird von Kogro übernommen.
Und hier kommt noch ein Hinweis, da das Rätsel wohl doch sehr klifflig ist.
Der FTF und der STF sind ohne diesen Hinweis gefunden worden.
Moin Student A na bist du gestern mit den verstreuten Teilwörtern noch weitergekommen?
Moin Student B.
Bis auf, dass meine ganze Wohnung verraucht ist und mein Kopf heute brummt bin ich nicht wirklich weitergekommen und du?
Ne leider auch nicht. Aber Student C hat uns berechnet, wie lange unser bisheriger Algorithmus für dieses Wort brauchen würde. Obwohl wir die Komplexität ja um die Hälfte verringern konnten macht das bei hoch n natürlich nicht wirklich was aus. Ich weiß die Zahl nichtmehr genau, aber bis der Rechner fertig ist, ist die Menschheit vermutlich schon längst ausgestorben.
Ja das habe ich mir schon gedacht. Ich habe unseren Prof nochmal gefragt und er meinte, dass er ein Programm geschrieben hat, was die Anzahl der verstreuten Teilwörter in linearer Zeit berechnen kann.
Denken wir das doch nochmal langsam durch. Also für Wörter ohne doppelte Buchstaben ist das ganze ja Kindergram. Bei unseren bisherigen Überlegungen sind wir ja immer vom Wortende ausgegangen und haben versucht die Doppelten Teilwörter zu berechnen und dann von der Maximalanzahl abzuziehen.
Student D Hey ihr da vorne wartet doch mal.
Natürlich. Wieso versuchen wir es denn nicht mal anders herum. Wir fangen das Wort von VORNE an !
Aber klar! wieso haben wir das denn so kompliziert gemacht. Da wir die Reihenfolge beachten müssen ist das doch sowieso viel logischer. Wenn ein doppelter Buchstabe weiter vorne drankommt sind es ja weniger doppelte Wörter, als wenn der Buchstabe weiter hinten im Wort drankommt.
Also einen Moment mal. Hier habe ich ein Blatt Papier. Wir fangen mit dem ersten Buchstaben an. Wir wissen ja, dass es hierfür 2 verstreute Teilwörter gibt. Der Buchstabe selbst und das leere Wort. Also eben kein Buchstabe. Jetzt gehen wir das Wort einfach Buchstabe für Buchstabe durch. Wenn der Buchstabe noch nie vorgekommen ist, ist es ja klar was wir machen. Aber wenn er schon mal vorgekommen ist?
Natürlich dann müssen wir rausfinden wie viele wirklich neue Teilwörter es gibt.
Aber klar durch die Reihenfolge ist das ja leicht rauszufinden. Ich weiß auch schon wie wir das anstellen können. Dann müssen wir ja nur das ganze Wort durchgehen und am Ende haben wir die richtige Anzahl.
Ach man. Manchmal steht man aber echt auf dem Schlauch. Danke Student C ohne dich wären wir vermutlich nie auf die Idee gekommen. Auf geht's in den Pool64. Lassen wir den PC die Arbeit für uns erledigen.
Und heute Abend stoßen wir dann in der Kneipe an.
Willst du lieber in Kneipe A oder in Kneipe B?
Lass uns man in Kneipe B gehen. Da ist heute Abend eine coole Musikgruppe und außerdem haben die einen kostenlosen Tischkicker.
Okay ich sag den anderen bescheid.