MINT lernen

Übungen: Operationen zählen

Zehn Übungen zum Zählen — von einfachen Schleifen über Dreiecksschleifen bis zur Laufzeitfunktion des Maximums.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Warum zählen?
AFB I

Laufzeiten werden im Unterricht durch Zählen von Operationen bestimmt. Nennen Sie alle Aussagen, die zutreffen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Die Zeitmessung hängt von Prozessor, Sprache und Auslastung ab. Im ungünstigsten Fall zählt der teurere Zweig. Und die Daten spielen oft mit: Die lineare Suche braucht je nach Position von x 1 bis \(n\) Vergleiche.
Ansatz: Suchen Sie bei jeder Aussage ein Gegenbeispiel.
Weiter: Denken Sie an die lineare Suche: Hängt ihre Vergleichszahl nur von \(n\) ab?
A2
Stimmt's? — Drei Durchgänge
AFB I

Ein Programm prüft jede Messung dreimal:

for (int i = 1; i <= n; i++) {        // Zeile A
    for (int j = 0; j < 3; j++) {    // Zeile B
        pruefe(i, j);                // Zeile C
    }
}

Lesen Sie die Anzahlen am Code ab und entscheiden Sie bei jeder Aussage, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Feste Grenzen wie j < 3 liefern einen konstanten Faktor. Nur Grenzen, die von n abhängen, verändern das Wachstum.
Ansatz: Zählen Sie zuerst, wie oft die innere Schleife je äußerem Durchlauf läuft.
Weiter: Die Bedingung wird immer einmal öfter geprüft, als der Rumpf läuft.
A3
Schleife und Anzahl
AFB I

In jedem Fragment wird x++ ausgeführt; \(n\) ist eine Zweierpotenz mit \(n \ge 2\). Ordnen Sie jedem Fragment zu, wie oft x++ läuft.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Schrittweite 2 halbiert die Durchläufe, eine feste innere Grenze multipliziert mit einer Konstanten. Beim Verdoppeln nimmt i die Werte 1, 2, 4, …, \(\frac{n}{2}\) an — das sind \(\log_2 n\) Werte. Eine Rechnung mit \(n\) kostet nur einen Schritt.
Ansatz: Schreiben Sie für \(n = 8\) die Werte von i auf, für die der Rumpf läuft.
Weiter: Bei i = i * 2: 1, 2, 4 — dann ist i = 8 nicht mehr kleiner als \(n\).
A4
Wachsende Dreiecke
AFB II

Gegeben ist das Fragment

int t = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        t++;
    }
}

Berechnen Sie die gesuchten Anzahlen.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Ausführungen von t++ für n = 4:
  2. Prüfungen der inneren Bedingung j <= i für n = 4:
  3. Ausführungen von t++ für n = 100:
Für festes i läuft j von 0 bis i: \(i + 1\) Durchläufe. Summe \(1 + 2 + \ldots + n = \frac{n(n+1)}{2}\): für \(n = 4\) sind das 10, für \(n = 100\) 5050. Die Bedingung wird je äußerem Durchlauf einmal mehr geprüft: \(10 + 4 = 14\).
Ansatz: Schreiben Sie für n = 4 auf, wie oft die innere Schleife bei i = 0, 1, 2, 3 läuft.
Weiter: Kleiner Gauß: \(1 + 2 + \ldots + n = \frac{n(n+1)}{2}\).
A5
T(n) für das Maximum
AFB II

Die Suche nach dem Maximum einer Reihung der Länge \(n\):

int max = a[0];                      // 1-mal
for (int i = 1; i < n; i++) {        // Bedingung
    if (a[i] > max) {                 // Vergleich
        max = a[i];                  // Zuweisung
    }
}

Leiten Sie die Laufzeitfunktion her, indem Sie die Lücken füllen.

Baustein anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Drei Bausteine bleiben übrig.

Die Bedingung wird -mal geprüft, der Vergleich -mal ausgeführt. Am meisten Zuweisungen gibt es, wenn die Reihung sortiert ist; im besten Fall sind es . Im ungünstigsten Fall gilt \(T(n) = 1 + n + 2(n - 1) = \) .

