Hackerboard Wiki HaboBlog
Hackerboard bei Facebook Hackerboard bei Google+ Hackerboard bei Twitter

[HaBo]

 
Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.

Eimerproblem

Diskussion: Eimerproblem im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige 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 ...

Antwort
Alt 22.05.09, 18:37   #1 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard Eimerproblem

Anzeige

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 ):

nutzung,code   


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:
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)]).
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:
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)
Verifier:
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.
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 22.05.09, 20:03   #2 (permalink)
 
Registriert seit: 07.02.04
Foxalem Leistung: Facit NTK
Foxalem eine Nachricht über ICQ schicken
Likes: 0
Standard

1) hab ich in 10 schritten.
2) keine ahnung xD
Foxalem ist offline   Mit Zitat antworten
   
HaBOT
 
- Anzeige -

Werbung ist gerade online    
Alt 22.05.09, 22:39   #3 (permalink)
CDW
Moderator
Themenstarter
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

@Foxalem: wir sind im "Programmieraufgaben" Unterforum
Code & Lösungen, die man durch diesen Code bekommen hat, sind willkommen

Zu 1: wenn Du es im Format:
Zitat:
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)]
postest, kann ich es auch gleich verifizieren
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 22.05.09, 23:19   #4 (permalink)
 
Registriert seit: 07.02.04
Foxalem Leistung: Facit NTK
Foxalem eine Nachricht über ICQ schicken
Likes: 0
Standard

Ehm jo xD sorry ^^ ich hab mir kurz den taschenrechner hergenommen und das hingedaddelt. Nu verstehe ich auch warum da steht (dass man es nicht mit der hand macht)
Tut mir leid hab das eben nur so nebenbei gelesen und gleich den mist geschrieben.
Foxalem ist offline   Mit Zitat antworten
Alt 23.05.09, 10:40   #5 (permalink)
 
Registriert seit: 04.12.08
xpecs Leistung: Facit NTK
Likes: 0
Standard

Hey coole Aufagabe die erinnert mich sehr an Stirb langsam 3
Ich habe das Problem in C++ gelöst und scheint zu funktionieren

Programm bei der Auführung
Programm bei der Ausführung   

xpecs@tux:~/Desktop/workspace/eimer$ ./eimer
Jetzt wird B aufgefüllt
EimerA: 0
EimerB: 13

EimerA: 13
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 13
EimerB: 13

EimerA: 1
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 1
EimerB: 13

EimerA: 14
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 14
EimerB: 13

EimerA: 2
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 2
EimerB: 13

EimerA: 15
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 15
EimerB: 13

EimerA: 3
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 3
EimerB: 13

EimerA: 16
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 16
EimerB: 13

EimerA: 4
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 4
EimerB: 13

EimerA: 17
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 17
EimerB: 13

EimerA: 5
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 5
EimerB: 13

EimerA: 18
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 18
EimerB: 13

EimerA: 6
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 6
EimerB: 13

EimerA: 19
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 19
EimerB: 13

EimerA: 7
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 7
EimerB: 13

EimerA: 20
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 20
EimerB: 13

EimerA: 8
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 8
EimerB: 13

EimerA: 21
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 21
EimerB: 13

EimerA: 9
EimerB: 0

Jetzt wird B aufgefüllt
EimerA: 9
EimerB: 13

EimerA: 22
EimerB: 0

Fertig
Durchgänge: 18
Angehängte Dateien
Dateityp: txt Eimer.txt (968 Bytes, 14x aufgerufen)
xpecs ist offline   Mit Zitat antworten
Alt 23.05.09, 12:45   #6 (permalink)
 
Registriert seit: 07.02.04
Foxalem Leistung: Facit NTK
Foxalem eine Nachricht über ICQ schicken
Likes: 0
Standard

So nu hab ich mich mal rangesetzt und das problem per Batch gelöst.
Ich hoffe dasses so nun richtig ist:

Variante 2):

Code:
Durchgang 1 
Eimer B befuellen: 
A = 0 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 33 Liter 
B = 0 Liter 
 
Durchgang 2 
Eimer B befuellen: 
A = 33 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 16 Liter 
B = 0 Liter 
 
Durchgang 3 
Eimer B befuellen: 
A = 16 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 49 Liter 
B = 0 Liter 
 
Durchgang 4 
Eimer B befuellen: 
A = 49 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 32 Liter 
B = 0 Liter 
 
