Wert einer Folge berechnen

9. Juli, 2008

Gegeben sei folgende rekursive definierte Folge:

a_1 = 2, a_n = \frac{a_{n-1}}{2} + \frac{1}{a_{n-1}}

Diese Folge konvergiert gegen die Quadratwurzel von 2. Die Folge ist ein Beispiel für ein allgemeines Halbierungsverfahren zur Bestimmung der Quadratwurzel einer Zahl.

Implementieren Sie jeweils eine rekursive und nicht rekursive Methode, um den Wert der Folge näherungsweise zu berechnen.

Kommentar schreiben » | Kontrollanweisungen, Leicht, Rekursion | Mit Tag(s) versehen: , , | Permalink
Verfasst von programmieraufgaben

Sixteen-Puzzle lösen

4. Juni, 2008

Wir betrachten folgendes Geduldsspiel:

Das Spielbrett enthält 8 rote und 8 grüne Steine. Ein Feld in der Mitte ist frei.

Ziel des Spiels ist es die grünen und roten Steine auszutauschen.

Folgende horizontalen und vertikalen Züge sind dabei möglich:

  • Ein zum leeren Feld angrenzender Stein darf in das leere Feld verschoben werden.
  • Ein Stein darf über einen anderen Stein (egal welche Farbe) in das leere Feld springen.

Hier drei gültige aufeinanderfolgende Spielzüge:

Implementieren Sie ein Programm mit rekursivem Backtracking, das eine Lösung für dieses Problem findet. Beachten Sie, das ein Hin- und Herschieben von Steinen zu unendlichen Zugfolgen führt. Dies kann durch beschränkte Tiefensuche gelöst werden: Bei 50 Zügen wird die Suche abgebrochen (es gibt Lösungen mit weniger Zügen).

Das Spiel habe ich hier gefunden. Dort kann man es mit einem JavaScript-Programm spielen. Den Ursprung des Spiels habe ich leider nicht herausgefunden.

Kommentar schreiben » | Felder, Kontrollanweisungen, Rekursion, Schwierig | Mit Tag(s) versehen: , , , | Permalink
Verfasst von programmieraufgaben