Die Schleife beginnt bei i = 1: \(n - 1\) Durchläufe, also \(n\) Prüfungen. Bei aufsteigender Sortierung ist jedes neue Element ein neues Maximum — jede Prüfung führt zur Zuweisung.
Ansatz: Achten Sie auf den Start bei i = 1.
Weiter: Wann ist jedes neue Element größer als das bisherige Maximum?
A6
Nur n oder auch die Daten?
AFB II Mix

Manche Anzahlen stehen fest, sobald \(n\) bekannt ist, andere hängen von der Anordnung der Werte ab. Analysieren Sie die Größen und markieren Sie die zutreffende Spalte.

Klicken Sie die Felder an, die zutreffen. Ein zweiter Klick nimmt die Markierung zurück.
Größehängt nur von n abhängt auch von den Daten ab
Vergleiche beim Suchen des Maximums
Vergleiche der linearen Suche
Zuweisungen max = a[i]
Vergleiche beim Selectionsort
Vertauschungen beim Bubblesort
Das Maximum und Selectionsort vergleichen immer gleich oft — ihre Schleifengrenzen hängen nur von \(n\) ab. Die lineare Suche bricht beim Treffer ab, Zuweisungen und Vertauschungen stehen in einem bedingten Zweig.
Ansatz: Prüfen Sie, ob die gezählte Anweisung in einem if steht oder ob die Schleife vorzeitig enden kann.
Weiter: Selectionsort sucht das Minimum immer im ganzen Rest — ohne Abbruch.
A7
Schritte zu dritt
AFB II

Ein Förderband holt in jedem Takt drei Pakete:

int k = n;
int z = 0;
while (k > 0) {
    k = k - 3;
    z++;
}

Ermitteln Sie den Endwert von z für verschiedene \(n\).

Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls.
nEndwert von z
3
10
12
100
Die Schleife läuft, bis k nicht mehr positiv ist: \(\lceil n / 3 \rceil\) Durchläufe. Bei \(n = 10\) nimmt k die Werte 10, 7, 4, 1 an — vier Durchläufe. Wachstum: linear mit Faktor \(\frac{1}{3}\).
Ansatz: Schreiben Sie für n = 10 die Werte von k vor jedem Durchlauf auf.
Weiter: Auch ein Rest von 1 oder 2 erzeugt noch einen Durchlauf.
A8
Falsch gezählt
AFB III

Mia hat an jede Zeile geschrieben, wie oft sie ausgeführt wird. Überprüfen Sie ihre Kommentare und markieren Sie genau die falschen.

In diesem Code stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Wer die innere Grenze übersieht, zählt \(n^2\) statt \(\frac{n(n+1)}{2}\). Die Wachstumsart ist zwar dieselbe (quadratisch), die Zahl aber etwa halb so groß.
Ansatz: Prüfen Sie jede Zahl für n = 3 durch Aufschreiben aller Paare (i, j).
Weiter: Bei n = 3 läuft die innere Schleife 3-, 2- und 1-mal.
A9
Halbe Runden
AFB III Trick

Das folgende Fragment sieht nach „Schleife in Schleife“ aus:

int z = 0;
for (int i = n; i > 0; i = i / 2) {
    for (int j = 0; j < i; j++) {
        z++;
    }
}

Bestimmen Sie den Endwert von z für \(n = 16\).

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Die innere Schleife läuft 16 + 8 + 4 + 2 + 1 = 31-mal. Wer „zwei Schleifen, also \(n \log n\)“ rechnet, erhält 64 — zu viel: Die innere Arbeit halbiert sich jedes Mal, insgesamt sind es weniger als \(2n\).
Ansatz: Schreiben Sie die Werte von i auf: 16, 8, …
Weiter: Je Wert von i läuft die innere Schleife genau i-mal.
A10
Stimmt die Faustregel?
AFB III

In einer Lerngruppe kursieren Faustregeln zum Zählen. Beurteilen Sie jede Regel.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1Regel stimmt
2Regel stimmt nicht
Hintereinander heißt addieren: \(n + n = 2n\). Eine feste innere Länge ist ein konstanter Faktor: \(100n\). Eine Verzweigung wählt nur einen Zweig — die Durchläufe bleiben gleich.
Ansatz: Probieren Sie jede Regel an einem kleinen Beispiel mit \(n = 4\) aus.
Weiter: Nur verschachtelte Schleifen, deren Grenzen beide von \(n\) abhängen, multiplizieren sich zu \(n^2\).