studyklar
GdI 1 · Beispielklausur · Aufgabe 2

Ist x im Array? Sequenzielle Suche als Flussdiagramm

Gesucht ist ein Algorithmus, der prüft, ob eine Zahl x in einem unsortierten Array vorkommt, und sein Flussdiagramm. Die Idee: x der Reihe nach mit jedem Element vergleichen und beim ersten Treffer aufhören. Rechts entsteht das Flussdiagramm Schritt für Schritt, links steht die Erklärung zum aktuellen Schritt. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 2

Entwerfen Sie einen Algorithmus, welcher für ein gegebenes, unsortiertes Ganzzahlen-Array a mit n Elementen und eine einzugebende Zahl x prüft, ob x wenigstens einmal im Array a enthalten ist, und stellen Sie den Algorithmus in einem Flussdiagramm dar!

Hinweise:

  • Sie dürfen voraussetzen, dass n > 0 ist.
  • Es muss nicht ermittelt werden, an welcher Stelle im Array die Zahl steht.

Gegeben ist ein Array a: eine Reihe von n ganzen Zahlen, die unter einem gemeinsamen Namen gespeichert sind. „Unsortiert“ heißt: Die Zahlen stehen in beliebiger Reihenfolge. Dazu wird eine Zahl x eingegeben. Der Algorithmus soll nur eine Ja/Nein-Antwort geben: Kommt x mindestens einmal in a vor oder nicht?

Die Hinweise vereinfachen die Aufgabe. n > 0 heißt: Das Array ist nicht leer, es hat mindestens ein Element. Und die Stelle, an der x steht, muss nicht ausgegeben werden.

Worauf es in der Klausur ankommt: Das Flussdiagramm wird von Hand gezeichnet, mit den Symbolen der Vorlesung. Jede Raute braucht zwei beschriftete Ausgänge (Ja und Nein). Die Schleife muss enden, und beide Antworten müssen vorkommen.

Merke: In einem unsortierten Array kann x überall stehen. Man kann also kein Element überspringen.
  1. Die Idee in Worten aufschreiben.
  2. Das Flussdiagramm Symbol für Symbol aufbauen.
  3. Mit dem Array 7, 3, 9, 5 zwei Schreibtischtests machen: einmal mit, einmal ohne Treffer.

Die Idee: Element für Element vergleichen

  1. x eingeben.
  2. Beim ersten Element des Arrays anfangen.
  3. Gibt es noch ein Element? Wenn nein: „x ist nicht enthalten“ ausgeben, Ende.
  4. Ist das Element gleich x? Wenn ja: „x ist enthalten“ ausgeben, Ende.
  5. Sonst zum nächsten Element gehen und bei 3. weitermachen.

Ein Mensch überfliegt das Array und sieht x vielleicht sofort. Ein Algorithmus arbeitet in einfachen Einzelschritten. Er sieht also ein Element nach dem anderen an und vergleicht es mit x.

Sobald ein Element gleich x ist, steht die Antwort fest: x ist enthalten. Der Rest des Arrays muss nicht mehr angesehen werden, denn die Stelle ist nicht gefragt. Erst wenn alle n Elemente ungleich x waren, steht die andere Antwort fest: x ist nicht enthalten.

Dieses Verfahren heißt sequenzielles Suchen („sequenziell“ heißt: der Reihe nach). Das Skript zeigt es auf Folie 5-12 als Beispiel für Arrays.

Aus Skript 5, Folie 5-12: Sequenzielles Suchen eines Werts x in einem Array a, der Reihe nach. Hoher Suchaufwand: im Mittel n/2 Vergleiche. Im Skript steht a.length/2; a.length ist die Länge des Arrays, also n.

Symbole, Start und Eingabe

Start → x eingeben

Ein Flussdiagramm zeichnet den Algorithmus. Jede Aktion ist ein Symbol, Pfeile (Flusslinien) geben die Reihenfolge vor. Abgerundete Kästchen stehen für Start und Stop, Rechtecke für Anweisungen (auch Eingabe und Ausgabe), Rauten für Fragen mit den Ausgängen Ja und Nein.

Das Array a mit seinen n Elementen ist laut Aufgabe schon gegeben; es wird nicht eingelesen. Nur x ist „einzugeben“. Darum steht nach Start nur das Rechteck x eingeben.

Aus Blatt 3, Aufgabe 1 („Minimum von vier Zahlen“): Dort wurden die Symbole des Flussdiagramms eingeführt (Skript 3, Folie 3-19): abgerundet für Start/Stop, Rechteck für Anweisungen, Raute für Verzweigungen mit Ja und Nein, Pfeile für die Reihenfolge.
Noch 11 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Abbildung 1

Start
Legendehell gefüllt: schon erklärt bzw. schon durchlaufenNoch steht nur Start da. Das Flussdiagramm entsteht in den nächsten Schritten Symbol für Symbol.