Operationen zählen: Übungen – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Ü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.

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?

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.

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\).