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.
Klausur 31.07.2008
Ich hab ne Frage zu Aufgabe 1 (Rucksack) c) und zwar:
Wie habt ihr den Teil des Algorithmus implementiert, mit dem man feststellt, ob k Teil der Lösung ist?
Mir fallen nur umständliche Sachen ein die sicher nicht in den freien Platz passen…
Da ich da bei den Übungen ziemlich viele Fehler hatte:
Bei 3a) kommt folgendes raus:
statisch: A, dynamisch: A
statisch: A, dynamisch: AA
statisch: B, dynamisch: B
?
Gegenfrage Aufgabe 6.)
6 b.) sollte hier einfach jedes Element des Arrays Photo []p mit Date d verglichen werden??
6 c.) Der Aufwand wäre doch O(n) (Es sind ja keine Angaben dazu gemacht ob die Reihung in c.) sortiert ist ??)
6 d.)Frage 1.) Naja, dass kommt doch auf die Implementierung aus b.) an!Würde ich durch das ganze Array gehen und jedes Element des Arrays mit date vergleichen → dann ja!Würde ich mich aber vom gefundenen Photo aus, nach links und rechts tasten dann nicht.
Frage 2.) Kommt doch wieder auf die Implementierung an?!
Würde mich über ein paar Anmerkungen freuen!
Macht doch bitte nächstens zu jeder Aufgabe einen neuen Thread auf, das erhöht die Übersichtlichkeit und kann dann besser ins Prüfungswiki einsortiert werden.
Richtig.
Nein, das Array p enthält einfach die Photos, du sollst nun alle zurückliefern die du mit dem Datum findest, also einfach von Aufgabe a) die findPhotoForDate() aufrufen und dann mit dem gefundenen Index linear weitersuchen und die Elemente in ein Array packen.
Ich denke sie beziehen das schon auf die ganze Aufgabe und in der a) steht ja dass es sort ist → binary search → O(log n).
1.) Nein, würde zu deadlock führen (man steigt ja nur ab, und nicht auch wieder auf)
2.) Ja, im best-case findet man das Element natürlich sofort → O(1)
Ohne Gewähr:
for(int i = 1; i < n; i++) { // Zeilen
for(int j = 0; j < m + 1; j++) { // Spalten
if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht
tab[i+1][j] = OHNE; // so muss die Zelle daraunter den Wert OHNE haben.
if(j + k[i+1] <= m)
tab[i+1][j+k[i+1]] = MIT;
}
}
}Super, jetzt ist mir das Prinzip beim Rucksack klar geworden. Diese Prüfung ist i. A. ganz schön tricky. Gerade hänge ich bei der Rekursion 5b). Meine Idee ist: jeweils im aktuellen Album die Fotos in die kombinierte Liste übernehmen und dann mit einer for-Schleife rekursiv in die Teilalben rein bis myAlbums == null. Nur stehe ich gerade auf dem Schlauch was die Zwischenspeicherung der AllPhotosSorted angeht. Oder ist das schon wieder zu kompliziert gedacht?
Meine Lösung dafür ist:
public Photo[] getAllPhotosSorted(){
Photo[] p = myPhotos;
for(int i = 0; i<myAlbums.length;i++)
p = combinePhotos(p,myAlbums[i].getAllPhotosSorted());
return p;
}Kann das funktionieren?
@ Guanta
erstmal danke für deine Antwort. Ich habe noch einmal ein Rückfrage. Was
meinst du mit “deadlock”? Und was meinst du mit" man steigt ja nur ab, und nicht auch wieder auf" ?
Das ist der sogenannte Todesblick. Er sorgt dafür dass parallele Programme aufhören zu exekutieren wenn man sie anschaut.
2 „Gefällt mir“
Erstmal muss ja eine binäre Suche nach dem Bild gemacht werden (also findFotoForDate(…) aufrufen). Diese schlägt aber fehl, wenn das Array nicht sortiert ist. Stell dir z.B. die Folge 6 3 7 4 5 vor und du suchst nach der 5, ich prüfe die Mitte (=7) sehe, das ist größer, also gehe ich in die linke Hälfte, dort treffe ich auf die 6, immer noch zu groß → kann nicht weiter absteigen → Ende.
Jop, das sieht richtig aus!