P1-WS04-MusterLoesung07.txt: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
fsrwiki_>1illig K (spam) |
fsrwiki_>Oddmuse Import K (link fix) |
||
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. | ||
Version vom 5. November 2007, 07:49 Uhr
% -*-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