studyklar
GdI 1 · Übungsblatt 3 · Aufgabe 2

Gerade oder ungerade ohne Division

Gesucht ist ein Algorithmus, der sagt, ob eine natürliche Zahl n gerade oder ungerade ist. Teilen ist verboten. Die Idee: So lange 2 abziehen, bis 0 oder 1 übrig bleibt. Rechts steht das Ablaufdiagramm, links die Erklärung zum aktuellen Schritt. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 3.2

Entwerfen Sie einen Algorithmus, der zu einem gegebenen n ∈ ℕ bestimmt, ob n gerade oder ungerade ist. Geben Sie eine Lösung ohne Verwendung der Division und Modulo-Funktion an.

Eingabe ist eine natürliche Zahl n (n ∈ ℕ heißt: n ist eine der Zahlen 0, 1, 2, 3, …; manche Bücher beginnen bei 1, der Algorithmus funktioniert für beide). Ausgabe ist „gerade“ oder „ungerade“.

Gerade heißt: Beim Teilen durch 2 bleibt kein Rest. Genau diese Division und die Modulo-Funktion (sie liefert den Rest, in Java n % 2) sind aber verboten. Erlaubt sind Vergleichen und Abziehen.

Merke: Zieht man von einer Zahl 2 ab, bleibt sie gerade oder ungerade, wie sie war.
  1. Die Idee: Teilen durch wiederholtes Abziehen ersetzen.
  2. Das Ablaufdiagramm mit einer Schleife aufbauen.
  3. Begründen, warum die Schleife endet.
  4. Schreibtischtest mit n = 7.

Die Idee: 2 abziehen, bis 0 oder 1 übrig ist

  1. n eingeben.
  2. Solange n ≥ 2: n ← n − 2.
  3. Falls n = 0, „gerade“ ausgeben, sonst „ungerade“ ausgeben.

Teilen durch 2 heißt: Wie oft passt die 2 hinein, und was bleibt übrig? Das kann man auch durch Abziehen herausfinden. Man zieht 2 ab, solange noch mindestens 2 da sind. Am Ende bleibt 0 oder 1 übrig. Das ist genau der Rest beim Teilen durch 2.

Warum stimmt das? Zieht man von einer geraden Zahl 2 ab, ist sie wieder gerade; von einer ungeraden wieder ungerade. Der Rest 0 oder 1 am Ende ist also gerade bzw. ungerade genau dann, wenn n es war.

Start und Eingabe

Start → n eingeben

Das Diagramm beginnt mit Start (abgerundetes Kästchen). Dann wird n eingegeben; wie im Skript steht die Eingabe in einem Rechteck, dem Symbol für eine Anweisung.

Aus Skript 3, Folie 3-19 („Flussdiagramm“): Abgerundetes Kästchen: Beginn und Ende. Rechteck: Anweisung. Raute: Verzweigung mit Ja und Nein. Pfeile (Flusslinien) legen fest, welcher Schritt als Nächstes kommt.
Noch 7 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

JaNeinJaNeinStartn eingebenn ≥ 2?n ← n − 2n = 0?„gerade“ ausgeben„ungerade“ ausgebenStop
Legendehell gefüllt: schon erklärt bzw. schon durchlaufenAblaufdiagramm: gerade oder ungerade ohne Division.