P1-WS04-MusterLoesung07.txt - Versionsgeschichte

PatrickFey: 2 Versionen

2007-11-05T05:50:07Z

2 Versionen

← Nächstältere Version		Version vom 5. November 2007, 05:50 Uhr
(kein Unterschied)

fsrwiki_>Oddmuse Import: link fix

2007-11-05T05:49:25Z

link fix

← Nächstältere Version		Version vom 5. November 2007, 05:49 Uhr
Zeile 68:		Zeile 68:

	% (d) tore_durchschnitt(+Mannschaft,		% (d) tore_durchschnitt(+Mannschaft,
	% ?Treffer_Durchschnitt, ?Gegentreffer_Durchschnitt)		% ?[[Treffer_Durchschnitt]], ?[[Gegentreffer_Durchschnitt]])
	% berechnet die durchschnittliche Zahl von Treffern und		% berechnet die durchschnittliche Zahl von Treffern und
	% Gegentreffern pro Spiel einer Mannschaft (unter Benutzung des		% Gegentreffern pro Spiel einer Mannschaft (unter Benutzung des
Zeile 74:		Zeile 74:
	% length/2 für Listen):		% length/2 für Listen):

	tore_durchschnitt(Mannschaft, Treffer_Durchschnitt, Gegentreffer_Durchschnitt) :-		tore_durchschnitt(Mannschaft, [[Treffer_Durchschnitt]], [[Gegentreffer_Durchschnitt]]) :-
	trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),		trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
	sum(Trefferliste, Treffer),		sum(Trefferliste, Treffer),
	sum(Gegentrefferliste, Gegentreffer),		sum(Gegentrefferliste, Gegentreffer),
	length(Trefferliste, AnzahlSpiele),		length(Trefferliste, [[AnzahlSpiele]]),
	Treffer_Durchschnitt is Treffer / AnzahlSpiele,		[[Treffer_Durchschnitt]] is Treffer / [[AnzahlSpiele]],
	Gegentreffer_Durchschnitt is Gegentreffer / AnzahlSpiele.		[[Gegentreffer_Durchschnitt]] is Gegentreffer / [[AnzahlSpiele]].

	% (e) punkte(+Mannschaft, ?Plus, ?Minus)		% (e) punkte(+Mannschaft, ?Plus, ?Minus)
Zeile 92:		Zeile 92:

	punkte(Mannschaft, 1, 1) :-		punkte(Mannschaft, 1, 1) :-
	tore(Mannschaft, Unentschieden_Treffer, Unentschieden_Treffer).		tore(Mannschaft, [[Unentschieden_Treffer]], [[Unentschieden_Treffer]]).

	punkte(Mannschaft, 0, 2) :-		punkte(Mannschaft, 0, 2) :-
Zeile 153:		Zeile 153:

	% schlage_wort_nach(?Deutsch, ?Englisch, ?Woerterbuch)		% schlage_wort_nach(?Deutsch, ?Englisch, ?Woerterbuch)
	% sucht Deutsch/Englisch Wortpaar in Woerterbuch (einer Liste von		% sucht Deutsch[[/Englisch]] Wortpaar in Woerterbuch (einer Liste von
	% "Paaren", wobei letzteres lt. Aufgabenblatt Listen mit zwei		% "Paaren", wobei letzteres lt. Aufgabenblatt Listen mit zwei
	% Elementen sind).		% Elementen sind).
Zeile 174:		Zeile 174:

	uebersetzung([], []).		uebersetzung([], []).
	uebersetzung([DeutschesWort\|RestDeutsch],		uebersetzung([[[DeutschesWort]]\|[[RestDeutsch]]],
	[EnglischesWort\|RestEnglisch]) :-		[[[EnglischesWort]]\|[[RestEnglisch]]]) :-
	schlage_wort_nach(DeutschesWort, EnglischesWort),		schlage_wort_nach([[DeutschesWort]], [[EnglischesWort]]),
	uebersetzung(RestDeutsch, RestEnglisch).		uebersetzung([[RestDeutsch]], [[RestEnglisch]]).

	% Tests zeigen was passiert, wenn mehrer Wörter gleich übersetzt sind;		% Tests zeigen was passiert, wenn mehrer Wörter gleich übersetzt sind;