Durchgang 5 
Eimer B befuellen: 
A = 32 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 15 Liter 
B = 0 Liter 
 
Durchgang 6 
Eimer B befuellen: 
A = 15 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 48 Liter 
B = 0 Liter 
 
Durchgang 7 
Eimer B befuellen: 
A = 48 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 31 Liter 
B = 0 Liter 
 
Durchgang 8 
Eimer B befuellen: 
A = 31 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 14 Liter 
B = 0 Liter 
 
Durchgang 9 
Eimer B befuellen: 
A = 14 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 47 Liter 
B = 0 Liter 
 
Durchgang 10 
Eimer B befuellen: 
A = 47 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 30 Liter 
B = 0 Liter 
 
Durchgang 11 
Eimer B befuellen: 
A = 30 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 13 Liter 
B = 0 Liter 
 
Durchgang 12 
Eimer B befuellen: 
A = 13 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 46 Liter 
B = 0 Liter 
 
Durchgang 13 
Eimer B befuellen: 
A = 46 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 29 Liter 
B = 0 Liter 
 
Durchgang 14 
Eimer B befuellen: 
A = 29 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 12 Liter 
B = 0 Liter 
 
Durchgang 15 
Eimer B befuellen: 
A = 12 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 45 Liter 
B = 0 Liter 
 
Durchgang 16 
Eimer B befuellen: 
A = 45 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 28 Liter 
B = 0 Liter 
 
Durchgang 17 
Eimer B befuellen: 
A = 28 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 11 Liter 
B = 0 Liter 
 
Durchgang 18 
Eimer B befuellen: 
A = 11 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 44 Liter 
B = 0 Liter 
 
Durchgang 19 
Eimer B befuellen: 
A = 44 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 27 Liter 
B = 0 Liter 
 
Durchgang 20 
Eimer B befuellen: 
A = 27 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 10 Liter 
B = 0 Liter 


Fertig!
In Eimer A befinden sich nun 10 Liter.
Dabei wurden in 20 Durchgaengen, 650 Liter weggekippt.
Angehängte Dateien
Dateityp: txt Eimer.txt (709 Bytes, 9x aufgerufen)
Foxalem ist offline   Mit Zitat antworten
Alt 23.05.09, 12:56   #7 (permalink)
CDW
Moderator
Themenstarter
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

@Foxalem:
ich glaub' Du hast einen Überlauf bzw fehlerhafte Berechnung
Code:
Durchgang 2 
Eimer B befuellen: 
A = 33 Liter 
B = 33 Liter 
 
Eimer B in A umfuellen: 
A = 16 Liter 
B = 0 Liter
In A passen 50 Liter rein. Beim Durchgang 2 sind da schon 33 Liter drin. Wenn man nochmal 33 hinzufügt, sind es trotzdem maximal 50 Liter und in B verbleiben 26 Liter. D.h wie Du auf die A=16 Liter kommst, ist etwas unklar

Beim Durchgang 5 gilt dasselbe (weiter habe ich nicht geschaut).
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 23.05.09, 13:08   #8 (permalink)
 
Registriert seit: 07.02.04
Foxalem Leistung: Facit NTK
Foxalem eine Nachricht über ICQ schicken
Likes: 0
Standard

Ehm... 33 + 33 = 66
66 - 50 = 16

Ich habe quasi in A schon 33Liter, kippe weitere 17 Liter von B in A. Kippe A aus und Kippe den Rest von B (16 Liter) in A.
Hab das nur etwas übersprungen. Hab mich eben an der Lösung von xpecs orrientiert, welche genauso ist

Mfg

Edit: Bei der lösung von xpecs zähle ich 19 durchgänge. Funktioniert mit meinem Programm auch wenn man die Variablen ändert. Is wohl das gleiche Prinzip.
Foxalem ist offline   Mit Zitat antworten
Alt 23.05.09, 16:55   #9 (permalink)
 
Registriert seit: 04.12.08
xpecs Leistung: Facit NTK
Likes: 0
Unhappy

