Algorithmen und Programmierung II

Übungsblatt 11 - Musterlösung

    void dowhile() { z=f(z); if (c(z)) dowhile(); }

    T dowhile(T z) {
        z = f(z);
        if (c(z)) return dowhile(z);
        else return z;
    }

    dowhile :: (a -> a) -> (a-> Bool) -> a -> a
    dowhile f c z = if c z' then dowhile f c z' else z'
                    where z' = f z

public class Wegsuche {
    
    static boolean[][] adj;     // Adjazenzmatrix
    static boolean[] marke;     // Markierung für besuchte Knoten
    static int[] weg;           // bisheriger Weg
    static int schritte = 0;    // Anzahl Schritte auf bisherigem Weg
    static int start, ziel;
    
    static void sucheWeg(boolean [][] matrix, int a, int b) throws Exception {
        adj = matrix; start = a; ziel = b;
        marke = new boolean[matrix.length];
        weg = new int[matrix.length];
        schritte = 0;
        if (!versuche(a)) throw new Exception ("kein Weg vorhanden");
    }
    
    static boolean versuche(int knoten) {
        if ((knoten==start || adj[weg[schritte-1]][knoten]) && !marke[knoten]) {
            marke[knoten] = true;       // "forwards"
            weg[schritte++] = knoten;   // "forwards"
            if (knoten == ziel) {       // "complete"
                ausgabe();
                return true;
            } else 
                for (int i = 0; i < adj.length; i++)
                    if (versuche(i)) return true;
            schritte--;                 // "backwards"
        }
        return false;
    }
    
    static void ausgabe() {
        for (int i = 0; i < schritte; i++)
            System.out.print(weg[i] + (i == schritte - 1 ? "\n" : " -> "));
    }
}

import java.io.*;

public class Springerzug {

    static boolean[][] marke;  // das Schachbrett
    static int[] zugX, zugY;   // aktueller Weg, i. Schritt = (zugX[i], zugY[i])
    static int n,              // Kantenlänge des Bretts
               zuege,          // Länge des aktuellen Weges 
               startX, startY;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) {
        initialisiere();
        versuche(startX, startY);
    }

    /** Parameter von der Kommandozeile einlesen, Variablen initialisieren */
    static void initialisiere() {
        try {
            System.out.print("Kantenlaenge des Bretts (n): ");
            n = Integer.parseInt(br.readLine());
            System.out.print("Startposition (x [1..n]): ");
            startX = Integer.parseInt(br.readLine());
            System.out.print("Startposition (y [1..n]): ");
            startY = Integer.parseInt(br.readLine());
        } catch (Exception e) {
            System.out.println("Eingabe konnte nicht gelesen werden.");
            System.exit(1);
        }
        marke = new boolean[n + 1][n + 1];  // [0] wird ignoriert
        zugX = new int[n * n + 1];
        zugY = new int[n * n + 1];
    }

    /** Backtracking: rekursive Methode */
    static void versuche(int x, int y) {
        if (x > 0 && x <= n && y > 0 && y <= n && !marke[x][y]) { // "legal"
            markiere(x, y);
            if (zuege == n * n) {  // "complete"
                ausgabe();
                pause();
            } else {
                for (int plusX = -2; plusX <= 2; plusX++)
                    for (int plusY = -2; plusY <= 2; plusY++)
                        if (Math.abs(plusX) + Math.abs(plusY) == 3)
                                versuche(x + plusX, y + plusY);
            }
            loeschen(x, y);
        }
    }

    /** Backtracking: "forwards"-Schritt */
    static void markiere(int x, int y) {
        marke[x][y] = true;
        zuege++;
        zugX[zuege] = x;
        zugY[zuege] = y;
    }

    /** Backtracking: "backwards"-Schritt */
    static void loeschen(int x, int y) {
        marke[x][y] = false;
        zuege--;
    }

    static void ausgabe() {
        for (int i = 1; i < zugX.length; i++)
            System.out.print(zugX[i] + "," + zugY[i] + (i % 20 == 0 ? "\n" : " "));
        System.out.println("\n");
    }

    static void pause() {
        System.out.print("Abbrechen (N/j)? ");
        try { if (br.readLine().equalsIgnoreCase("j")) System.exit(0); } 
        catch (Exception e) { }
    }
}