Legen Sie eine Datenstruktur fest, die den Zustand der „Eimer-Welt“ repräsentiert. Logik und Logikprogrammierung.

Question

Aufgabe Eimer-Problem:

Ein Wasserverkäufer sitzt an seinem Brunnen, um Wasser zu verkaufen. Er hat zwei Eimer, einen zu 7 l und einen zu 4 l. Für einen Liter Wasser verlangt er einen Preis von einem Goldstück.

Die Wasserkäufer möchten daher nur die tatsächlich benötigte Wassermenge kaufen, z. B. 1 l, 2 l, 3 l, 5 l und 6 l.

Der Wasserverkäufer kann folgende Handlungen ausführen:

· einen leeren Eimer im Brunnen voll Wasser füllen,
· einen Eimer beliebiger Füllung in den Brunnen entleeren,
· Wasser aus einem Eimer in den anderen ohne Verlust umfüllen.

Ist es möglich und wenn ja, wie die gewünschten Mengen abzumessen?

Anleitung:

a) Legen Sie eine Datenstruktur fest, die den Zustand der „Eimer-Welt“ repräsentiert. Als wesentliche Daten muss sie die Inhalte der beiden Eimer enthalten.

b) Formulieren Sie mithilfe dieser Datenstruktur sechs Regeln für die Prozedur aktion/2, die die möglichen Handlungen repräsentieren:
· den großen Eimer entleeren · den kleinen Eimer entleeren · den großen Eimer vollschöpfen · den kleinen Eimer vollschöpfen
· die mögliche Menge vom kleinen Eimer in den großen Eimer umfüllen · die mögliche Menge vom großen Eimer in den kleinen Eimer umfüllen

c) Definieren Sie einen sinnvollen Startzustand durch einen Fakt!
Definieren Sie für die interessierenden Zielzustände jeweils einen Fakt!

d) Wählen Sie ein geeignetes Suchverfahren zur Lösung!

Problem/Ansatz:

Die Aufgabe ist für Logikprogramierung in Prolog. Wie könnte man aber so eine Aufgabe grundsätzlich programmiermäßig darstellen?

Kann ruhig auch in C, C++ oder Java sein.

1. Teil: Datenstruktur

2 l Eimer, 4 l Eimer und Mengen

2. Teil: 6 Funktionen

3. Teil + 4. Teil: Start, Ende, Hauptprogramm

5. Teil: Suchverfahren

Answer 1

Antwort mit KI erzeugt

Datenstruktur für die „Eimer-Welt“:

In diesem Problem geht es darum, den aktuellen Zustand der beiden Eimer zu verfolgen. Dazu können wir eine Struktur verwenden, die die aktuelle Füllmenge der beiden Eimer speichert. In Java könnte dies beispielsweise durch eine Klasse BucketState dargestellt werden:

java
class BucketState {
    int bigBucket;  // Füllstand des großen Eimers (7 l)
    int smallBucket;  // Füllstand des kleinen Eimers (4 l)

    // Konstruktor
    public BucketState(int bigBucket, int smallBucket) {
        this.bigBucket = bigBucket;
        this.smallBucket = smallBucket;
    }

    // Methode zur Ausgabe des aktuellen Zustands
    @Override
    public String toString() {
        return "(" + bigBucket + "L, " + smallBucket + "L)";
    }

    // Methode zur Überprüfung der Gleichheit zweier Zustände
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        BucketState other = (BucketState) obj;
        return bigBucket == other.bigBucket && smallBucket == other.smallBucket;
    }

    @Override
    public int hashCode() {
        return 31 * bigBucket + smallBucket;
    }
}

Sechs Funktionen für die möglichen Aktionen:

1. Großen Eimer entleeren.
2. Kleinen Eimer entleeren.
3. Großen Eimer vollschöpfen.
4. Kleinen Eimer vollschöpfen.
5. Wasser vom kleinen Eimer in den großen Eimer umfüllen.
6. Wasser vom großen Eimer in den kleinen Eimer umfüllen.

Hier sind die Methoden, die diese Aktionen in Java definieren:

java
class WaterSeller {