Kann mir mal einer sagen, wieso ich bei 1.) ein Durchgang weniger habe als der Threadersteller?
und in Variante 2 komme ich auch nur auf 19 Durchgänge nicht auf 20 ?(

Antworten nach vorne
xpecs ist offline   Mit Zitat antworten
Alt 23.05.09, 17:16   #10 (permalink)
CDW
Moderator
Themenstarter
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

Zitat:
Kann mir mal einer sagen, wieso ich bei 1.) ein Durchgang weniger habe als der Threadersteller?
1)Deine Durchgangvariable wird nicht initialisiert
2)sie wird erst zum Schluss inkrementiert - und vorher kommen Breaks etc.. D.h angenommen man benötigt nur eine Aktion (Eimer auffüllen). Dann wird Dein Programm 0 Durchgänge ausgeben

3) Ihr beide zählt sowieso die Durchgänge komisch. Ein Durchgang/Schritt ist immer eine Aktion. Nicht 3-4 zusammengefasst
Bps:
Code:
//never ending :P
for(j = 0; j < 4; j--){
 EimerB.inhalt = EimerB.tank;
 
//Fülle B --> A
for(i = 0; i < EimerB.tank; i++)
{
 EimerB.inhalt--;
 EimerA.inhalt++;

//Eimer A voll, dann auskippen

 if(EimerA.inhalt >= EimerA.tank){
  EimerA.inhalt = 0;
 }
//Eimer B leer? auffüllen
 else if(EimerB.inhalt <= 0){
  break;
 }
}

 durchgang++;
}
Mehrere Modifizierungen der Inhalte werden hier als nur 1 Schritt gezählt. Kein Wunder, dass für die zweite Aufgabe nur 19 Schritte gebraucht werden
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 23.05.09, 17:37   #11 (permalink)
 
Registriert seit: 07.02.04
Foxalem Leistung: Facit NTK
Foxalem eine Nachricht über ICQ schicken
Likes: 0
Standard

Mhh.. nu hab ichs wohl kapiert. Ne frage hätt ich allerdings noch.
Ich hätte nun Ne möglichkeit mit der ich das evtl. schaffen könnte. Dafür müsstee ich den weg quasi einprogrammieren dasses auch dahinführt.

Wäre dass falsch? Also muss man wirklich logic ins programm einfügen damit dass programm dass von alleine schafft durch soll-ist-wert vergleiche und dadurch den kleinsten weg findet?

Mfg
Foxalem ist offline   Mit Zitat antworten
Alt 23.05.09, 19:07   #12 (permalink)
 
Registriert seit: 04.12.08
xpecs Leistung: Facit NTK
Likes: 0
Standard

Danke @ CDW
Du hast recht^^ Bin ich gar net drauf gekommen hehe

und verdammt -.- du hast wieder recht. Naja, es war gestern spät :] und ich habe das mit dem zählen nicht so genau genommen
xpecs ist offline   Mit Zitat antworten
Alt 24.05.09, 02:12   #13 (permalink)
CDW
Moderator
Themenstarter
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

Zitat:
Original von Foxalem
Ich hätte nun Ne möglichkeit mit der ich das evtl. schaffen könnte. Dafür müsstee ich den weg quasi einprogrammieren dasses auch dahinführt.

Wäre dass falsch?
Du meinst die Lösung hart zu kodieren ?
Das kannst Du machen. Ich hab allerdings jetzt noch eine Habofrage hinzugefügt, um "Handrechnungen" wirklich auszuschließen

Zitat:
Also muss man wirklich logic ins programm einfügen damit dass programm dass von alleine schafft durch soll-ist-wert vergleiche und dadurch den kleinsten weg findet?
Jep. Stichwort wäre hier z.B Backtracking und das Suchen aller Lösungen. Dann eben Anzahl der Schritte pro Lösung vergleichen. Möchte ich allerdings niemanden dazu zwingen, daher gibt es ja auch "Teilaufgaben".

@xpecs:
probiere mal mit Behälter A: 15l, B: 13l, Ziel: 20l



ein solver in Prolog   

SWI,GNU Prolog, Sicstus kompatibel:
nutzung:
solve([Bez:Maxvolume,Startvol, Bez:Maxvol,Starvol], Ziel, Loesung)
bsp:
solve([a:15:0,b:13:0],20,Solution).
Code:
:-use_module(library(lists)).

%Paramter: [Behaelter,Behaelder],[Ergebnis],Schritt
step(Tanks,[X:Max:0|T],empty(X)):-select(X:Max:_,Tanks,T).  %leere Eimer
step(Tanks,[X:Max:Max|T],fill(X)):-select(X:Max:_,Tanks,T). %fuelle Eimer

