3Listen, Rekursion
Lösungen
3.1Familienbeziehungen
Ergänzen Sie die Familienbeziehungen aus der Übung 1.1 durch:
vorfahr( V, X ) /* V ist Vorfahr von X */
nachkomme( N, X) /* N ist ein Nachkomme von X */
verwandt( X, Y) /* X und Y sind verwandt */
Lösung 3.1
3.2Fakultät & Fibonacci
Implementieren Sie die folgenden Funktionen als rekursive Relationen:
fakultaet( N, F) /* F ist die Fakultät von N */
fibo(N, F) /* F ist die N-te Fibonacci Zahl: */
/* F(n) = F(n-1) + F(n-2), F(0) = F(1) = 1 */
Lösung 3.2
3.3Listenmanipulation
Implementieren Sie einige der folgenden Prädikate:
member(X, Y) /* X ist Element der Liste Y */
append( X, Y, Z)/* Liste Z ist Liste Y "plus" Liste X */
reverse( X, Y)/* Y ist die umgekehrte Liste zu X */
/* Implementierung mittels append */
rev( X, Y)/* Y ist die umgekehrte Liste zu X */
/* Impl.: akkumulierte Parameter */
min_list( X, Y)/* Y ist das Minimum der Elemente der Liste X */
sum( X, S) /* S = Summe der Elemente der Liste X */
length( X, L)/* L ist die Länge der Liste X */
positive( X, Y)/* Y is die Liste der positiven Elemente (Zahlen) der Liste X */
Wenn Sie Lust haben, implementieren Sie auch noch:
flatten( X, Y)
/* Y ist Liste der atomaren Elemente, die in der Liste X oder in deren Sublisten vorkommen.
Bsp: flatten( [a, [b, [c, d]], a], [a, b, c, d, a]). */
set( X, Y)
/* Y ist die Liste der Elemente von X ohne Wiederholungen.
Bsp.: set( [1, 1, 2], [1,2]) */
sort( X, Y)
/* Y ist die geordnete Liste der Elemente von X.
(Ordnungsrekation ?).
Implementierung mittels "Insert sort":
Im k-ten Schritt sind X1, X2, ... Xk bereits als
Y1, Y2, ... Yk geordnet. Nun wird Xk+1 in die Reihe
Y1, Y2, ... Yk an die richtige Stelle eingefügt. */
Lösung 3.3
3.4Ein komplexes Velo
Eine hierarchische Struktur kann durch folgende Fakten beschrieben werden:
struktur( k, [k1, k2, ..., kn])
/* Komponente k besteht aus Teilkomponenten k1, .., kn */
element( k)
/* Komponente k ist elementar, d.h. nicht weiter zerlegbar */
Schreiben Sie die folgenden Prädikate:
teile( K, E)
/* E ist die Liste der elementaren Objekte, aus denen K besteht. */
teil( K, SubK)
/* SubK ist eine elementare oder zusammengesetzte Komponente, die in K direkt oder indirekt enthalten ist. */
Testen Sie Ihre Lösungen am Beispiel der Zusammensetzung eines Velos:
struktur( velo, [rahmen, rad, rad, antrieb]).
struktur( rahmen, [vorderrahmen, hinterrahmen]).
struktur( vorderrahmen, [lenker, gabel]).
struktur( hinterrahmen, [hauptrahmen, sattel]).
struktur( rad, [nabe, speichen, felge, reifen]).
element( lenker).
element( gabel).
element( hauptrahmen).
element( sattel).
element( nabe).
element( speichen).
element( felge).
element( reifen).
element( antrieb).
Bemerkung: Jeder Fakt muss im Programm auf einer neuen Zeile stehen.