    // Großen Eimer entleeren
    public static BucketState emptyBigBucket(BucketState state) {
        return new BucketState(0, state.smallBucket);
    }

    // Kleinen Eimer entleeren
    public static BucketState emptySmallBucket(BucketState state) {
        return new BucketState(state.bigBucket, 0);
    }

    // Großen Eimer vollschöpfen
    public static BucketState fillBigBucket(BucketState state) {
        return new BucketState(7, state.smallBucket);
    }

    // Kleinen Eimer vollschöpfen
    public static BucketState fillSmallBucket(BucketState state) {
        return new BucketState(state.bigBucket, 4);
    }

    // Wasser vom kleinen Eimer in den großen Eimer umfüllen
    public static BucketState pourSmallIntoBig(BucketState state) {
        int transferAmount = Math.min(state.smallBucket, 7 - state.bigBucket);
        return new BucketState(state.bigBucket + transferAmount, state.smallBucket - transferAmount);
    }

    // Wasser vom großen Eimer in den kleinen Eimer umfüllen
    public static BucketState pourBigIntoSmall(BucketState state) {
        int transferAmount = Math.min(state.bigBucket, 4 - state.smallBucket);
        return new BucketState(state.bigBucket - transferAmount, state.smallBucket + transferAmount);
    }
}

Startzustand und Zielzustände:

java
class Main {
    public static void main(String[] args) {
        BucketState startState = new BucketState(0, 0);
        BucketState goalState1 = new BucketState(0, 1);
        BucketState goalState2 = new BucketState(0, 2);
        BucketState goalState3 = new BucketState(0, 3);
        BucketState goalState5 = new BucketState(0, 5);
        BucketState goalState6 = new BucketState(0, 6);

        // Hier könnte der Code weitergehen, um die Suchstrategie zu implementieren.
    }
}

Suchverfahren:

Ein gängiges Suchverfahren für solch ein Problem ist der "Breadth-First Search" (BFS), weil es garantiert, dass die gefundenen Lösungen die kürzesten Wege sind. Hier ist eine Implementierung in Java:

java
import java.util.*;

class BucketSolver {

    public static List<BucketState> bfs(BucketState startState, BucketState goalState) {
        Queue<BucketState> frontier = new LinkedList<>();
        Map<BucketState, BucketState> cameFrom = new HashMap<>();  // um den Pfad zu rekonstruieren

        frontier.add(startState);
        cameFrom.put(startState, null);

        while (!frontier.isEmpty()) {
            BucketState current = frontier.poll();

            if (current.equals(goalState)) {
                return reconstructPath(cameFrom, current);
            }

            for (BucketState next : getNeighbors(current)) {
                if (!cameFrom.containsKey(next)) {  // falls der Zustand noch nicht betrachtet wurde
                    frontier.add(next);
                    cameFrom.put(next, current);
                }
            }
        }
        return null;  // kein Weg gefunden
    }

    private static List<BucketState> reconstructPath(Map<BucketState, BucketState> cameFrom, BucketState current) {
        List<BucketState> path = new ArrayList<>();
        while (current != null) {
            path.add(current);
            current = cameFrom.get(current);
        }
        Collections.reverse(path);
        return path;
    }

    private static List<BucketState> getNeighbors(BucketState state) {
        List<BucketState> neighbors = new ArrayList<>();
        neighbors.add(WaterSeller.emptyBigBucket(state));
        neighbors.add(WaterSeller.emptySmallBucket(state));
        neighbors.add(WaterSeller.fillBigBucket(state));
        neighbors.add(WaterSeller.fillSmallBucket(state));
        neighbors.add(WaterSeller.pourSmallIntoBig(state));
        neighbors.add(WaterSeller.pourBigIntoSmall(state));
        return neighbors;
    }

    public static void main(String[] args) {
        BucketState startState = new BucketState(0, 0);
        BucketState goalState = new BucketState(0, 3);  // Beispiel mit 3 Liter Zielzustand

        List<BucketState> path = bfs(startState, goalState);
        if (path != null) {
            for (BucketState state : path) {
                System.out.println(state);
            }
        } else {
            System.out.println("Kein Weg gefunden.");
        }
    }
}