ubuntuusers.de

[swi Prolog] Programm soll Summe berechnen

Status: Gelöst | Ubuntu-Version: Kein Ubuntu
Antworten |

En_Passant

Anmeldungsdatum:
24. Juni 2011

Beiträge: 178

Guten Tag,

ich habe mit swi-Prolog zu programmieren begonnen und bin mit der ungewohnten Art der Programmierung noch nicht ganz im Reinen.

In meiner Wissensbasis stehen z.B. folgende Fakten:

basis(a, 5),
basis(b, 10),
basis(c, 20),

Erstes Atom im Faktum soll immer den Bezeichner angeben, zweites Atom immer dessen Zahl.

Nun suche ich eine Regel berechne(SUMME), welche mir z.B. auf die Anfrage ?- berechne(35) die kombinatorisch möglichen Summanden ausgibt, bzw. bestenfalls dessen Namen.

Im entsprechenden Beispiel müsste a+a+a+a+a+a+a eine gefundene Ausgabe sein! Nach langem Rumprobieren, muss ich leider zugeben, keinen Schimmer zu haben.

Vain

Avatar von Vain

Anmeldungsdatum:
12. April 2008

Beiträge: 2510

Servus,

Prolog brauche ich nie im Alltag, aber da es so eine schöne Übung ist, will ich’s mal versuchen.

Meine erste Vereinfachung wäre, die Bezeichner für die Werte wegzulassen. Zumindest vorübergehend. Das heißt, ich würde nur das hier schreiben:

basis(5).
basis(10).
basis(20).

Dann hast du ja in Prolog keine „Rückgabewerte“. Das heißt, dein „berechne“ muss zwei „Parameter“ erhalten. Da wäre mein Ansatz, das zu formulieren als: „Berechne 35, wobei die Summanden in der Liste L enthalten sind.“ Also „berechne(35, L).“. Die Hoffnung ist, dass Prolog dir dann die verschiedenen Lösungsmöglichkeiten für „L“ ausgibt.

Der einfache Fall (Rekursionsende):

berechne(E, [E]) :- basis(E).

Wenn der Wert „E“ direkt schon eine Basis ist, dann ist unser „L“ eine Liste mit genau einem Element, nämlich „E“.

Ansonsten haben wir es mit einem Wert „W“ zu tun und das hypothetische „L“ würde bestehen aus einem Kopf „K“ und Rest „R“. Dann:

berechne(W, [K | R]) :-
	% Der Listenkopf muss eine erlaubte Basis sein.
	basis(K),

	% Wir berechnen eine Zwischensumme N, die nicht negativ werden darf
	% (sonst bricht die Rekursion nie ab) und ein N von 0 wäre
	% uninteressant.
	N is W - K,
	N > 0,

	% Dann rekursiv: Bestimme die restlichen Summanden in der Liste R,
	% wobei sich diesmal alle Summanden nur noch zu N aufsummieren
	% müssen.
	berechne(N, R).

Insgesamt sieht das ganze Ding so aus:

berechne(E, [E]) :- basis(E).
berechne(W, [K | R]) :-
	basis(K),
	N is W - K,
	N > 0,
	berechne(N, R).

basis(5).
basis(10).
basis(20).

Ein paar Beispielabfragen sehen gut aus:

?- berechne(-10, L).
false.

?- berechne(0, L).
false.

?- berechne(19, L).
false.

?- berechne(20, L).
L = [20] ;
L = [5, 5, 10] ;
L = [5, 5, 5, 5] ;
L = [5, 10, 5] ;
L = [10, 10] ;
L = [10, 5, 5] ;
false.

(Das „false“ ganz am Ende heißt ja nur, dass keine weiteren Lösungen gefunden wurden.)

Ja, er liefert noch „5, 10, 5“ und „5, 5, 10“ als verschiedene Ergebnisse. Aber mein Code ist ja auch nur ein Ansatz. ☺

– Nachtrag: Es gibt zur Verhinderung „doppelter“ Ergebnisse eine ganz simple Lösung. Wenn du verstanden hast, wie der obige Code funktioniert, dann kommst du da auch locker selbst drauf. Will ja den Spaß nicht verderben.

En_Passant

(Themenstarter)

Anmeldungsdatum:
24. Juni 2011

Beiträge: 178

Danke für Deine Hilfe!

Vain schrieb:

– Nachtrag: Es gibt zur Verhinderung „doppelter“ Ergebnisse eine ganz simple Lösung. Wenn du verstanden hast, wie der obige Code funktioniert, dann kommst du da auch locker selbst drauf. Will ja den Spaß nicht verderben.

Ich habe verstanden, wie der Code funktioniert. Ich verstehe die Programme recht gut, nur fehlt mir das gewisse Intellektuelle, um selbst Lösungen zu entwickeln. Prolog verlangt mir wirklich vieles ab.

Ich habe nämlich wieder keinen Schimmer, wie ich doppelte Funde verhindern kann. Ich habe mich zwar mittlerweile befriedigend mit der Rekursion anfreunden können, dennoch fällt mir die rekursive Denkweise äußerst schwer.

Vain

Avatar von Vain

Anmeldungsdatum:
12. April 2008

Beiträge: 2510

En Passant schrieb:

nur fehlt mir das gewisse Intellektuelle, um selbst Lösungen zu entwickeln. Prolog verlangt mir wirklich vieles ab.

Keine Bange, ich muss meinen Kopf auch umdrehen, wenn ich Prolog anfasse. Finde aber, dass genau das das Schöne an der Übung ist. 😉

