spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ja ich hab eben die const char* durch ConstBoundPointer<char> ersetzt. Das verhält sich wie ein Pointer, nur dass es bei Dereferenzierung (operator[], operator*, operator->) ob sich das ganze noch in dem Limit befindet, das am Anfang übergeben wird. Da ich die Klasse jedoch vor ca. 2 Jahren erstellt habe, und bir nicht 100% sicher bin, obs wirklich 100% richtig ist, hab ich ja geschrieben, man sollte das ganze mit nem Debugger testen... (wenn mir in der Infovorlesung immer noch langweilig ist, test ich das mal durch)

@TGGC:
palindrome_tggc("123123123123123123123123123123123123123123213")
-> endlosloop, habs 1:1 kopiert, darum musste ich es aus dem Test rausnehmen,

TGGC's Code beinhaltet keine Endlosschleife.

Die einzige enthaltene Schleife läuft bis NormalerIQ < TGGCsIQ, wobei in jedem Schleifendurchlauf NormalerIQ inkrementiert wird und TGGCsIQ unverändert bleibt. Die Schleife terminiert.

Da die Funktion im Anschluss an die Rekursion zurückkehrt, erzeugt jeder Aufruf von TGGCsSuperGeheimeFunktion keinen oder 2 rekursive Aufrufe.
Und da vor den rekursiven Aufrufen TGGCsIQ dekrementiert wird ist sichergestellt, dass, sobald TGGCsIQ 0 erreicht hat, keine weiteren rekursiven Aufrufe erfolgen. Die Rekursion terminiert.

Das Problem ist die exponentielle Worst-Case-Komplexität:

Der Worst-Case tritt dann ein, wenn der zu prüfende string kein Palindrom enthält. Dann werden 2^Länge_des_strings rekrusive Aufrufe getätigt.
Für das oben genannte Beispiel sind das 2^45 ~ 35 Billionen (Zahl mit zwölf Nullen !) Aufrufe von TGGCsSuperGeheimeFunktion.

Nichts desto trotz ist die Funktion - zumindest meiner bescheidenen Meinung nach - korrekt. Den experimentellen Beleg dafür überlasse ich anderen

Selbstverständlich. Aber ich habe auch nur darzulegen versucht, dass die Funktion terminiert, nicht, dass sie das korrekte Ergebnis liefert. Aber wenn man den Ansatz nachvollzieht, sollte man zu diesem Schluss kommen.

Wir akzeptieren die verbliebenen Lösungen aber weiterhin als korrekt, bis das Gegenteil bewiesen wurde, oder ?

PS: wie komme ich eigentlich zu dem Titel Contest-Gewinner ?! Ehre, wem Ehre gebührt, und das ist David selbst. Ich will mich ja nicht mit fremden Federn schmücken.

Zitat von »"David Scherfgen"«

Armer Helmut ... naja, der nächste Contest kommt bestimmt!

Tjo, wie sich wohl die Gewinner von der Tour de France fühlen weiß ich wohl jetzt

Ne, aber schon irgendwo ärgerlich, es hätte keine Minute gekostet, den Algo an nem Beispiel nachzuvollziehen, dann wär der Fehler sofort aufgeflogen.

Aber was soll's, bis zum nächsten Contest