Zeile 218:		Zeile 218:
	suffix(S, [_\|X]) :- suffix(S, X).		suffix(S, [_\|X]) :- suffix(S, X).

	% Anfragen, bei denen nur der Präfix/Suffix instanziiert sind,		% Anfragen, bei denen nur der Präfix[[/Suffix]] instanziiert sind,
	% terminieren, aber geben nur eine Lösung, bei der die gesamte		% terminieren, aber geben nur eine Lösung, bei der die gesamte
	% Restliste durch eine Variable dargestellt wird:		% Restliste durch eine Variable dargestellt wird:
Zeile 245:		Zeile 245:
	% Hierfür muß wiederum lediglich der Rekursionsabschluß so		% Hierfür muß wiederum lediglich der Rekursionsabschluß so
	% geändert werden, daß die Liste selbst mindestens ein Element		% geändert werden, daß die Liste selbst mindestens ein Element
	% mehr als der Präfix/Suffix hat (hier als Varianten der Prädikate		% mehr als der Präfix[[/Suffix]] hat (hier als Varianten der Prädikate
	% aus (b), analog auch für die Originale aus (a) machbar):		% aus (b), analog auch für die Originale aus (a) machbar):

Zeile 285:		Zeile 285:
	% jetzt brauchen wir ein Hilfsprädikat, um rekursiv die Liste		% jetzt brauchen wir ein Hilfsprädikat, um rekursiv die Liste
	% durchzugehen und die Worthäufigkeiten zu bestimmen:		% durchzugehen und die Worthäufigkeiten zu bestimmen:
	zaehle_woerter(Woerter, Haeufigkeiten_Roh),		zaehle_woerter(Woerter, [[Haeufigkeiten_Roh]]),
	% anschließend ist das Ergebnis noch nach den Wörtern sortiert,		% anschließend ist das Ergebnis noch nach den Wörtern sortiert,
	% nicht wie gewünscht zuerst nach den Häufigkeiten, aber das ist		% nicht wie gewünscht zuerst nach den Häufigkeiten, aber das ist
	% schnell erledigt:		% schnell erledigt:
	sort(Haeufigkeiten_Roh, Haeufigkeiten).		sort([[Haeufigkeiten_Roh]], Haeufigkeiten).

	% zaehle_woerter/2 bekommt die sortierte Liste der Wörter und soll		% zaehle_woerter/2 bekommt die sortierte Liste der Wörter und soll
Zeile 315:		Zeile 315:
	% Rekursionsabschluß / Zählen beenden, wenn man auf ein anderes Wort		% Rekursionsabschluß / Zählen beenden, wenn man auf ein anderes Wort
	% trifft (und _nur_ dann):		% trifft (und _nur_ dann):
	zaehle_wort([Wort,NaechstesWort\|Woerter], Wort, 1, [NaechstesWort\|Woerter]) :-		zaehle_wort([Wort,[[NaechstesWort]]\|Woerter], Wort, 1, [[[NaechstesWort]]\|Woerter]) :-
	Wort \= NaechstesWort.		Wort \= [[NaechstesWort]].

	% Rekursion falls Wort noch mehrfach in der Liste - ein Vorkommnis		% Rekursion falls Wort noch mehrfach in der Liste - ein Vorkommnis
	% wegnehmen und nach diesem Wort weitersuchen/zählen, rekursiv Anzahl		% wegnehmen und nach diesem Wort weitersuchen/zählen, rekursiv Anzahl
	% um einen erhöhen.		% um einen erhöhen.
	zaehle_wort([Wort,Wort\|Woerter], Wort, Anzahl, RestWoerter) :-		zaehle_wort([Wort,Wort\|Woerter], Wort, Anzahl, [[RestWoerter]]) :-
	zaehle_wort([Wort\|Woerter], Wort, Nochanzahl, RestWoerter),		zaehle_wort([Wort\|Woerter], Wort, Nochanzahl, [[RestWoerter]]),
	Anzahl is Nochanzahl + 1.		Anzahl is Nochanzahl + 1.

fsrwiki_>1illig: spam

2006-12-22T05:38:11Z

