H5 6.2

Benutzeravatar
scowli
Erstie
Erstie
Beiträge: 11
Registriert: 22. Nov 2007 23:48
Wohnort: Darmstadt

H5 6.2

Beitrag von scowli »

habe ein problem in der übung 5. und zwar geht es hierbei um die aufgabe 6.2 (pfade und backtracking), genauer um die hilfsprozedur 4 (eine prozedur, die für eine liste benachbarter kanten eines knotens alle möglichen pfade zurückgibt)
mir stellt sich jetzt die frage:
ich habe als paramater der funktion nur eine liste von kanten zu übergeben, von denen ein knoten bei allen kanten gleich ist und eine liste aller kanten, oder? also wenn ich mich auf das haus des nikolauses beziehe:

z.b. (define (procedure '((a b) (a c) (a e) )E ) ...).

kann mir einer helfen und sagen, was die prozedur für dieses beispiel ausspucken müsst, damit ich verstehe, was sie genau tun soll?!?!?

Schalli
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 24. Okt 2006 21:50
Wohnort: Bayern

Beitrag von Schalli »

Ich stehe vor genau dem selben Problem.

Allerdings heißt es in der Aufgabenstellung
Eine Prozedur, die für eine Liste benachbarter Kanten eines Knotens alle möglichen Pfade
zurückgibt (wechselseitige Rekursion)
was bedeutet, dass die Prozedur nur die Liste aller benachbarten Kanten eines Knotens übergeben bekommt, und nicht noch die Liste aller Kanten (im Fall Haus des Nikolaus die Liste E)

Also so in etwa:
(define (procedure '((a b) (a c) (a e)) ) ...).

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

Also ich habe das so verstanden: Du sollst eine Prozedur schreiben die einen Knoten und eine Liste von benachbarten Kanten des Knoten erhälst und dann alle Wege als Liste ausspuckt. Das ergibt auch nur dadurch Sinn, da der Graph ungerichtet ist.

So kannst du zum Beispiel als Liste der banchbarten Kanten des Knotens c die Liste '( (a c) (b c) (c e) (c d) ) erhalten. Nun sollen wir daraus die Pfaden generieren, also folgendes Ergebnis produzieren:

'( (c a) (c b) (c e) (c d) )

Also soll der Inhalt einer Kante so geändert, dass ein Knoten (hier c) von jeder Kante aus ein Startpunkt ist.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Beitrag von Demmi »

@Stumpf.Alex: Das hab ich genau so verstanden, allerdings finde ich das ein bisschen sinnfrei, weil ja laut Definition diese beiden equivalent sind:

Code: Alles auswählen

'((a b)(c b)(c a)) == '((a b)(b c)(c a))
Das zweite sieht halt nur besser (logischer) aus.

Meins funktioniert übrigens schon, allerdings muss ich flatten-once aus der dritten (?) Übung nehmen, damit es hübsch aussieht ;)

Benutzeravatar
Dominik
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 4. Okt 2007 09:40
Wohnort: Wiesbaden

Beitrag von Dominik »

ja, meins funtkioniert auch schon... nur siehts katastrophal aus und mein letzer schritt bleibt auf der strecke... jetzt muss ich nur noch rausfinden, wo du flatten-once benutzt hast :P

Benutzeravatar
scowli
Erstie
Erstie
Beiträge: 11
Registriert: 22. Nov 2007 23:48
Wohnort: Darmstadt

Beitrag von scowli »

ah ok, ich probiers gleich mal aus :wink:

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon »

Demmi ich hab dir mal ne PN Geschickt..

Bei mir funktioniert das ganze auch schon so halb. Krieg aber ohne flatten-once ungefähr eine Milliarden Unterlisten und mit hängt er mir seltsamerweise die letzte Kante ab und setzt sie in eine neue Liste:

(list
(list (list (list empty (list 'a 'b)) (list 'b 'c)) (list 'c 'd))
(list 'b 'd)
(list (list (list empty (list 'a 'b)) (list 'b 'd)) (list 'c 'd))
(list 'b 'c))

Das ist jetzt das Ergebnis von generate-path wenn ich das Beispiel aus dem Template nehme (mit a b c d e) und es mit 'a aufrufe..

Und das empty am Anfang muss ich auch noch rausfiltern..

Benutzeravatar
der Interpeter
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 30. Okt 2007 22:24

Beitrag von der Interpeter »

Ich krieg eine ziemlich eigenartige Liste mit insgesamt 54 Pfaden für den Anfangsknoten A heraus. Kann das stimmen?
Ich hab jetzt mal 10 Pfade davon handisch nachvollzogen und es war immerhin keine Kante doppelt und (noch) kein Pfad doppelt.

Wenn ich jetzt alle Pfade für alle möglichen Anfangsknoten suchen lasse wird das ja riesig, wer will denn die Liste kontrollieren?

Wie prüft ihr ob euer generate-path bzw. generate-all-paths macht was es soll?
I never comment my sourcecode. What's HARD to write must be HARD to read!

Stumpf.Alex
Nerd
Nerd
Beiträge: 643
Registriert: 1. Okt 2007 12:40
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Stumpf.Alex »

Also ich habe für generate-all-paths 88 raus ^^.

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Beitrag von taufrisch »

der Interpeter hat geschrieben:Ich krieg eine ziemlich eigenartige Liste mit insgesamt 54 Pfaden für den Anfangsknoten A heraus. Kann das stimmen?
Nein. :|

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon »

http://de.wikipedia.org/wiki/Haus_vom_Nikolaus

44 Lösungen laut Wikipedia, bzw 88 wenn spiegelbildliche Lösungen zugelassen sind ^^

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon »

Ich hätte auch mal noch ne Frage. Wie ist das Haus vom Nikolaus definiert:

1.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen.
2.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen und komme am Ende wieder am Ursprung raus.

Wenn man das Haus vom Nikolaus zeichnet trifft ja das zweite zu. Auf dem Aufgabenblatt steht davon nichts. Ich frage wegen folgendem: Wenn man den Beispielgraph aus dem Template nimmt, gibt es, wenn man vom Knoten b ausgeht 2 Lösungen bei Definition 1, aber keine bei Definition 2. Was ist richtig?

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Beitrag von Krümelmonster »

Kann mir jemand sagen, was bei Aufgabe 6.2
die vierte Hilfsprozedur machen soll?

Wenn es einige schon fertig haben,
wissen sie ja bestimmt was sie machen
soll.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Beitrag von taufrisch »

s!mon hat geschrieben:Ich hätte auch mal noch ne Frage. Wie ist das Haus vom Nikolaus definiert:

1.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen.
Genau :D
s!mon hat geschrieben:2.Durchlaufe alle Kanten des Graphes ohne eine zwei Mal zu durchlaufen und komme am Ende wieder am Ursprung raus.
Das geht nicht. :wink:
s!mon hat geschrieben:Wenn man das Haus vom Nikolaus zeichnet trifft ja das zweite zu.
Das mußt du mir mal zeigen... :shock:

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon »

http://upload.wikimedia.org/wikipedia/c ... kolaus.gif

Links oben zb

Du fängst rechts unten an das Haus zu zeichnen und kommst am Ende wieder rechts unten an..

Antworten

Zurück zu „Archiv“