Not logged in. · Lost password · Register

LaCucaracha
Member since Jan 2012
43 posts
Subject: 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...
LaCucaracha
Member since Jan 2012
43 posts
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

?
Horst
Member since Jan 2011
14 posts
Subject: 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!
Guanta
Avatar
Member since Oct 2005
307 posts
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.
An eye for an eye will make the whole world blind. (Gandhi)
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #2
Quote by LaCucaracha:
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

?

Richtig.
An eye for an eye will make the whole world blind. (Gandhi)
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #3
Quote by Horst:
6 b.) sollte hier einfach jedes Element des Arrays Photo []p mit Date d verglichen werden??
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.
Quote by Horst:
6 c.) Der Aufwand wäre doch O(n) (Es sind ja keine Angaben dazu gemacht ob die Reihung in c.) sortiert ist ??)
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).
Quote by Horst:
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?!
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)
An eye for an eye will make the whole world blind. (Gandhi)
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #1
Quote by LaCucaracha:
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...

Ohne Gewähr:
  1. for(int i = 1; i < n; i++) {            // Zeilen
  2.     for(int j = 0; j < m + 1; j++) {    // Spalten
  3.         if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht
  4.             tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben.
  5.             if(j + k[i+1] <= m)
  6.                 tab[i+1][j+k[i+1]] = MIT;
  7.         }
  8.     }
  9. }
An eye for an eye will make the whole world blind. (Gandhi)
LaCucaracha
Member since Jan 2012
43 posts
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?
Ouler
Member since Oct 2011
66 posts
Meine Lösung dafür ist:

  1. public Photo[] getAllPhotosSorted(){
  2.          Photo[] p = myPhotos;
  3.  
  4.          for(int i = 0; i<myAlbums.length;i++)
  5.                     p = combinePhotos(p,myAlbums[i].getAllPhotosSorted());
  6.  
  7.         return p;
  8.  
  9.  
  10. }

Kann das funktionieren?
Horst
Member since Jan 2011
14 posts
In reply to post #6
@ 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" ?
This post was edited on 2012-02-20, 11:40 by Horst.
Der Ich
93,333% Dipl.-Exzentriker
Avatar
Member since Oct 2006
3642 posts
+2 pug, meisterT
Quote by Horst:
meinst du mit "dead look"?

Das ist der sogenannte Todesblick. Er sorgt dafür dass parallele Programme aufhören zu exekutieren wenn man sie anschaut.
* 01.10.2006, + 28.11.2011, † 31.01.2013
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #10
Quote by Horst:
@ 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" ?

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.
An eye for an eye will make the whole world blind. (Gandhi)
Guanta
Avatar
Member since Oct 2005
307 posts
In reply to post #9
Quote by Ouler:
Meine Lösung dafür ist:

  1. public Photo[] getAllPhotosSorted(){
  2.          Photo[] p = myPhotos;
  3.  
  4.          for(int i = 0; i<myAlbums.length;i++)
  5.                     p = combinePhotos(p,myAlbums[i].getAllPhotosSorted());
  6.  
  7.         return p;
  8.  
  9.  
  10. }

Kann das funktionieren?

Jop, das sieht richtig aus!
An eye for an eye will make the whole world blind. (Gandhi)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen