Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

#02: "Palindrom", K.d.C., 20.01.2008

Werbeanzeige

neido

Treue Seele

Beiträge: 225

Wohnort: Wien

  • Private Nachricht senden

131

24.01.2008, 18:46

Mist, jetzt ist meine Lösung also doch falsch.
Aber ich kann beim besten Willen den Fehler nicht finden, es wird doch vorher die Länge des Strings extra geprüft! :? Und was bedeutet "BoundPointer Exception: access violates left boundary" genau?

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

132

24.01.2008, 19:00

Ich habe den Test-Code aktualisiert.
Da kannst du den Fehler nachvollziehen.
Es bedeutet, dass du nach links aus dem String heraus liest, also auf den Speicher vor dem ersten Zeichen zugreifst.
David Scherfgens Website | Konzentrationstest Polizei

p0llux

Treue Seele

Beiträge: 101

Wohnort: Aachen

Beruf: HiWi (theo. Inf.)

  • Private Nachricht senden

133

25.01.2008, 00:41

Falls hier jemand das Halteproblem löst, bitte melden! Wollte mich gerne über Rekursionstheorie prüfen lassen und da kann etwas Extrawissen nicht schaden ;)
http://www.scienceandcode.org http://www.mathestudium.org

Entenwickler

Frischling

Beiträge: 6

  • Private Nachricht senden

134

25.01.2008, 17:44

Zitat von »"S.Seegel"«

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 ;)


Ich hab mir den Code überhaupt nicht angeschaut, sondern nur C'P, und das wollte dann eben nicht klappen ;)
Ich bin kein Klukscheisser - ich weiß es wirklich besser!

Werbeanzeige