 |
|||
| HSG |
|
Problem des Monats CIX, April/Mai 2008
Auf der Insel Hohstaufia gibt es blaue, grüne und rote Chamäleons. Wenn sich zwei Chamäleons treffen, so ändern beide ihre Farbe in die dritte (nicht anwesende) Farbe. Die Frage ist, ob es (natürlich in Abhängigkeit von der Anfangszahl der Tiere) möglich ist, dass schließlich alle Chamäleons dieselbe Farbe besitzen (man gehe davon aus, dass sich tatsächlich immer nur genau zwei Chamäleons treffen und dass immer der gleiche Bestand an Tieren vorhanden ist)?
Problem 1
Löse das Problem für einen Anfangsbestand von 1 blauen, 2 grünen und 2 roten Chamäleons.
Problem 2
Löse das Problem für einen Anfangsbestand von 1 blauen, 2 grünen und 3 roten Chamäleons.
Problem 3
Löse das Problem für einen Anfangsbestand von 1 blauen, 3 grünen und 5 roten Chamäleons. Verallgemeinere, wenn möglich!
Prolog-Modellierung
% Zustand [2,2,1] bedeutet: 2 C. haben die erste Farbe (rot), 2 C. die zweite (grün) und 1 C. die dritte (blau)
next([X,Y,Z],[X1,Y1,Z1]) :- X>0,Y>0,X1 is X-1,Y1 is Y-1,Z1 is Z+2.
next([X,Y,Z],[X1,Y1,Z1]) :- X>0,Z>0,X1 is X-1,Z1 is Z-1,Y1 is Y+2.
next([X,Y,Z],[X1,Y1,Z1]) :- Y>0,Z>0,Y1 is Y-1,Z1 is Z-1,X1 is X+2.
tiefensuche(Start,Ziel,Loesung) :- tiefensuche(Start,[Start],Ziel,Loesung).
tiefensuche(Ziel,Pfad,Ziel,Loesung) :- Loesung = Pfad.
tiefensuche(KnotenA,Pfad,Ziel,Loesung) :- next(KnotenA,KnotenN),
not(member(KnotenN,Pfad)),
tiefensuche(KnotenN,[KnotenN|Pfad],Ziel,Loesung).
breitensuche(Start,Ziel,Loesung) :- breitensuche([Start],[],Ziel,Loesung).
breitensuche(Pfad,_,Ziel,Loesung) :- Pfad=[Ziel|_],Pfad=Loesung,!.
breitensuche(Pfad,Pfade,Ziel,Loesung) :- Pfad=[KnotenA|_],
findall([KnotenN|Pfad],
(next(KnotenA,KnotenN),not(member(KnotenN,Pfad))),
GefundenePfade),
append(Pfade,GefundenePfade,NeuePfade),
NeuePfade=[PfadN|RestPfade],
breitensuche(PfadN,RestPfade,Ziel,Loesung).
Graph zu Problem 1
Graph zu Problem 2
Graph zu Problem 3
