Umfüllaufgabe
Anneli von Koenemann
ich hoffe, ich habe jetzt nicht überlesen, dass dieses Problem hier
schon besprochen wurde ...
Gibt es einen Trick, wie man "Umfüllaufgaben" angeht?
Also z.B.: in einem 8l-Krug sind 8 l Wasser, mittels zwei Krügen zu 3
und 5 l sollten zweimal 4 l abgemessen werden ...
Vielen Dank für jeden Tipp
Anneli
Jan Merolant
Anneli von Koenemann heeft geschreven in bericht
<6td91vcdnpikg2hc3...@4ax.com>...
>Hallo,
>
>ich hoffe, ich habe jetzt nicht überlesen, dass dieses Problem hier
>schon besprochen wurde ...
>Gibt es einen Trick, wie man "Umfüllaufgaben" angeht?
>Also z.B.: in einem 8l-Krug sind 8 l Wasser, mittels zwei Krügen zu 3
>und 5 l sollten zweimal 4 l abgemessen werden ...
>
v
v
v
v
Liters (3, 5, 8)
---------------------------
1. 8 => 5 (0 , 5 , 3)
2. 5 => 3 (3 , 2 , 3)
3. 3 => 8 (0 , 2 , 6)
4. 5 => 3 (2 , 0 , 6)
5. 8 => 5 (2 , 5 , 1)
6. 5 => 3 (3 , 4 , 1)
7. 3 => 8 (0 , 4 , 4)
Jan
Sandra Schneider
S
P
O
I
L
E
R
1) fülle 3 Liter in das 3 Liter Gefäß
2) fülle diese 3 Liter in das 5 Liter Gefäß
3) fülle erneut 3 Liter in das 3 Liter Gefäß
4) fülle 2 dieser 3 Liter in das 5 Liter Gefäß
5) schütte den Inhalt des 5 Liter Gefäßes zurück in das 8 Liter Gefäß
6) Fülle den verbliebenen Liter aus dem 3 Liter Gefäß in das 5 Liter Gefäß
7) Messe nochmals 3 Liter ab und fülle sie in das 5 Liter Gefäß um
Anneli von Koenemann
Ich wollte wissen, ob es einen "Trick" gibt, eine Formel, nach der man
sowas angeht.
Viele Grüße
Anneli
Michael Peuser (h)
"Anneli von Koenemann" <vonkoe...@web.de>
> Vielen Dank :-), aber die Lösung hatte ich schon :-)
> Ich wollte wissen, ob es einen "Trick" gibt, eine Formel, nach der man
> sowas angeht.
>
Mein Eindruck war auch schon, dass "Meta-Themen" in dieser NG nicht so gut
kommen...
Imo gibt es nur einen systematischen Ansatz:
(1) Erzeuge einen (gerichteten) Grafen, dessen Knoten aus allen möglichen
Füllstandskombinationen der Behälter bestehen (Im Beispiel also: 0...8 x
0..5 x 0..3 = 216 Knoten) Bei Ganzzahligkeit gibt es viele aber nicht
unendlich viele Möglichkeiten; lästig wird es, wenn die Behälter irrationale
Inhalte haben sollten ;-)
(2) Verbinde nun Knoten, wenn eine Umfüllung möglich ist.
(3) Suche den Weg vom Anfangszustand zum Endzustand.
Mir ist nicht bekannt, ob es da Programme für gibt - programmtechnisch
steckt da allerdings keine Schwierigkeit dahinter, außer dass die
Grafensuche etwas dauern könnte......
Gruß
Michael P
Bernd Gramlich
> Ich wollte wissen, ob es einen "Trick" gibt, eine Formel, nach der
> man sowas angeht.
Der Trick heißt "euklidischer Algorithmus". In einem alten Artikel
(<3B264A3B...@tenuki.de>) beschrieb ich einmal, wie man ihn für
zwei Krüge (z. B. mit 3 und 5 Litern) und einen unendlich großen
Wasservorrat anwendet (z. B. um 4 Liter abzumessen). Das klappt auch
noch, wenn Du den Wasservorrat durch einen dritten Krug ersetzt, der
mindestens so viel Wasser faßt wie die beiden anderen Krüge zusammen
(hier also 8 Liter).
Da ungefähr alle sechs Monate nach dieser allgemeinen Lösung gefragt
wird, könnte man sie evtl. einmal in die FAQ aufnehmen.
--
Bernd Gramlich Quod scripsi, scripsi.
Michael Peuser (h)
"Michael Peuser (h)" <po...@mpeuser.de> schrieb im Newsbeitrag
news:av6ru2$22l$07$1...@news.t-online.com...
....
> (1) Erzeuge einen (gerichteten) Grafen, dessen Knoten aus allen möglichen
> Füllstandskombinationen der Behälter bestehen (Im Beispiel also: 0...8 x
> 0..5 x 0..3 = 216 Knoten)
Man kann sich natürlich alle "Zustände" sparen, deren Füllstandssummen nicht
der gesamten Flüssigkeitsmenge entsprechen; damit bleiben im Beispiel nur
noch 24 Knoten übrig, das ist schon einigermaßen übersichtlich....
> Gruß
> Michael P
>
>
Anneli von Koenemann
also, da schluckt meiner-eine nur noch ... ;-)
anneli
Andreas Hohmann
Hallo,
folgendes schrieb ich vor fast einem Jahr zur selben Problematik:
Hallo,
ausnahmsweise mal kein Rätsel, sondern eine Anleitung, wie man jedes
Wassereimer-Rätsel grafisch lösen kann (z.B. das vom 17.01., wo man
mit 4- und 9-Liter Eimern 6 Liter abmessen soll, was ich hier als
Beispiel nehmen möchte).
1. Man zeichen ein Koordinatensystem mit Ursprung unten links und 4
Einheiten auf der Ordinate(y) und 9 Einheiten auf der Abszisse(x).
2. Dann zeichne Man ein Gitter ein, indem man innerhalb des Rechtecks
(x=0 bis x=9 und x=0 bis y=4) alle Senkrechten und alle Waagrechten
einzeichnet (immer auf ganzen Einheiten)
3. Nun muss man noch alle Diagonalen, die von links oben nach rechts
unten verlaufen einzeichnen, und zwar alle(!) innerhalb des Rechtecks,
also auch die ganz oben rechts (von x=8/y=4 bis x=9/y=3).
Ein beliebiger Schnittpunkt innerhalb des Rechtecks stellt nun den
Füllstand der beiden Eimer dar.
In diesem 'Graphen' kann man nun alle Lösungen finden, indem man sich
von der Lösung rückwärts entlang der Linien bis zum
Koordinatenursprung bewegt.
Eine Bewegung erfolgt entlang der Linien (vertikalen, Horizontalen und
Diagonalen) immer bis zum Rand des Rechtecks.
Für das Beispiel existieren zwei Lösungen (Füllstände immer in
(x/y)-Schreibweise):
A. Man beginnt beim Ziel, also (6/0), dann geht man senkrecht nach
oben zu (6/4), weiter zu (9/1), dann (0/1), (1/0), (1/4), (5/0),
(5/4), (9/0) und schließlich (0/0).
B. (länger): (6/0), (2/4), (2/0), (0/2), (9/2), (7/4), (7/0), (3/4),
(3/0), (0/3), (9/3), (8/4), (8/0), (4/4), (4/0), (0/4), (0/0).
Das System funktioniert auch mit drei Eimern, allerdings sieht das
Koordinatensystem etwas anders aus:
Die normalerweise senkrechte Ordinate ist um 45 Grad nach rechts
geneigt, somit kann ein Dreieck entstehen, wobei die dritte Seite
(also rechts) dem dritten Eimer entspricht.
Michael Peuser (h)
"Anneli von Koenemann" <vonkoe...@web.de> schrieb
> also, da schluckt meiner-eine nur noch ... ;-)
> anneli
Solltest du aber verstehen (s.u.) - sonst wirds nix mit Computerlinguistik
;-)
Andreas Baus
Dann bleibt die Flüssigkeitmenge aber nicht mehr konstant :)
--
----
-----------------------------------------------------------------------
[Insert joke here.] ----
--
an...@studcs.uni-sb.de (Andreas Baus)