binaer-mobile 11.5

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

binaer-mobile 11.5
hat diese aufgabe schon jemand gemacht?

ich hab probleme schon bei total-weight, weil ich nicht weiss, wie ich rausfinden kann, ob ein ast schon am ende ist oder ob da nochmal ein weiteres mobile dranhaengt. kann mir jemand weiterhelfen?

thx,
-steppenwolf

3

Genau da häng ich auch… meiner Meinung nach braucht man noch ne Funktion Branch? und eine Funktion Mobile? um zu pruefen, wo man gerade ist.

4

Hier meine Lösung. total-weight lässt sich wunderbar rekursiv implementieren!

[CODE]; Aus der Angabe
(define (make-mobile l-branch r-branch) (list l-branch r-branch))
(define (make-branch length mobile) (list length mobile))

; a)
(define left-branch car)
(define right-branch cadr)
(define branch-length car)
(define branch-mobile cadr)

; b)
(define (total-weight mobile)
(if (list? mobile)
(+ (total-weight (branch-mobile (left-branch mobile))) (total-weight (branch-mobile (right-branch mobile))))
mobile))

; c)
(define (is-balanced? mobile)
(or (not (list? mobile))
(eq? (* (branch-length (left-branch mobile)) (total-weight (branch-mobile (left-branch mobile))))
(* (branch-length (right-branch mobile)) (total-weight (branch-mobile (right-branch mobile)))))))[/CODE]

d) Änderungen:

  • in den Funktionen right-branch und branch-mobile cadr durch cdr ersetzen
  • in den Funktionen total-weight und is-balanced list? durch pair? ersetzen
5

Hallo,

ich glaube die c) stimmt nicht ganz. Man soll nicht nur prüfen, ob das Mobile insgesamt ausbalanciert ist, sondern man soll auch die Teilmobile prüfen. D.h. man braucht noch einmal einen Satz rekursiver Aufrufe um den Rest auf Ausbalanciertheit zu prüfen.

Das sieht dann mit Krulls Ansatz und meinem Gewurschtel drum herum ungefähr so aus:

(define (is-balanced? mobile)
  (if (number? mobile) #t
     (if (eq? (* (branch-length (left-branch mobile)) (total-weight (branch-mobile (left-branch mobile))))
              (* (branch-length (right-branch mobile)) (total-weight (branch-mobile (right-branch mobile)))))
         
         (begin
           (is-balanced? (branch-mobile (left-branch mobile)))
           (is-balanced? (branch-mobile (right-branch mobile))))
              #f)
     )
  )

Und wenn ich jetzt in meiner geistigen Umnachtung nichts übersehen habe, dann sollte das sogar funktionieren.

6

Hast recht, hatte da einen Teilsatz übersehen:

Denke aber es reicht dann aus zu schreiben:

(define (is-balanced? mobile) (or (not (list? mobile)) (and (eq? (* (branch-length (left-branch mobile)) (total-weight (branch-mobile (left-branch mobile)))) (* (branch-length (right-branch mobile)) (total-weight (branch-mobile (right-branch mobile))))) (is-balanced? (left-branch mobile)) (is-balanced? (right-branch mobile)))))

7

Ja, gut, das if-Konstrukt ist überflüssig, aber ich werde mich nie daran gewöhnen, irgendwas ohne if zu schreiben. :slight_smile:

8

TheVoid

dein Zeugs ist IMO falsch.
Was du dir unter 'begin ’ vorstellst würd ich gern wissen, warscheinlich einfach ein typischen ‘and’
‘begin’ wertet die Parameter(heissen die Dinger in Scheme überhaupt so) aus, liefert aber nur den ersten (oder war’s der letze ??) Parameter zurück und wird eigentlich nur bei Nebenläufigkeiten (typischerweise display) gebraucht.

9

Ich bin entzückt.

Hast aber recht, hab das ‚begin‘ gerade mal nachgeschlagen. Es liefert nur den Rückgabewert der Auswertung des letzten Parameters zurück, hatte nur noch die sequentielle Ausführung in Erinnerung. Egal, ich habs jetzt mal zu deinen ‚and‘ verschlimmbessert und es scheint zu gehen (macht auch irgendwie mehr Sinn als ‚begin‘).