Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch Miniklausur WS 2018/19   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesung-miniklausur-18 [12.01.2019 20:45] – gabriel2029pruefungen:bachelor:aud:loesung-miniklausur-18 [30.03.2019 21:17] (aktuell) – gabriel2029
Zeile 15: Zeile 15:
  
 **c)** Die Aussagen 1 und 2 sind richtig. Zur Erklärung: **c)** Die Aussagen 1 und 2 sind richtig. Zur Erklärung:
-  * Da bei der O-Notation bei Summen nur der Summand zählt, der bei sehr großen Zahlen //das größte Gewicht// hat, muss nur der erste Summand betrachtet werden. Da Konstanten keine Auswirkung auf die O-Notation haben, können sie unbeachtet gelassen werden. (//Anmerkung: Die hier dargestellte Funktion ist ein Polynom. Die O-Laufzeit war also damit eigentlich schon bekannt und war nicht neu zu erschließen.//)+  * Da bei der O-Notation bei Summen nur der Summand zählt, der bei sehr großen Zahlen //das größte Gewicht// hat, muss hier nur der erste Summand betrachtet werden. Da Konstanten keine Auswirkung auf die O-Notation haben, können sie unbeachtet gelassen werden. (//Anmerkung: Die hier dargestellte Funktion ist ein Polynom. Die O-Laufzeit war also damit eigentlich schon bekannt und war nicht neu zu erschließen.//)
   * Hier wird ziemlich präzise die O-Notation beschrieben, nämlich, dass alle Methoden darin liegen, die __höchstens so schnell__ wie g(n) wachsen.   * Hier wird ziemlich präzise die O-Notation beschrieben, nämlich, dass alle Methoden darin liegen, die __höchstens so schnell__ wie g(n) wachsen.
   * Betrachtet man //pop(push(s, e))//. Hier wird zunächst //e// auf den Stapel gelegt, und anschließend das oberste Element, also //e//, wieder entfernt. Es gilt also //pop(push(s, e)) = s//. Betrachtet man //push(pop(s), e)//. Hier wird zuerst das oberste Element aus //s// entfernt und __anschließend__ //e// auf den Stapel gelegt. Der erste Stapel enthält //e// nun nicht, während der zweite //e// enthält. Die beiden Stapel sind also verschieden.   * Betrachtet man //pop(push(s, e))//. Hier wird zunächst //e// auf den Stapel gelegt, und anschließend das oberste Element, also //e//, wieder entfernt. Es gilt also //pop(push(s, e)) = s//. Betrachtet man //push(pop(s), e)//. Hier wird zuerst das oberste Element aus //s// entfernt und __anschließend__ //e// auf den Stapel gelegt. Der erste Stapel enthält //e// nun nicht, während der zweite //e// enthält. Die beiden Stapel sind also verschieden.
Zeile 68: Zeile 68:
     m[1] = m[2] = 1;     m[1] = m[2] = 1;
     for (int i = 3; i <= n; i++) {     for (int i = 3; i <= n; i++) {
-        m[i] = m[m[i - 1]] + m[n - m[n - 1]];+        m[i] = m[m[i - 1]] + m[i - m[i - 1]]; //Sollten die n's hier nicht auch i's sein? // hast Recht, wurde ausgetauscht
     }     }
     return m[n];     return m[n];