Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:bachelor:aud:loesungws09 [20.03.2018 18:12] – Evren
+++ pruefungen:bachelor:aud:loesungws09 [17.05.2019 15:09] – SpeedyGonzalez
@@ Zeile 10: / Zeile 10: @@
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8861-Klausur-25-02-2010-Aufgabe-7b-Dijkstra]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9468-Klausur-25-02-2010]]
+  * [[https://fsi.cs.fau.de/forum/thread/17186-Klausur-Ws2009-Frage-zu-ADTs-A8c]]
 ===== Lösungsversuch =====
@@ Zeile 79: / Zeile 80: @@
 private static long[][] b = new long[MAX][MAX];
 // Vorinitialisierung des Felds b[][] mit -1
+//Klausurfragestellung nicht ganz eindeutig, gefragt ist hier richtigerweise dynamische Programmierung mittels Memoization
-private static long binomFast(int n, int k) {
+private static long binom(int n, int k) {
 	if(k > n)
 		return 0;
@@ Zeile 187: / Zeile 189: @@
   * **O(n log n)**
 Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!)
+Ja O(n), in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm
 **c)**
@@ Zeile 201: / Zeile 205: @@
 	}
 }
+</code>
+Das ginge meines Erachtens (bei anderer Angabe noch leichter), oder??:
+<code java>
+public static void haldenSortierung(int[] feld){
+    haldenEigenschaftHerstellen(feld);
+    for(int i = feld.length - 1; i > 0; i--){
+        tausche(feld, 0, i);
+        versickern(feld, 0, i - 1);
+    }
+}
 </code>