spam

Neue Seite

<pre>
% -*-prolog-*-
%
% P1 Übungen WS2004/2005
% Musterlösung Blatt 7 (Hans Meine)
%
%---------------------------------------------------------------------
% 1. Datenaggregation
%---------------------------------------------------------------------
%
% Beispieldaten von Aufgabenblatt:

spiel(4,kiel,magdeburg,30,28).
spiel(4,lemgo,essen,27,23).
spiel(4,minden,nordhorn,32,28).
spiel(5,solingen,schwerin,29,32).
spiel(5,nordhorn,lemgo,20,21).
spiel(5,eisenach,wetzlar,28,34).

% (a) sum(+Liste,?Summe)
% berechnet die arithmetische Summe der Elemente einer Liste

sum([], 0).
sum([Kopf|Rest], Summe) :-
sum(Rest, Restsumme),
Summe is Kopf + Restsumme.

% (b) tore(?Mannschaft,?Treffer,?Gegentreffer)
% bestimmt eigene und gegenerische Tore berechnet, unabhängig
% davon, ob das Spiel zu Hause oder auswärts stattfand.

tore(Mannschaft, Treffer, Gegentreffer) :- % Heimspiel
spiel(_, Mannschaft, _, Treffer, Gegentreffer).

tore(Mannschaft, Treffer, Gegentreffer) :- % Auswärtsspiel
spiel(_, _, Mannschaft, Gegentreffer, Treffer).

% (c) tor_verhaeltnis(+Mannschaft, ?Treffer, ?Gegentreffer)
% berechnet Summe aller Tore bzw. Gegentore in allen Spielen der
% Mannschaft, indem alle Ergebnisse in Listen gesammelt und mit
% dem sum/2 aus (a) aufaddiert werden:

tor_verhaeltnis_1(Mannschaft, Treffer, Gegentreffer) :-
findall(Tore, tore(Mannschaft, Tore, _), Trefferliste),
sum(Trefferliste, Treffer),
findall(Gegentore, tore(Mannschaft, _, Gegentore), Gegentrefferliste),
sum(Gegentrefferliste, Gegentreffer).

% (Wie das + im dokumentierten Prädikatskopf schon andeutet, muß
% Mannschaft instanziiert werden, damit findall nur die Spiele
% einer Mannschaft findet.)
%
% Da (d) so ähnlich gelöst werden kann, bilden wir noch ein
% Hilfsprädikat:
% trefferlisten(+Mannschaft, ?Trefferliste, ?Gegentrefferliste)
% bildet die Listen aller Treffer beziehungsweise aller Gegentreffer:

trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste) :-
findall(Tore, tore(Mannschaft, Tore, _), Trefferliste),
findall(Gegentore, tore(Mannschaft, _, Gegentore), Gegentrefferliste).

% ..damit kann tor_verhaeltnis/3 etwas kürzer formuliert werden:

tor_verhaeltnis(Mannschaft, Treffer, Gegentreffer) :-
trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
sum(Trefferliste, Treffer),
sum(Gegentrefferliste, Gegentreffer).

% (d) tore_durchschnitt(+Mannschaft,
% ?Treffer_Durchschnitt, ?Gegentreffer_Durchschnitt)
% berechnet die durchschnittliche Zahl von Treffern und
% Gegentreffern pro Spiel einer Mannschaft (unter Benutzung des
% eben definierten trefferlisten/3-Prädikats und des eingebauten
% length/2 für Listen):

tore_durchschnitt(Mannschaft, Treffer_Durchschnitt, Gegentreffer_Durchschnitt) :-
trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
sum(Trefferliste, Treffer),
sum(Gegentrefferliste, Gegentreffer),
length(Trefferliste, AnzahlSpiele),
Treffer_Durchschnitt is Treffer / AnzahlSpiele,
Gegentreffer_Durchschnitt is Gegentreffer / AnzahlSpiele.

% (e) punkte(+Mannschaft, ?Plus, ?Minus)
% berechnet die in einem Spiel von einer Mannschaft erzielten
% Tabellenpunkte, unabhängig davon, ob das Spiel zu Hause oder
% auswä rts stattfand:

