Deklarative Programmierung

Übungszettel 08 - Jonathan Wendt

originaler Übungszettel

Racket-File

Aufgabe 06

Aufgabenbeschreibung:

Das Nim-2-3-Spiel1 ist ein Spiel für 2 Personen. Zu Beginn werden Streichhölzer in 2 Reihen ausgelegt, wobei die Anzahl der Streichhölzer in den einzelnen Reihen beliebig gewählt werden kann. Die Spieler ziehen nun abwechselnd. Wer am Zug ist, entnimmt aus der Reihe, die mehr Streichhölzer enthält, 2 oder 3 Streichhölzer. Wenn beide Reihen gleich viele Streichhölzer enthalten, kann eine beliebige Reihe wählen. Wer zuerst nicht mehr ziehen kann, hat das Spiel verloren.

Aufgabe 06 (a)

Aufgabenbeschreibung

Schreiben Sie eine Funktion:

xxxxxxxxxx
; Number Number -> Bool
; Checks if one can win the game if the two rows contain
; n and m matches.

(check-expect (win? 2 2) false)
(check-expect (win? 3 2) false)
(check-expect (win? 2 4) true)
(check-expect (win? 2 5) true)
(check-expect (win? 9 6) true)

(define (win? n m) ...

Lösung

xxxxxxxxxx
; Number Number -> Bool
; Checks if one can win the game if the two rows contain
; n and m matches.
(check-expect (win? 2 2) false)
(check-expect (win? 3 2) false)
(check-expect (win? 2 4) true)
(check-expect (win? 2 5) true)
(check-expect (win? 9 6) true)

(define (win? n m)
  (if (and (< n 2) (< m 2)) false
    (not (and
      (if (>= n 3) (win? (- n 3) m) true)
      (if (>= n 2) (win? (- n 2) m) true)
      (if (>= m 3) (win? n (- m 3)) true)
      (if (>= m 2) (win? n (- m 2)) true)
     ))))

Aufgabe 06 (b)

Aufgabenbeschreibung

Zeigen Sie, dass Ihre (win? n m)-Implementierung terminiert.

Lösung

Der erste Aufruf von win? erfolgt mit beliebigen $n$$n$ und $m$$m$. Sofern die Abbruchbedingung $(n<2)\wedge (m<2)$$(n<2) \land (m<2)$ erfüllt ist, erfolgt kein weiterer rekursiver Aufruf und die Funktion terminiert. Ist die Bedingung nicht erfüllt, so erfolgt...

• falls $n\ge 3$$n \geq 3$ mit $n=n-3$$n=n-3$
• falls $n\ge 2$$n \geq 2$ mit $n=n-2$$n=n-2$
• falls $m\ge 3$$m \geq 3$ mit $m=m-3$$m=m-3$
• falls $m\ge 2$$m \geq 2$ mit $m=m-3$$m=m-3$

... ein erneuter Aufruf von win?, während der jeweils andere Wert unverändert bleibt.

In jedem erneuten Aufruf gilt also in jedem Fall entweder $n_1<n_0$$n_1 < n_0$ oder $m_1<m_0$$m_1 < m_0$, womit beide Parameter mit jeder Rekursionsstufe gegen ihre Abbruchbedingung streben.

Aufgabe 06 (c)

Aufgabenbeschreibung

Schreiben Sie eine Funktion:

xxxxxxxxxx
; Number Number -> String
; Suggests a move for the pick-a-match game
(check-expect (suggest 3 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
(check-expect (suggest 2 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
(check-expect (suggest 6 2) "Ziehe 3 aus der ersten Reihe")
(check-expect (suggest 4 2) "Ziehe 2 aus der ersten Reihe")
(check-expect (suggest 2 4) "Ziehe 2 aus der zweiten Reihe")
(check-expect (suggest 2 5) "Ziehe 3 aus der zweiten Reihe")

(define (suggest n m) ...

(suggest m n) soll dabei dem Spieler den nächsten Zug empfehlen, sodass dieser gewinnt. Greifen Sie dabei auf ihre (win? n m)-Funktion zurück. Ist es nicht möglich für den Spieler zu gewinnen, soll ein Text mit dieser Information zurückgegeben werden.

Lösung

xxxxxxxxxx
; Number Number -> String
; Suggests a move for the pick-a-match game
(check-expect (suggest 3 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
(check-expect (suggest 2 2) "Du kannst das Spiel mit keinem Zug mehr gewinnen")
(check-expect (suggest 6 2) "Ziehe 3 aus der ersten Reihe")
(check-expect (suggest 4 2) "Ziehe 2 aus der ersten Reihe")
(check-expect (suggest 2 4) "Ziehe 2 aus der zweiten Reihe")
(check-expect (suggest 2 5) "Ziehe 3 aus der zweiten Reihe")

(define (suggest n m)
  (if (not (win? n m)) "Du kannst das Spiel mit keinem Zug mehr gewinnen"
    (cond
      [(and (>= n 3) (not (win? (- n 3) m))) "Ziehe 3 aus der ersten Reihe"]
      [(and (>= m 3) (not (win? n (- m 3)))) "Ziehe 3 aus der zweiten Reihe"]
      [(and (>= n 2) (not (win? (- n 2) m))) "Ziehe 2 aus der ersten Reihe"]
      [(and (>= m 2) (not (win? n (- m 2)))) "Ziehe 2 aus der zweiten Reihe"])))