Was ist der Unterschied zwischen beispielsweise „5, 10, 5“ und „5, 5, 10“? Die eine Liste ist aufsteigend sortiert, die andere nicht. Da uns das bisherige Programm alle möglichen Permutationen ausspuckt, würde es reichen, nur die auszugeben, die sortiert sind: Die, die nicht sortiert sind, könnte man durch Sortierung in die sortierte Form überführen, wodurch sie äquivalent werden.

Ob eine Liste sortiert ist, kann man beispielsweise so umsetzen. Wir wollen sie ja nicht aktiv sortieren, sondern nur testen, ob sie es ist. Wenn Prolog anhand der folgenden Regeln für eine Liste ein „true“ ableiten kann, dann reicht das:

% Eine einelementige Liste ist immer sortiert.
sortiert([_]).

% Eine Liste mit mindestens zwei Elementen (R kann hier [] sein) ist
% dann sortiert, wenn K1 kleiner oder gleich K2 ist und die Restliste
% bestehend aus [K2 | R] auch sortiert ist.
sortiert([K1 | [K2 | R]]) :- K1 =< K2, sortiert([K2 | R]).

Und jetzt kann man „berechne()“ entsprechend erweitern, weil wir nur sortierte Ergebnisse haben wollen (das muss ganz ans Ende, weil „R“ schon unifiziert sein muss):

berechne(E, [E]) :- basis(E).
berechne(W, [K | R]) :-
	basis(K),
	N is W - K,
	N > 0,
	berechne(N, R),
	sortiert([K | R]).

(Beim nochmaligen Lesen bin ich mir nicht mehr sicher, ob die Lösung wirklich so „ganz simpel“ ist. Irgendwie muss man schon drauf kommen. Am Donnerstag fand ich das total naheliegend…)

En_Passant

(Themenstarter)

Anmeldungsdatum:
24. Juni 2011

Beiträge: 178

Vain schrieb:

Was ist der Unterschied zwischen beispielsweise „5, 10, 5“ und „5, 5, 10“? Die eine Liste ist aufsteigend sortiert, die andere nicht.

Ich habe nur diese beiden Sätze gelesen und mich dann an die Arbeit gemacht! ☺ Ich bin auf ein ähnlichen Quelltext gekommen. Lediglich ein paar syntaktische Unterschiede, semantisch jedoch - abgesehen vom Cut - ziemlich äquivalent.

sortiert([_]).
sortiert([ K | R]) :- R = [K2 | _], K =< K2, sortiert(R), !. 

(Beim nochmaligen Lesen bin ich mir nicht mehr sicher, ob die Lösung wirklich so „ganz simpel“ ist. Irgendwie muss man schon drauf kommen. Am Donnerstag fand ich das total naheliegend…)

Das war das Verwirrende. Da Du sagtest, es sei ganz simpel, bin ich von einer geringen Codeänderung ausgegangen. Ich zog es deshalb nicht in Betracht, eine weitere Regel zu definieren.

Du hast mir sehr geholfen, auch dahingehend, mein Verständnis für Prolog zu erweitern. Danke dafür!

Beste Grüße!

Zusatz:

Ich habe hier gleich noch den vollständigen Quelltext, mit dem ich meinem Ursprungsprogramm, wie ich es im ersten Beitrag gewünscht hatte, näher komme.

Mit der Regel gib_Bezeichner/2 gebe ich entsprechend die Bezeichner, sprich das erste Atom im Faktum basis/2 aus.

basis(a, 5).
basis(b, 10).
basis(c, 20).

sortiert([_]).
sortiert([K | R])               :- R = [K2 | _], 
                                   K =< K2, 
                                   sortiert(R), !. 

gib_Bezeichner(ListeB, ListeZ)  :- ListeB = [KB],
                                   ListeZ = [KZ],
                                   basis(KB, KZ). 
gib_Bezeichner(ListeB, ListeZ)  :- ListeB = [KB | RB],
                                   ListeZ = [KZ | RZ], 
                                   basis(KB, KZ), 
                                   gib_Bezeichner(RB, RZ).

berechne(E, [E])                :- basis(_, E).
berechne(W, [K | R])            :- basis(_, K), 
                                   N is W - K, 
                                   N > 0,
                                   berechne(N, R),
                                   sortiert([K | R]).

Nun gibt z.B. die Anfrage ?- berechne(15, X), gib_Bezeichner(Y, X) auch die entsprechenden Permutationen mit den "Bezeichnern".

Zusatz2:

Man benötigt die Regel gib_Bezeichner/2 eigentlich gar nicht. Ich habe berechne/2 entsprechend umgeschrieben und berechne2/2 genannt. Nun werden nur die Bezeichner ausgegeben.

berechne2(KZ, ListeB)           :- ListeB = [KB], basis(KB, KZ), _ = [KZ].
berechne2(W, ListeB)            :- ListeB = [KB | RB], basis(KB, KZ), _ = [KZ | _],  
                                   N is W - KZ, 
                                   N > 0,
                                   berechne(N, RB),
                                   sortiertB(ListeB).

Problem hierbei ist, dass auch die Regel sortiert/1 so umgeschrieben werden muss, dass sie die Bezeichner in der korrekten Folge erkennt. Dies schaffen wir durch die Bindung der Bezeichner an ihre Zahlen.

sortiertB([KB])                 :- basis(KB, KZ), _ = [KZ]. 
sortiertB([KB | RB])            :- RB = [KB2 | _], basis(KB, KZ), basis(KB2, KZ2),
                                   KZ =< KZ2, 
                                   sortiertB(RB), !. 
Antworten |