Grundlagen der Informatik – Lösungen & Aufgaben

Umfüllprobleme

Eine Bauersfrau soll aus einem oben offenen Bottich voll Essig genau einen Liter abmessen, hat dazu jedoch nur ein 3-l- und ein 5-l-Gefäß. Wie erreicht sie dies am besten?

Gitter
via FH Friedberg

Es wird ein 60°-Gitter konstruiert. Die Höhe beträgt dabei das Fassvolumen des ersten Behälters. Die Breite beträgt das Fassvolumen des zweiten Behälters. Es werden nur Wege markiert, um an das Ziel zu kommen. Um beispielweise die Menge zu erhalten, benötigen wir einen Wert auf der zweiten horizontalen Linie (von unten) oder zweiten vertikalen Linie (von links). Es gilt dabei, dass wir die Richtung angeben müssen und dann folglich bis zum Rand fahren müssen. Das bedeutet, wer bei (0, 0) beginnt und die Waagrechte wählt, muss bis zu (5, 0) fahren.

Die Lösung für das Problem ist also wie folgt:

(0, 0) → (5, 0) Fülle den ersten (= 5 Liter) Behälter mit 5 Litern auf
(5, 0) → (2, 3) Mache den zweiten Behälter mit dem Inhalt des ersten Behälters voll
(2, 3) → (2, 0) Entleere den zweiten Behälter
(2, 0) → (0, 2) Fülle den zweiten Behälter mit dem Inhalt des ersten Behälters auf
(0, 2) → (5, 2) Fülle den ersten Behälter mit 5 Litern auf
(5, 2) → (4, 3) Mache den zweiten Behälter mit dem Inhalt des ersten Behälters voll
(4, 3) → (4, 0) Entleere den zweiten Behälter
(4, 0) → (1, 3) Fülle den zweiten Behälter mit dem Inhalt des ersten Behälters auf
(1, 3) → (0, 1) Entleere den zweiten Behälter. Fülle den zweiten Behälter mit dem Inhalt des ersten Behälters auf
(0, 1) Ziel erreicht

Es lassen sich alle Umfülle-Probleme mit diesem System lösen, die die folgenden Eigenschaften besitzen:

Die vorige Aussage stimmt nicht ganz. Der Lösungsansatz führt immer zu einer Lösung, wenn das Problem lösbar ist. Die Menge 1 lässt sich nicht durch Umfüllen von 4 und 6-Liter-Behältern erhalten. In diesem Lösungansatz erhält man dann ein unendliches Konstrukt in dem Gitter.

python Skript

Mit dem mitgelieferten Skript lassen sich alle Lösungen für Umfüllprobleme mittels eines Gitters berechnen und die schnellste Lösung wird zurückgegeben.

meisterluk@linux ~/proj/problems/gdi % python decating_problems.py           
maximal elements in container 1: 3
maximal elements in container 2: 5
You want to fill up a container with: 1

((0, 0), (3, 0), (0, 3), (3, 3), (1, 5))

== Description of the solution ==
Fill up container 1.
Move content of container 1 to 2.
Fill up container 1.
Move content of container 1 to 2.

Die errechnete Lösung ist schneller als die vorher vorgestellte.

Alle Umfüllprobleme

4 & 9 → 6: 9 Liter auffüllen. 9 Liter zu 4 Liter umfüllen. 4 Liter wegleeren. 9 Liter zu 4 Liter umfüllen. 4 Liter umfüllen. 9 Liter zu 4 Liter umfüllen. 4 Liter auffüllen. 9 Liter zu 4 Liter umfüllen.
3 & 5 → 1: 3 Liter auffüllen. 3 Liter zu 5 Liter umfüllen. 3 Liter auffüllen. 3 Liter zu 5 Liter umfüllen.
5 & 3 → 4: 8 Liter zu 5 Liter umfüllen. 5 Liter zu 3 Liter umfüllen. 3 Liter zu 8 Liter umfüllen. 5 Liter zu 3 Liter umfüllen. 8 Liter zu 5 Liter umfüllen. 5 Liter zu 3 Liter umfüllen.