punkte(Mannschaft, 2, 0) :-
tore(Mannschaft, Treffer, Gegentreffer),
Treffer > Gegentreffer.

punkte(Mannschaft, 1, 1) :-
tore(Mannschaft, Unentschieden_Treffer, Unentschieden_Treffer).

punkte(Mannschaft, 0, 2) :-
tore(Mannschaft, Treffer, Gegentreffer),
Treffer < Gegentreffer.

% (f) punkte_verhaeltnis(+Mannschaft, ?Plus, ?Minus)
% errechnet das das Punkteverhältnis aus allen Spielen einer
% Mannschaft.

punkte_verhaeltnis(Mannschaft, Plus, Minus) :-
findall(Plus, punkte(Mannschaft, Plus, _), Pluspunkte),
sum(Pluspunkte, Plus),
findall(Minus, punkte(Mannschaft, _, Minus), Minuspunkte),
sum(Minuspunkte, Minus).

% (g) Man müßte tore/3 und punkte/3 um jeweils eine Argumentstelle für
% den Spieltag und/oder Spieltyp (heimspiel/auswaerts) erweitern,
% ebenso für alle darauf aufbauenden Prädikate, die zur Auswertung
% benötigt werden, und anschließend die findall-Aufrufe in diesen
% Prädikaten dementsprechend um die Bedingungen erweitern, z.B.

punkte_verhaeltnis_spieltyp(Mannschaft, Plus, Minus, Spieltyp) :-
findall(Plus, punkte(Mannschaft, Plus, _, Spieltyp), Pluspunkte),
sum(Pluspunkte, Plus),
findall(Minus, punkte(Mannschaft, _, Minus, Spieltyp), Minuspunkte),
sum(Minuspunkte, Minus).

% wobei punkte/4 aus sechs Regeln der folgenden Form besteht:

punkte(Mannschaft, 2, 0, heimspiel) :-
spiel(_, Mannschaft, _, Treffer, Gegentreffer),
Treffer > Gegentreffer.

punkte(Mannschaft, 2, 0, auswaerts) :-
spiel(_, _, Mannschaft, Gegentreffer, Treffer),
Treffer > Gegentreffer.

% Die Eingrenzung auf einen Saisonteil kann besonders elegant
% erfolgen, wenn man ein Hilfsprädikat definiert wie:

zeitraum(Tag, erste_saisonhaelfte) :- Tag < 18.
zeitraum(Tag, zweite_saisonhaelfte) :- Tag >= 18.
zeitraum(_, ganze_saison).

% damit können dann Anfragen nach beliebigen Zeiträumen ermöglicht
% werden, wie folgt skizziert:

punkte_verhaeltnis_zeitraum(Mannschaft, Plus, Minus, Zeitraum) :-
findall(Plus, (punkte_tag(Mannschaft, Plus, _, Plustag),
zeitraum(Plustag, Zeitraum)), Pluspunkte),
sum(Pluspunkte, Plus),
findall(Minus, (punkte_tag(Mannschaft, Minus, _, Minustag),
zeitraum(Minustag, Zeitraum)), Minuspunkte),
sum(Minuspunkte, Minus).

%---------------------------------------------------------------------
% 2. Umkodieren
%---------------------------------------------------------------------

% schlage_wort_nach(?Deutsch, ?Englisch, ?Woerterbuch)
% sucht Deutsch/Englisch Wortpaar in Woerterbuch (einer Liste von
% "Paaren", wobei letzteres lt. Aufgabenblatt Listen mit zwei
% Elementen sind).

schlage_wort_nach(Deutsch, Englisch, [[Deutsch, Englisch]|_]).
schlage_wort_nach(Deutsch, Englisch, [_|Woerterbuch]) :-
schlage_wort_nach(Deutsch, Englisch, Woerterbuch).

% schlage_wort_nach(?Deutsch, ?Englisch)
% benutzt ein vorgegebenes Woerterbuch, um ein Wort nachzuschlagen

schlage_wort_nach(Deutsch, Englisch) :-
schlage_wort_nach(Deutsch, Englisch,
[[hund,dog], [mann,man], [frau,woman], [katze,cat],
[die,the], [der,the], [schlaeft,sleeps]]).

