Aus ProgrammingWiki
Berrechnen Sie den höchst möglichen Wert, den Sie in den Rucksack mit der Kapazität = 30 einpacken können. Gegeben sind folgende Gegenstände:
Überprüfen Sie Ihr Ergebnis mit Hilfe der Prozedur bruchteilrucksack.
2. Übung zum Dijkstra-Algorithmus
Gegeben ist folgende Matrix:
Zeichnen Sie den Graphen und wenden Sie den Dijkstra-Algorithmus auf diesen an. Gesucht ist der kürzeste Weg von A nach H.
3. Übung zur Bildung eines minimalen Spannbaums
Wenden Sie einen Algorithmus Ihrer Wahl (Kruskal oder Prim) auf den Graphen aus Aufgabe 2 an und erstellen Sie den minimalen Spannbaum.
4. Gegeben ist folgender Graph:
Finden Sie mit Hilfe des Dijkstra-Algorithmus den kürzesten Weg von A nach P.
5. Bilden Sie den minimalen Spannbaum für den Graphen aus Aufgabe 4 mit einem Algorithmus Ihrer Wahl und begründen Sie, warum Sie sich für den benutzten Algorithmus entschieden haben.
6. Programmieren Sie auf Grundlage des Greedy-Templates eine Scheme-Prozedur, die eine Zahl in ihre Primfaktoren zerlegen kann. Beachten Sie dabei, dass Sie die Hilfsprozedur delete benötigen.
(define delete
(lambda (item ls)
(cond
((null? ls) '())
((eqv? (car ls) item) (cdr ls))
(else
(cons (car ls) (delete item (cdr ls)))))))
Aufrufbeispiel:
> (primfaktoren 30)
((5 3 2) 3)
Hinweis: Die letzte "3" ist die Anzahl der Primfaktoren.
Weitere Aufrufbeispiele:
- 28
- 76
- 102
- 1024
- 2011
