SystemSuche Loesung

Aus ProgrammingWiki

Archivierte Version vom 2009-05-08T18:21:18+00:00. Aktuelle Version

1. beschränkten Tiefensuchbaum für 15,35,42, 77 bei K=55.

(define gewichte
  (lambda (ls)
    (map car ls)))

(define werte
  (lambda (ls)
    (map cdr ls)))

(define rucksack3a
  (lambda (g-ls k)
    (let
        ((max-s-ls '())
         (mwert 0))
      (letrec
          ((helper
            (lambda (g-ls s-ls)
              (if (null? g-ls)
                  (let
                      ((gesamtgewicht (apply + (gewichte s-ls)))
                       (gesamtwert (apply + (werte s-ls))))
                    (if (and
                         (hoechstens-maxgewicht? (gewichte s-ls) k)
                         (> gesamtwert mwert))
                        (begin
                          (set! max-s-ls (gewichte s-ls))
                          (set! mwert gesamtwert)))
                    (cons max-s-ls mwert))
                  (begin
                    (if (hoechstens-maxgewicht? (gewichte s-ls) k)
                        (helper (cdr g-ls) (cons (car g-ls) s-ls)))
                    (if (hoechstens-maxgewicht? (gewichte s-ls) k)
                        (helper (cdr g-ls) s-ls)))))))
        (helper g-ls '())))))

3. a)Erstellen Sie einen Breitensuchbaum für folgende 4 Gegenstände : '(15 35 42 77) b)Erzeugen Sie einen reduzierten Breitensuchbaum zu den 4 Gegenständen.

4. Machen Sie sich mit den Hilfspozeduren von Scheme für das Konzept des Nichtdeterminismus aus der Vorlesung vertraut.

a)Schreiben Sie die Prozeduren summandensucheA bzw. summandenA, dass eine Liste als Eingabeparameter angegeben kann.

(summandensucheA '(0 1 2 3 4 5) 6)

speichern & ausführen

b)Schreiben Sie eine Prozedur summandensucheB die, nur Zahlenpaare aus gibt, deren Summe durch 3 teilbar ist.(todo)

(bag-of(summandensucheB '(1 2 3 4 5)))

speichern & ausführen

c)Verändern Sie summandensucheB so, dass auf Teilbakeit von x (x in N) verallgemenert werden kann. Der Wert x soll ebenfalls als Eingabewert übergeben werden.

(teilbar_x '(1 2 3 4 5 6 7 8 9) 6)

speichern & ausführen

Wer diese und die Aufgaben im Buch durchgearbeitet hat, kann als Zusatz folgende bearbeiten: ZA*** : Verändern Sie die 4.c) so,dass es zu keinen doppelten Pärchen mehr kommt. E soll verhindert werden, dass (3,1) und (1,3) beide in der Ergebnisliste zu sehen ist. ZA*** : Implementieren Sie das n Damenproblem oder die Breitensuche in Scheme oder in einer anderen Programmiersprache.