% uebersetzung(?Deutsch, ?Englisch)
% kann in beiden Richtungen auf primitive Weise übersetzen, ruft
% einfach auf rekursive Weise auf jedem Wort schlage_wort_nach/2 auf.

uebersetzung([], []).
uebersetzung([DeutschesWort|RestDeutsch],
[EnglischesWort|RestEnglisch]) :-
schlage_wort_nach(DeutschesWort, EnglischesWort),
uebersetzung(RestDeutsch, RestEnglisch).

% Tests zeigen was passiert, wenn mehrer Wörter gleich übersetzt sind;
% es werden einfach alle Alternativen ausgegeben:

% ?- uebersetzung(Deutsch, [the, dog, sleeps]).
% Deutsch = [die, hund, schlaeft] ;
% Deutsch = [der, hund, schlaeft] ;
% No

% Wenn man unbekannte Wörter behandeln will, kann man natuerlich
% einfach einen Fakt hinzufügen, der das Wort unübersetzt läßt:

schlage_wort_nach(Wort, Wort, []).

% Jetzt funktioniert zwar die folgende Anfrage:

% ?- uebersetzung([der, hund, schlaeft, gut], X).
% X = [the, dog, sleeps, gut]

% aber alternative Anfragen führen zu Unglück:
% X = [the, dog, sleeps, gut] ;
% X = [the, dog, schlaeft, gut] ;
% X = [the, hund, sleeps, gut] ;
% X = [the, hund, schlaeft, gut] ;
% ...

%---------------------------------------------------------------------
% 3. Listenmanipulation
%---------------------------------------------------------------------

% (a) Schreiben Sie zwei Prädikate prefix/2 und suffix/2, die
% überprüfen, ob eine Liste Anfangs- bzw. Endstück einer zweiten
% Liste ist.

prefix([], _).
prefix([E|R], [E|X]) :- prefix(R, X).

suffix(X, X).
suffix(S, [_|X]) :- suffix(S, X).

% Anfragen, bei denen nur der Präfix/Suffix instanziiert sind,
% terminieren, aber geben nur eine Lösung, bei der die gesamte
% Restliste durch eine Variable dargestellt wird:

% ?- prefix([a,b,c],X).
% X = [a, b, c|_G232] ;
% No

% (b) Implementieren Sie eine Variante von prefix/2 bzw. suffix/2, bei
% denen die leere Liste nicht zur Lösungsmenge gehört.

% Hierfür muß lediglich der Rekursionsabschluß dementsprechend
% geändert werden:

prefix_nonempty([E], [E|_]).
prefix_nonempty([E|R], [E|X]) :- prefix_nonempty(R, X).

suffix_nonempty([E|R], [E|R]).
suffix_nonempty(S, [_|X]) :- suffix_nonempty(S, X).

% (c) Implementieren Sie eine weitere Variante der beiden Prädikate,
% die ausschließlich echte Präfixe bzw. Suffixe ermittelt. Echt
% sei ein Präfix bzw. Suffix einer Liste, wenn es ungleich der
% Liste selbst ist (vgl. Teilmenge <-> echte Teilmenge).

% Hierfür muß wiederum lediglich der Rekursionsabschluß so
% geändert werden, daß die Liste selbst mindestens ein Element
% mehr als der Präfix/Suffix hat (hier als Varianten der Prädikate
% aus (b), analog auch für die Originale aus (a) machbar):

real_prefix([E], [E,_|_]).
real_prefix([E|R], [E|X]) :- real_prefix(R, X).

real_suffix([E|R], [_,E|R]).
real_suffix(S, [_|X]) :- real_suffix(S, X).

% (d) Vergleichen Sie Unterschiede und Gemeinsamkeiten zwischen den
% Prädikaten prefix/2, suffix/2 und append/3. Wie lassen sich die
% Gemeinsamkeiten bei der Definition der Prädikate ausnutzen?

% Die Beziehungen können am einfachsten durch die folgenden
% Prädikatsdefinitionen ausgedrückt werden:

prefix_by_append(Prefix, List) :-
append(Prefix, _, List).

suffix_by_append(Suffix, List) :-
append(_, Suffix, List).