step(Tanks,[A:MaxA:NVolA,B:MaxB:NVolB],A:VolA>>B:VolB):-    %umfuellen
    select(A:MaxA:VolA,Tanks,[B:MaxB:VolB]),
    VolA>0,                                                 %umfuellen macht keinen Sinn, wenn A leer ist
    DifB is MaxB-VolB-VolA,                                 %Passt A komplett in B rein ?
    ((DifB>=0,NVolA=0,NVolB is VolB+VolA) ;                 %wenn nicht: Rest berechnen
    (DifB<0,NVolA is VolA-(MaxB-VolB),NVolB=MaxB)).

solve([_:_:VolA,_:_:VolB],Goal,_,[]):-Goal is VolA+VolB.    %Ziel erreicht?
solve(Tanks,Goal,States,[Step|Sol]):-                   
        step(Tanks,State,Step),sort(State,Sorted),          
        \+member(Sorted,States),                            %Zustand schon mal erreicht worden?
        solve(Sorted,Goal,[Sorted|States],Sol).
		
%Useraufruf, vorinitialisierungen
solve(Tanks,Goal,Sol):- solve(Tanks,Goal,Tanks,Sol).
optimierte Version   

nur noch Sicstus/SWI kompatibel
Code:
:-use_module(library(lists)).
:-use_module(library(assoc)).

%Paramter: [Behaelter,Behaelder],[Ergebnis],Schritt
step(Tanks,[X:Max:0|T],empty(X)):-select(X:Max:_,Tanks,T).  %leere Eimer
step(Tanks,[X:Max:Max|T],fill(X)):-select(X:Max:_,Tanks,T). %fuelle Eimer

step(Tanks,[A:MaxA:NVolA,B:MaxB:NVolB],A:VolA>>B:VolB):-    %umfuellen
    select(A:MaxA:VolA,Tanks,[B:MaxB:VolB]),
    VolA>0,                                                 %umfuellen macht keinen Sinn, wenn A leer ist
    DifB is MaxB-VolB-VolA,                                 %Passt A komplett in B rein ?
    ((DifB>=0,NVolA=0,NVolB is VolB+VolA) ;                 %wenn nicht: Rest berechnen
    (DifB<0,NVolA is VolA-(MaxB-VolB),NVolB=MaxB)).

solve([_:_:VolA,_:_:VolB],Goal,_,[]):-Goal is VolA+VolB.    %Ziel erreicht?
solve(Tanks,Goal,States,[Step|Sol]):-                   
        step(Tanks,State,Step),sort(State,Sorted),          
        \+get_assoc(Sorted,States,_),                       %Zustand schon mal erreicht worden?
	put_assoc(Sorted,States,_,NSts),                    %wenn nein, weitermachen
        solve(Sorted,Goal,NSts,Sol).
%Useraufruf, vorinitialisierungen
solve(Tanks,Goal,Sol):-empty_assoc(Assoc),                  %zustände in einem AVL Baum sichern:
	               put_assoc(Tanks,Assoc,_,NAssoc),     %da für größere Mengen schnellere Suche
                       solve(Tanks,Goal,NAssoc,Sol).
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 24.05.09, 14:07   #14 (permalink)
 
Registriert seit: 04.12.08
xpecs Leistung: Facit NTK
Likes: 0
Unhappy

@CDW
Zitat:
probiere mal mit Behälter A: 15l, B: 13l, Ziel: 20l
Wieso sollte ich das ausprobieren? Wie soll ich denn in einem 15l oder 13l Eimer 20 reinkriegen?^^
Versteh jetzt die Aufgabe nicht sorry^^
xpecs ist offline   Mit Zitat antworten
Alt 24.05.09, 14:18   #15 (permalink)
 
Registriert seit: 07.02.04
Foxalem Leistung: Facit NTK
Foxalem eine Nachricht über ICQ schicken
Likes: 0
Standard

Warum oder, und ist die Antwort
7l in Eimer A und 13 Liter in Eimer B, schon haste 20liter zusammen.

13 + 13 = 26
26 - 15 = 11
11+13 = 24
24 - 15 =9
9 + 13 = 22
22 - 15 = 7

7 + 13 = 20

Hoffe ich hab dir das Rätzel nich versaut, musste ja immerhin noch programmieren
Foxalem ist offline   Mit Zitat antworten
Antwort
   
- Anzeige -

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » Eimerproblem
Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61