Felder und die Grundmuster

Felder: viele Werte unter einem Namen

Bisher hatte jede Variable genau einen Wert. Sobald eine Aufgabe von „den Messwerten“, „allen Kunden“ oder „einer Liste von Preisen“ spricht, brauchst du ein Feld (Array). Stell dir ein Feld als Reihe nummerierter Fächer vor: Jedes Fach enthält einen Wert, und die Nummer des Fachs heißt Index. Das Feld zahlen mit vier Werten sieht so aus:

Auf ein einzelnes Fach greifst du mit dem Index in eckigen Klammern zu: zahlen[2] ist 9, zahlen[4] ist 7. Der Index darf auch eine Variable sein, und genau das macht Felder so nützlich: zahlen[i] meint je nach Wert von i ein anderes Fach. Die Anzahl der Elemente heißt im Kurs n; manche Aufgaben schreiben stattdessen laenge(zahlen) oder geben die Anzahl im Text fest vor („ein Feld mit 20 Messwerten“).

Alle Elemente der Reihe nach anzusehen ist die Grundbewegung bei Feldern. Weil die Anzahl vorher feststeht, ist die Zählschleife aus Lektion 3 das passende Werkzeug. Der Zähler ist zugleich der Index:

FÜR i = 1 BIS n
    AUSGABE zahlen[i]
ENDE FÜR

Für das Feld oben werden nacheinander 4, 9, 2 und 7 ausgegeben. Jedes der folgenden Muster ist nichts anderes als dieser Durchlauf mit etwas Zusatz davor, im Rumpf und danach.

Summe und Durchschnitt

Das erste Muster: alle Werte zusammenzählen. Dafür braucht es eine Variable, die vor der Schleife auf 0 gesetzt wird und in jedem Durchlauf das aktuelle Element dazubekommt. Eine solche Variable heißt Akkumulator („Sammler“).

summe = 0
FÜR i = 1 BIS n
    summe = summe + zahlen[i]
ENDE FÜR
AUSGABE summe

Der Schreibtischtest (Wertetabelle) für zahlen = [4, 9, 2, 7] mit n = 4:

Der Durchschnitt ist die Summe geteilt durch die Anzahl. Er kommt nach der Schleife dazu, als eine Anweisung. Wir setzen n >= 1 voraus (mindestens ein Wert), sonst würde durch 0 geteilt:

summe = 0
FÜR i = 1 BIS n
    summe = summe + zahlen[i]
ENDE FÜR
durchschnitt = summe / n
AUSGABE durchschnitt

Für unser Feld: 22 / 4 = 5,5. Achte auf den Datentyp: durchschnitt muss eine Kommazahl sein, und die Division ist das / mit Nachkommastellen, nicht DIV. Mit ganzzahliger Division käme 5 heraus, und das ist in vielen Lösungshinweisen ein eigener Abzug. Wenn eine Aufgabe die Datentypen nennen lässt, schreibe „summe: Ganzzahl, durchschnitt: Kommazahl“ dazu.

Maximum und Minimum mit Index

Das größte Element finden: Du merkst dir einen Kandidaten und vergleichst jedes weitere Element mit ihm. Ist das Element größer, wird es der neue Kandidat. Oft will die Aufgabe nicht nur den Wert, sondern auch die Stelle, an der er steht; dann merkst du dir den Index gleich mit. Wir setzen n >= 1 voraus (mindestens ein Wert), damit der Startkandidat existiert.

max = zahlen[1]
pos = 1
FÜR i = 2 BIS n
    WENN zahlen[i] > max DANN
        max = zahlen[i]
        pos = i
    ENDE WENN
ENDE FÜR
AUSGABE max, pos

Das Minimum ist dieselbe Struktur mit umgedrehtem Vergleich: Der Kandidat wird ersetzt, wenn das Element kleiner ist.

Kommt der größte Wert mehrfach vor, behält > die erste Stelle, weil ein gleich großes Element die Bedingung nicht erfüllt. Mit >= würde die letzte Stelle gemerkt. Wenn die Aufgabe dazu nichts sagt, sind beide Varianten in Ordnung; sag im Zweifel in einem Satz dazu, welche du gewählt hast.

Zählen mit Bedingung

„Wie viele Werte sind größer als 5?“ Das Muster kennst du aus Lektion 4: ein Zähler, der vor der Schleife auf 0 gesetzt wird, und eine Verzweigung im Rumpf, in deren Ja-Zweig der Zähler um 1 erhöht wird. Neu ist nur, dass die Bedingung ein Feldelement prüft.

anzahl = 0
FÜR i = 1 BIS n
    WENN zahlen[i] > 5 DANN
        anzahl = anzahl + 1
    ENDE WENN
ENDE FÜR
AUSGABE anzahl

Der Unterschied zur Summe: Beim Zählen kommt in jedem Treffer + 1 dazu, bei der Summe + zahlen[i]. Beides lässt sich kombinieren, etwa „Summe aller geraden Werte“: Verzweigung mit zahlen[i] MOD 2 == 0, im Ja-Zweig summe = summe + zahlen[i].

Lineare Suche

„Kommt der Wert 2 im Feld vor, und wenn ja, an welcher Stelle?“ Die lineare Suche geht die Elemente von vorn nach hinten durch und vergleicht jedes mit dem gesuchten Wert. Zwei Dinge musst du dir merken: ob etwas gefunden wurde (ein Merker vom Typ Wahrheitswert) und wo (die Position). Sobald der Wert gefunden ist, darf die Suche aufhören. Deshalb ist die Standardform eine kopfgesteuerte Schleife mit doppelter Bedingung:

EINGABE gesucht
gefunden = falsch
i = 1
SOLANGE i <= n UND NICHT gefunden
    WENN zahlen[i] == gesucht DANN
        gefunden = wahr
        position = i
    ENDE WENN
    i = i + 1
ENDE SOLANGE
WENN gefunden DANN
    AUSGABE "Position", position
SONST
    AUSGABE "nicht gefunden"
ENDE WENN

Die Schleife läuft, solange noch Elemente übrig sind (i <= n) und noch nichts gefunden wurde (NICHT gefunden). Sobald eine der beiden Bedingungen kippt, endet sie: entweder am Feldende oder nach dem Treffer. Der Schreibtischtest für die Suche nach 2 in [4, 9, 2, 7]:

Würde nach 5 gesucht, bliebe gefunden falsch, i liefe bis 5, die Bedingung 5 <= 4 wäre falsch, und die Ausgabe wäre „nicht gefunden“. Die Verzweigung nach der Schleife entscheidet über die Ausgabe; im Rumpf selbst wird nichts ausgegeben.

Die Alternative ist eine Zählschleife mit Merker. Sie ist kürzer, läuft aber nach dem Treffer bis zum Feldende weiter und merkt sich bei mehrfach vorkommenden Werten die letzte Position:

Merkregeln für alle Muster

1. Startwert passend zum Muster: 0 für Summe und Zähler, 1 für ein Produkt, das erste Element für Maximum und Minimum, falsch für den gefunden-Merker.
2. Eine Schleife über alle Elemente, der Zähler ist der Index. Grenzen zur Indexbasis passend: 1 bis n oder 0 bis n − 1.
3. Ausgabe nach der Schleife, nicht im Rumpf. Im Rumpf wird nur gerechnet, verglichen und gemerkt.

Übungen

Jetzt selbst testen

Vier Fragen zu Feldern und den Grundmustern.