% Diese Prädikatsdefinitionen verhalten sich in jeder Hinsicht wie
% die einfachsten Prädikate aus (a).

%---------------------------------------------------------------------
% 4. Häufigkeitswörterbuch
%---------------------------------------------------------------------

haeufigkeiten(Text, Haeufigkeiten) :-
% zuerst benutzen wir flatten, weil uns die verschachtelte
% Struktur der Text-Liste nicht interessiert, im Gegenteil bei der
% Rekursion sogar stört:
flatten(Text, Wortliste),
% anschließend sortieren wir alle Woerter, damit unsere
% Zählaufgabe sich darauf beschränkt, Sequenzen von direkt
% aufeinanderfolgenden Wörtern zu zählen:
msort(Wortliste, Woerter),
% jetzt brauchen wir ein Hilfsprädikat, um rekursiv die Liste
% durchzugehen und die Worthäufigkeiten zu bestimmen:
zaehle_woerter(Woerter, Haeufigkeiten_Roh),
% anschließend ist das Ergebnis noch nach den Wörtern sortiert,
% nicht wie gewünscht zuerst nach den Häufigkeiten, aber das ist
% schnell erledigt:
sort(Haeufigkeiten_Roh, Haeufigkeiten).

% zaehle_woerter/2 bekommt die sortierte Liste der Wörter und soll
% Sequenzen von gleichen Wörtern zählen. Hierfür verwenden wir ein
% weiteres Hilfsprädikat, das alle aufeinanderfolgenden Vorkommnisse
% des gleichen Wortes zusammenfaßt und rufen dieses rekursiv für jedes
% neue Wort auf. Mit den Ergebnissen des Hilfsprädikats bauen wir die
% Liste mit den Häufigkeiten auf:

zaehle_woerter([], []).
zaehle_woerter(Woerter, [[Anzahl, Wort]|Haeufigkeiten]) :-
zaehle_wort(Woerter, Wort, Anzahl, Restwoerter),
zaehle_woerter(Restwoerter, Haeufigkeiten).

% zaehle_wort(Wortliste, Wort, Anzahl, Restliste)
% nimmt das erste Wort aus der Wortliste und zählt die folgenden
% Vorkommnisse des gleichen Wortes. Restliste wird mit dem Suffix der
% Wortliste unifiziert, der bleibt wenn alle Vorkommnisse von <Wort>
% entfernt wurden.

% Rekursionsabschluß (nötig, weil die folgenden Regeln nur auf Listen
% mit mindestens zwei Elementen angewendet werden können)
zaehle_wort([Wort], Wort, 1, []).

% Rekursionsabschluß / Zählen beenden, wenn man auf ein anderes Wort
% trifft (und _nur_ dann):
zaehle_wort([Wort,NaechstesWort|Woerter], Wort, 1, [NaechstesWort|Woerter]) :-
Wort \= NaechstesWort.

% Rekursion falls Wort noch mehrfach in der Liste - ein Vorkommnis
% wegnehmen und nach diesem Wort weitersuchen/zählen, rekursiv Anzahl
% um einen erhöhen.
zaehle_wort([Wort,Wort|Woerter], Wort, Anzahl, RestWoerter) :-
zaehle_wort([Wort|Woerter], Wort, Nochanzahl, RestWoerter),
Anzahl is Nochanzahl + 1.

% Test der Prädikate anhand des "Textes" vom Aufgabenblatt mit Hilfe
% der angegebenen Definition

portray(X) :- write_term(X,[max_depth(30)]).

% und formatiert:

% ?- haeufigkeiten(
% | [[wenn, hinter, fliegen, fliegen, fliegen, fliegen, fliegen, nach],
% | [blaukraut, bleibt, blaukraut, und, brautkleid, bleibt, brautkleid],
% | [wenn, du, denkst, du, denkst, denkst, du, nur, du, denkst]],
% | Haeufigkeiten).
%
% Haeufigkeiten = [[1, hinter],
% [1, nach],
% [1, nur],
% [1, und],
% [2, blaukraut],
% [2, bleibt],
% [2, brautkleid],
% [2, wenn],
% [4, denkst],
% [4, du],
% [5, fliegen]] ;
%
% No

</pre>