![[HaBo]](/styles/default/logoklein.png){kind=small}
Das Rätsel hat bestimmt schon fast jeder mal gesehen:
http://www.okkd.de/kd-web/raetsel/eimer.php
Also 2 Eimer mit X,Y Liter Fassungsvermögen, mit denen man Z Liter abemessen muss.
Klassisches Beispiel:
Eimer A fasst 3, Eimer B 5 Liter. Wie kann man 4 Liter abmessen?
Mögliche Lösung :
fuelle:A=5,
(von:A, inh:5>>B,inh:0),
leere:B,
(von:A,inh:2>>B,inh:0),
fuelle:A=5,
(von:A,inh:5>>B,inh:2),
leere:B
Habo Frage:
einfach:
1)´Eimer A: 25l, B: 13l
Wir brauchen 22 Liter. Sollte in 19 Schritten möglich sein
mittel:
2) Eimer A: 15: B:13, gesucht: 20 Liter. 15 Schritte müssten es sein.
3) Eimer A:1550,B:1320, Gesucht: 2000L. 89 Schritte (nun aber wirklich per Hand nicht mehr mit vertretbarem Zeitaufwand lösbar
).
schwer:
4) A: 50, B:33, Gesucht:10 Liter
Wieviele Schritte hat die kleinste Lösung?
Edit:
Vorschlag für die Ausgabe:
Eimer eindeutig durch Kleinbuchstaben bezeichnen,
jeden Schritt durch ein Komma trennen, Namensgebung der Schritte:
Füllen:
fuelle(Bez)
Leeren:
leere(Bez)
Umfüllen:
Bez:AktuellerInhalt>>Bez:AktuellerInhalt
Bsp für 5 und 3 Liter:
[fuelle(a),
a:5>>b:0,
leere(b),
a:2>>b:0,
fuelle(a),
a:5>>b:2,
leere(b)]
Wer sich daran hält, kann den kleiner verifier nutzen (Sicstus, GNU Prolog oder SWI vorausgesetzt):
http://www.okkd.de/kd-web/raetsel/eimer.php
Also 2 Eimer mit X,Y Liter Fassungsvermögen, mit denen man Z Liter abemessen muss.
Klassisches Beispiel:
Eimer A fasst 3, Eimer B 5 Liter. Wie kann man 4 Liter abmessen?
Mögliche Lösung :
fuelle:A=5,
(von:A, inh:5>>B,inh:0),
leere:B,
(von:A,inh:2>>B,inh:0),
fuelle:A=5,
(von:A,inh:5>>B,inh:2),
leere:B
Habo Frage:
einfach:
1)´Eimer A: 25l, B: 13l
Wir brauchen 22 Liter. Sollte in 19 Schritten möglich sein
mittel:
2) Eimer A: 15: B:13, gesucht: 20 Liter. 15 Schritte müssten es sein.
3) Eimer A:1550,B:1320, Gesucht: 2000L. 89 Schritte (nun aber wirklich per Hand nicht mehr mit vertretbarem Zeitaufwand lösbar
).schwer:
4) A: 50, B:33, Gesucht:10 Liter
Wieviele Schritte hat die kleinste Lösung?
Edit:
Vorschlag für die Ausgabe:
Eimer eindeutig durch Kleinbuchstaben bezeichnen,
jeden Schritt durch ein Komma trennen, Namensgebung der Schritte:
Füllen:
fuelle(Bez)
Leeren:
leere(Bez)
Umfüllen:
Bez:AktuellerInhalt>>Bez:AktuellerInhalt
Bsp für 5 und 3 Liter:
[fuelle(a),
a:5>>b:0,
leere(b),
a:2>>b:0,
fuelle(a),
a:5>>b:2,
leere(b)]
Wer sich daran hält, kann den kleiner verifier nutzen (Sicstus, GNU Prolog oder SWI vorausgesetzt
):Nutzung:
Sich an das Ausgabeformat halten (als Bezeichner dann bitte Kleinbuchstaben nehmen, da Großbuchstaben in Prolog für ungebundene Variablen stehen)
Nachfolgenden Code als PL Datei speichern, in der Prolog Konsole:
consult('dateiname.pl'). eingeben.
für die verifizierung ruft man
verify(ZielWert,[Eimer1,Eimer2 usw],[Schritt1,Schritt2...]). <---Punkt als Anfragebestätigung
auf.
Eimerliste: liste mit Eimern, die genutzt werden
D.h zwischen den [ ] Klammern werden die Eimer aufgeführt:
Format: eimer(Bezeichner:Maxvolume:Startvolume)
Bsp: [eimer(x:10:0),eimer(y:5:0),eimer(z:7:0)]
Schritte: eure Programmausgabe eingefügt zwischen [ ]
Bsp:
ob die Liste nun zusätzlich zum Komma durch Zeilenumbrüche getrennt ist, spielt keine Rolle - eine Anfrage ist in Prolog erst mit "." (Punkt) bestätigt und kann damit über viele Zeilen gehen
Im Erfolgsfall gibt Prolog ein klares 'yes' aus, im Fehlerfall (wenn z.B die Endsumme oder Vol.Werte abweichen) wird ein "Trace" ausgegeben, angefangen mit dem "fehlerhaften" Schritt rückwärts bis zum ersten.
bsp (absichtlich eingebauter Fehler im letzten Schritt: in der eingegeben Lösung enthält Eimer b zu dem Zeitpunkt 1 Liter, nach interner Tabelle(Zustan) sind es allerdings 2:
Verifier:
Sich an das Ausgabeformat halten (als Bezeichner dann bitte Kleinbuchstaben nehmen, da Großbuchstaben in Prolog für ungebundene Variablen stehen)
Nachfolgenden Code als PL Datei speichern, in der Prolog Konsole:
consult('dateiname.pl'). eingeben.
für die verifizierung ruft man
verify(ZielWert,[Eimer1,Eimer2 usw],[Schritt1,Schritt2...]). <---Punkt als Anfragebestätigung
auf.
Eimerliste: liste mit Eimern, die genutzt werden
D.h zwischen den [ ] Klammern werden die Eimer aufgeführt:
Format: eimer(Bezeichner:Maxvolume:Startvolume)
Bsp: [eimer(x:10:0),eimer(y:5:0),eimer(z:7:0)]
Schritte: eure Programmausgabe eingefügt zwischen [ ]
Bsp:
Code:
verify(4,[eimer(a:5:0),eimer(b:3:0)],
[fuelle(a),a:5>>b:0,leere(b),a:2>>b:0,fuelle(a),a:5>>b:2,leere(b)]).Im Erfolgsfall gibt Prolog ein klares 'yes' aus, im Fehlerfall (wenn z.B die Endsumme oder Vol.Werte abweichen) wird ein "Trace" ausgegeben, angefangen mit dem "fehlerhaften" Schritt rückwärts bis zum ersten.
bsp (absichtlich eingebauter Fehler im letzten Schritt: in der eingegeben Lösung enthält Eimer b zu dem Zeitpunkt 1 Liter, nach interner Tabelle(Zustan) sind es allerdings 2:
Code:
?- verify(4,[eimer(a:5:0),eimer(b:3:0)],
[fuelle(a),a:5>>b:0,leere(b),a:2>>b:0,fuelle(a),a:5>>b:1,leere(b)]).
Zustand:[eimer(a:5:5),eimer(b:3:2)] ; Schritt:a:5>>b:1
Zustand:[eimer(a:5:0),eimer(b:3:2)] ; Schritt:fuelle(a)
Zustand:[eimer(b:3:0),eimer(a:5:2)] ; Schritt:a:2>>b:0
Zustand:[eimer(a:5:2),eimer(b:3:3)] ; Schritt:leere(b)
Zustand:[eimer(a:5:5),eimer(b:3:0)] ; Schritt:a:5>>b:0
Zustand:[eimer(a:5:0),eimer(b:3:0)] ; Schritt:fuelle(a)
Code:
:-use_module(library(lists)).
sum([],0).
sum([eimer(_:_:Vol)|T],Sum):-sum(T,SubSum),Sum is SubSum+Vol.
step(Vars,leere(X),[eimer(X:Max:0)|T]):- select(eimer(X:Max:_),Vars,T),!.
step(Vars,fuelle(X),[eimer(X:Max:Max)|T]):-select(eimer(X:Max:_),Vars,T),!.
step(Vars,X:VolX>>Y:VolY,[eimer(X:XMax:NVolX),eimer(Y:YMax:NVolY)|T]):-
select(eimer(X:XMax:VolX),Vars,TVars),
select(eimer(Y:YMax:VolY),TVars,T),
YDif is YMax-VolY,
(VolX>YDif,NVolX is VolX-YDif,NVolY = YMax;
VolX=<YDif,NVolX=0,NVolY=VolX).
%Vars=Liste mit "eimer(Bez:Maxvolume:Startvolume)"
verify(Goal,Vars,[]):-sum(Vars,Goal); write('summe stimmt nicht'),fail.
verify(Goal,Vars,[Step|Steps]):-step(Vars,Step,NVars),
verify(Goal,NVars,Steps);
nl,write('Zustand':Vars),write(' ; Schritt':Step),fail.
