Die Wetterstation
14 BEAFB I–IIEine Schul-Wetterstation speichert die Tageshöchsttemperaturen einer Woche in °C in der Reihung t. Um den heißesten Tag zu finden, wurde die abgebildete Methode groesster nach dem Prinzip Teile und herrsche programmiert. Der Aufruf lautet groesster(t, 0, t.length - 1).
static int groesster(int[] a, int links, int rechts) {
if (links == rechts) {
return a[links];
}
int mitte = (links + rechts) / 2;
int g1 = groesster(a, links, mitte);
int g2 = groesster(a, mitte + 1, rechts);
if (g1 >= g2) {
return g1;
}
return g2;
}- Beschreiben Sie am Beispiel der Methode
groessterdie drei Schritte der Strategie Teile und herrsche und nennen Sie den Basisfall. (3 BE) - Stellen Sie die Aufrufe von
groesster(t, 0, 5)als Aufrufbaum dar. Notieren Sie an jedem Aufruf die Parameterlinks,rechtsund den Rückgabewert. (5 BE) - Geben Sie die Anzahl der Aufrufe und die Anzahl der Vergleiche
g1 >= g2für diese Reihung an. Verallgemeinern Sie beide Anzahlen für eine Reihung mit \(n\) Elementen. (3 BE) - Implementieren Sie nach demselben Prinzip eine Methode
static int anzahlUeber(int[] a, int links, int rechts, int grenze), die zählt, an wie vielen Tagen die Temperatur übergrenzelag. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
mitte = 2. Zeichnen Sie für jeden Aufruf zwei Kinder, bis die Bereiche nur noch ein Element haben.Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Teilen: Der Bereich links … rechts wird bei mitte in zwei Hälften geteilt. Herrschen: Für beide Hälften wird groesster rekursiv aufgerufen (g1, g2). Zusammenführen: Der größere der beiden Teilwerte wird zurückgegeben. Basisfall: links == rechts — ein einzelnes Element ist sein eigenes Maximum.
Erwartungshorizont zu Aufgabe b)
Der Rückgabewert 22 gehört zu Index 2 (dritter Tag).
Erwartungshorizont zu Aufgabe c)
11 Aufrufe, davon 6 Basisfälle und 5 Aufrufe mit Vergleich; also 5 Vergleiche. Allgemein: \(n\) Basisfälle und \(n - 1\) Zusammenführungen, insgesamt \(2n - 1\) Aufrufe und \(n - 1\) Vergleiche — genauso viele Vergleiche wie bei einer Schleife.
Erwartungshorizont zu Aufgabe d)
static int anzahlUeber(int[] a, int links, int rechts, int grenze) {
if (links == rechts) {
if (a[links] > grenze) {
return 1;
}
return 0;
}
int mitte = (links + rechts) / 2;
return anzahlUeber(a, links, mitte, grenze)
+ anzahlUeber(a, mitte + 1, rechts, grenze);
}Für t und grenze = 15 liefert die Methode 3 (22, 17, 19).
Schnelles Potenzieren
16 BEAFB II–IIIIn der Kryptologie müssen Potenzen \(x^n\) mit sehr großen Exponenten berechnet werden. Die naive Methode multipliziert \(n - 1\)-mal mit \(x\). Die abgebildete Methode potenz nutzt dagegen \(x^n = x^{n/2}\cdot x^{n/2}\) für gerades \(n\) und \(x^n = x^{(n-1)/2}\cdot x^{(n-1)/2}\cdot x\) für ungerades \(n\).
static long potenz(long x, int n) {
if (n == 0) {
return 1;
}
long h = potenz(x, n / 2);
if (n % 2 == 0) {
return h * h;
}
return h * h * x;
}- Analysieren Sie den Aufruf
potenz(3, 10): Geben Sie alle Aufrufe mit ihren Rückgabewerten in der Reihenfolge an, in der sie enden. (4 BE) - Leiten Sie her, wie viele Multiplikationen
potenzfür \(n = 2^k\) höchstens ausführt, und vergleichen Sie für \(n = 1024\) mit dem naiven Verfahren. (4 BE) - Erläutern Sie, warum die Variante
return potenz(x, n / 2) * potenz(x, n / 2);(für gerades \(n\)) den Vorteil vollständig zunichtemacht. (4 BE) - Beurteilen Sie den Einsatz von
potenzfür die Verschlüsselung, bei der Exponenten mit mehreren hundert Stellen vorkommen. Berücksichtigen Sie Laufzeit, Rekursionstiefe und den Datentyplong. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
n = 0.Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
long werden?Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Aufrufkette: potenz(3,10) → potenz(3,5) → potenz(3,2) → potenz(3,1) → potenz(3,0). Sie enden in umgekehrter Reihenfolge:
| Aufruf | h | n gerade? | Rückgabe |
|---|---|---|---|
| potenz(3, 0) | — | Basisfall | 1 |
| potenz(3, 1) | 1 | nein | 1 · 1 · 3 = 3 |
| potenz(3, 2) | 3 | ja | 3 · 3 = 9 |
| potenz(3, 5) | 9 | nein | 9 · 9 · 3 = 243 |
| potenz(3, 10) | 243 | ja | 243 · 243 = 59 049 |
Erwartungshorizont zu Aufgabe b)
Für \(n = 2^k\) sind alle Exponenten außer 1 gerade: \(2^k, 2^{k-1}, \dots, 2\) mit je einer Multiplikation, dazu \(n = 1\) mit zwei Multiplikationen (\(h\cdot h\cdot x\)).
\(M(2^k) = k + 2 = \log_2 n + 2\); allgemein höchstens \(2(\lfloor\log_2 n\rfloor + 1)\). Für \(n = 1024\): 12 Multiplikationen statt 1023.
Erwartungshorizont zu Aufgabe c)
Beide Aufrufe berechnen dasselbe Ergebnis, aber jeweils vollständig neu. Die Zahl der Aufrufe verdoppelt sich auf jeder Ebene: \(1 + 2 + 4 + \dots + n \approx 2n\) Aufrufe. Damit ist der Aufwand wieder linear in \(n\) — schlechter als die naive Schleife, weil noch Methodenaufrufe hinzukommen. Der Vorteil entsteht nur, weil ein Teilproblem gelöst und das Ergebnis h doppelt verwendet wird.
Erwartungshorizont zu Aufgabe d)
Laufzeit: Die Zahl der Multiplikationen wächst nur mit \(\log_2 n\); bei 300 Dezimalstellen (\(n\approx10^{300}\approx2^{1000}\)) sind es etwa 2000 statt \(10^{300}\) Multiplikationen — nur so ist die Rechnung überhaupt möglich. Rekursionstiefe: etwa 1000 Aufrufe, unkritisch für den Aufrufstapel. Datentyp: Ein long reicht nur bis etwa \(9\cdot10^{18}\); die Ergebnisse laufen sofort über. Man muss deshalb nach jeder Multiplikation modulo rechnen und mit beliebig großen Zahlen (z. B. BigInteger) arbeiten. Fazit: Das Verfahren ist geeignet und wird in der Kryptologie so genutzt, aber nicht mit long.