inf-schule | Algorithmusbegriff

Übungen

Aufgabe 1: Verfahrensbeschreibungen

Handelt es sich bei den folgenden Verfahrensbeschreibungen um Algorithmen? Benutze die Kriterien, um deine Entscheidung zu begründen.

Schach spielen:

SOLANGE weiß und schwarz nicht schachmatt:
    führe abwechselnd (beginnend mit weiß) einen Zug aus:

Primzahlen auflisten:

zahl = 2
Ausgabe: zahl
zahl = zahl + 1
SOLANGE zahl keine Primzahl:
    zahl = zahl + 1
Ausgabe: zahl
zahl = zahl + 1
SOLANGE zahl keine Primzahl:
    zahl = zahl + 1
Ausgabe: zahl
zahl = zahl + 1
SOLANGE zahl keine Primzahl:
    zahl = zahl + 1
Ausgabe: zahl
...

Würfeln:

zahl = Zufallszahl aus {1..6}
anzahl = 1
Solange zahl keine 6 ist:
    zahl = Zufallszahl aus {1..6}
    anzahl = anzahl + 1
Ausgabe: "Du hast so viele Versuche benötigt: ", anzahl

Aufgabe 2: Ein Algorithmenpuzzle

Wie testet man, ob eine natürliche Zahl n eine Primzahl ist oder nicht? Eine Möglichkeit besteht darin, schrittweise zu überprüfen, ob n durch eine Zahl zwischen 2 und n-1 teilbar ist.

Das folgende Struktogramm soll dieses Verfahren algorithmisch beschreiben. Es legt bisher nur die Ablauflogik mit Hilfe von geeigneten Bausteinen fest. Es fehlen hingegen noch die passenden Anweisungen und Bedingungen.

Ergänze das Struktogramm, indem du die folgenden Anweisungen in die leeren Kästchen

i = i+1
Ausgabe: prim
i = 2
prim = True
Eingabe: n
prim = False
prim = False

und die folgenden Bedingungen an die mit drei Punkten markierten Stellen

i <= n-1
n durch i teilbar
n == 1

einordnest. (Hinweis: Ein Kästchen bleibt leer. Welches? Zweiter Hinweis: Es gibt natürlich andere algorithmische Vorgehensweisen. Dieses Struktogramm und die dazugehörenden Anweisungen und Bedingungen sind nur eine Möglichkeit. Sie setzen genau die oben genannte Idee um.)

Beschreibe auch die Ablauflogik des oben dargestellten Struktogramms mit einem Flussdiagramm.

Implementiere den Algorithmus in Python und teste ihn.

Aufgabe 3: Ein Potenzierungsalgorithmus

In der freien Enzyklopädie Wikipedia findet man unter dem Stichwort schnelles Potenzieren die folgende Verfahrensbeschreibung:

Der Exponent wird schrittweise halbiert (das Ergebnis wird abgerundet) und die Basis schrittweise quadriert. Man streicht die Zeilen mit geradem Exponenten. Das Produkt der nichtgestrichenen rechten Zahlen ist die gesuchte Potenz.

Teste erst einmal dieses Verfahren zum schnellen Potenzieren. Entwickle anschließend ein Struktogramm zur Beschreibung des Verfahrens. Du kannst dich am Algorithmus zur ägyptischen Multiplikation orientieren.

Aufgabe 4: Robotersteuerung

Ein Roboter soll Ziegel transportieren. Die Ziegel sind (wie in der Abbildung zu sehen) alle auf einem Feld aufeinder gestapelt. Der Roboter soll den gesamten Ziegelturm zwei Felder weiter in Richtung Süden transportieren.