Einf. in das symbolische Programmieren CIS, SS 2001, H.Leiss ================================================================= Abgabe: Dienstag, 19.6.01 in der Uebungsstunde. ----------------------------------------------- Aufgabe 7 (5 Punkte) --------- Das Praedikat quicksort/2 von Folie 31 (mit qusort/3) gibt bei Eingabe von ?- quicksort([1,3,4,2,5],Sortiert). die Antwort Sortiert = [1, 2, 3, 4, 5]. (Leider enthielt das Praedikat partition/4 der Folien 30/31 einen Syntaxfehler: Prolog erlaubt zwar X >= Z, aber nicht X <= Z. Daher muss man erstmal X <= Z durch Z >= X ersetzen! Das habe ich inzwischen korrigiert.) a) Aendere das Hilfspraedikat qusort/2 --ohne Verwendung von reverse/2 oder rev/3-- so, dass quicksort die Antwort in der umgekehrten Reihenfolge ausgibt, mit den grossen Zahlen am Anfang der Ergebnisliste. Hinweis: Ueberlege, was auf den Akkumulator muss, und in welcher Reihenfolge die grossen und kleinen Elemente sortiert werden sollten. b) Formuliere die Fallunterscheidung (nach Z=X) im Hilfspraedikat partition/4 mit Hilfe eines ! (cut). Aufgabe 8 (5 Punkte) --------- Aendere die Definition von weg/2 auf Folie 35 so, dass fuer einen (kreisfreien) Graphen kante/2 auf den natuerlichen Zahlen durch ?- weg(X,Y,W). alle X,Y,W gesucht werden, so dass X der Anfangs- und Y der Endpunkt eines Weges im Graphen ist, und W die Liste der Punkte, die auf diesem Weg durchlaufen werden (inklusive der Endpunkte). W soll also eine Liste der Form [X,....,Y] als Antwort liefern, wenn es einen Weg von X nach Y gibt. Weil am Donnerstag schon wieder ein Feiertag ist, gibt es etwas mehr zu tun: Aufgabe 9 (5 Punkte) --------- Schreibe ein Praedikat difference(Liste1,Liste2,Ergebnis), das bei Eingabe zweier Listen, Liste1 und Liste2, von variablenfreien Termen im dritten Argument, Ergebnis, eine Liste der Elemente ausgibt, die in Liste1 vorkommen, aber nicht in Liste2. Hinweis: Schreibe zuerst ein Hilfspraedikat, mit dem man feststellen kann, ob ein Term in einer Liste vorkommt (oder benutze ein entsprechendes Praedikat von SWI-Prolog, im Handbuch suchen!). Bem. Dass die Terme der Eingabelisten keine Variablen enthalten, soll nicht ueberprueft, sondern angenommen werden.