Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss11 [20.03.2018 21:08] – Evren | pruefungen:bachelor:aud:loesungss11 [21.03.2018 11:56] – Evren | ||
---|---|---|---|
Zeile 224: | Zeile 224: | ||
} | } | ||
} | } | ||
+ | </ | ||
+ | alternativ: | ||
+ | \\ | ||
+ | <code java> | ||
+ | void resize(int h) { | ||
+ | urls.ensureCapacity(h); | ||
+ | ips.ensureCapacity(h); | ||
+ | } | ||
</ | </ | ||
Zeile 274: | Zeile 282: | ||
<code java> | <code java> | ||
- | public static long getPrimeDPHelper(int n, long primes[]) { | + | public static long getPrimeDPHelper(int n, long primes[]) |
- | if(n <= 0) | + | // ArrayIndexOutOfBoundsException detection (falls getPrimeDPHelper(..) falsch aufgerufen wird) |
+ | if (n >= primes.length) { | ||
+ | throw new ArrayIndexOutOfBoundsException(" | ||
+ | } | ||
+ | |||
+ | | ||
return 2; | return 2; | ||
// Geforderte Primzahl wurde noch nicht berechnet | // Geforderte Primzahl wurde noch nicht berechnet | ||
- | if(primes[n] == 0) { | + | if (primes[n] == 0) { |
// Berechne den vorherige Primzahl | // Berechne den vorherige Primzahl | ||
long p = getPrimeDPHelper(n - 1, primes); | long p = getPrimeDPHelper(n - 1, primes); | ||
Zeile 310: | Zeile 323: | ||
| 0 | 11 | 16 | 3 | 7 | 7 | [17] | | | 0 | 11 | 16 | 3 | 7 | 7 | [17] | | ||
| 0 | 11 | 16 | 3 | 7 | 7 | 17 | | | 0 | 11 | 16 | 3 | 7 | 7 | 17 | | ||
+ | |||
+ | alternativ: | ||
+ | |||
+ | ^ Kara ^ A ^ B ^ C ^D ^E ^ Klee ^ | ||
+ | | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | ||
+ | | | ∞ | 18< | ||
+ | | | 13< | ||
+ | | | 11< | ||
+ | | | [11< | ||
+ | | | | [16< | ||
+ | | | | | | | | [17< | ||
+ | | | | | | | | | | ||
+ | |||
+ | Indizes rückwärts (von unten nach oben) durchgehen : [17< | ||
+ | |||
+ | => umdrehen: Klara -> C -> E -> A -> Klee | ||
**b)** | **b)** | ||
Zeile 448: | Zeile 477: | ||
Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein. | Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein. | ||
Die Invariante ist somit gültig. | Die Invariante ist somit gültig. | ||
+ | </ | ||
+ | |||
+ | einfacher: | ||
+ | < | ||
+ | Zu zeigen: (I ∧ b) => wp(B, I) | ||
+ | |||
+ | I: p = 2^(n - k - 1) ∧ k ≥ 0 | ||
+ | b: (k > 0) | ||
+ | B: "p *= 2; k--" <=> "p = p * 2; k = k - 1;" | ||
+ | |||
+ | (I ∧ b): | ||
+ | p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0 | ||
+ | (k ≥ 0 ∧ k > 0 <=> k > 0) | ||
+ | <=> p = 2^(n - k - 1) ∧ k > 0 | ||
+ | |||
+ | wp(B, I): | ||
+ | wp("p = p * 2; k = k - 1;", p = 2^(n - k - 1) ∧ k ≥ 0) | ||
+ | <=> wp("p = p * 2;", p = 2^(n - (k - 1) - 1) ∧ k - 1 ≥ 0) | ||
+ | <=> wp("p = p * 2;", p = 2^(n - k) ∧ k ≥ 1) | ||
+ | <=> wp(" ", p * 2 = 2^(n - k) ∧ k ≥ 1) | ||
+ | <=> p * 2 = 2^(n - k) ∧ k ≥ 1 | ||
+ | <=> p = (1/2) * 2^(n - k) ∧ k ≥ 1 | ||
+ | <=> p = 2^(n - k) * (1/2) ∧ k ≥ 1 | ||
+ | <=> p = 2^(n - k) * 2^(-1) ∧ k ≥ 1 ((1/2) = 2^(-1)) | ||
+ | <=> p = 2^(n - k - 1) ∧ k ≥ 1 | ||
+ | |||
+ | (I ∧ b) => wp(B, I): | ||
+ | p = (2^(n - k - 1) ∧ k > 0) | ||
+ | -> wahr, weil k > 0 <=> k ≥ 1, da k vom Datentyp " | ||
+ | |||
+ | fertig | ||
</ | </ | ||