In diesem Kapitel lernen Sie, wie Sie die while-Schleife in Python verwenden können, um den selben Code wiederholt auszuführen.
Am Ende können Sie:
- Die Wichtigkeit von Wiederholung für Algorithmen verstehen.
- Verstehen, wie ein iterativer Algorithmus funktioniert.
- Die
while-Schleife in Python verwenden. - Iterative Algorithmen mit Python umsetzen.
Nach dem Sie gelernt haben, wie man @lialink(Werte berechnet und speichert) und @lialink(Entscheidungen) trifft, lernen Sie in diesem Kapitel das letzte Puzzleteil, das sie benötigen um Algorithmen vollständig in Python zu Formulieren: Die Wiederholung.
Für den Überblick über den gesamten Kurs kommen Sie @lialink(hier zurück zur Kursübersicht).
Ein wichtiger Bestandteil vieler Algorithmen ist die Wiederholung bestimmter Handlungsanweisungen. Auch bei vielen alltäglichen Handlungen spielt die Wiederholung eine wichtige Rolle.
Beispiel 3: Teigtaschen1 füllen
- Teilen Sie den ausgerollten Teig in gleich große Quadrate.
- Nehmen Sie ein Quadrat und füllen es mit Füllung. ⏺️
- Klappen Sie die Teigtaschen zu. ⏺️
- Wiederholen Sie Schritte 2-3 für jedes Teigquadrat. 🔁
Dies sind Beispiele für eine Iteration. In der Informatik bezeichnet man so die Wiederholung einer Handlungsanweisung mit einem bestimmten Ziel. In der Programmierung spricht man auch von Schleifen.
Betrachten Sie die obigen Beispiele, sehen Sie die Gemeinsamkeiten: Jedes Beispiel besteht aus einem Schleifenrumpf (hier markiert mit dem Symbol ⏺️) und einer Schleifenkontrollanweisung (hier markiert mit 🔁). Der Schleifenrumpf enthält alle Anweisungen, die wiederholt werden können. Die Schleifenkontrollanweisung erklärt, unter welchen Bedingungen die Schleife wiederholt wird.
Diese drei Beispiele stehen für drei Schleifentypen:
- Bedingungsschleife: Wiederholt bis eine Bedingung erfüllt ist (siehe Beispiel 1, Treppensteigen)
- Zählschleife: Wiederholt eine bestimmte Anzahl an Malen. (siehe Beispiel 2, Reifenwechsel)
- Mengenschleife: Wiederholt den Schleifenrumpf für jedes Element einer Menge (siehe Beispiel 3, Teigtaschen)
Alle drei Schleifentypen werden wir in diesem Kurs mit Python umsetzen.2
Welche Art von Schleifen benötigen die folgenden Algorithmen?
"Eine Musikplayer App spiele der Reihe nach alle Lieder einer Playlist"
[[Bedingungsschleife|Zählschleife|(Mengenschleife)]]
"Eine Klimaanlage kühlt den Raum so lange die Temperatur über 20 Grad ist."
[[(Bedingungsschleife)|Zählschleife|Mengenschleife]]
"Eine Eieruhr zählt die Sekunden bis die eingestellte Zeit abgelaufen ist und klingelt dann."
[[Bedingungsschleife|(Zählschleife)|Mengenschleife]]
Wir versuchen in der Informatik die unterschiedlichsten Problemstellungen mit Hilfe von Algorithmen zu lösen. Die Wiederholung, oder auch Iteration ist dafür ein wichtiger Grundbaustein.
Als ein Beispiel dafür wollen wir die Berechnung der Fakultät betrachten:
Die Mathematik definiert die Fakultät
$$
n! = \prod_{k=1}^{n} k
$$
Oder in Worten: das Produkt aller Zahlen von 1 bis n.
Für
Als iterativen Algorithmus berechnen wir die Fakultät folgendermaßen:
- Setze Variablen
iundfakjeweils auf 1 - Wiederhole die Schritte 3 und 4 so lange
i <= n: - Setze
fakauf das Produktfak * i - Erhöhe
ium 1 - Gebe das Ergebnis
fakzurück.
flowchart TD
i[Setze i = 1 und fak = 1]
condition{{i <= n?}}
update_fak[Setze fak = fak * i]
increment_i[Erhöhe i um 1]
return_result[Gebe fak zurück]
i --> condition
condition --> |Ja| update_fak
condition --> |Nein| return_result
update_fak --> increment_i
increment_i --> condition
Eine Schleife kann in Python mit dem Schlüsselwort while eingeleitet werden. Der Schleifenrumpf wird so lange wiederholt, wie die Bedingung wahr ist:
while BEDINGUNG:
# Dieser Code wird wiederholt
# solange BEDINGUNG wahr istgeheimzahl = 42
eingabe = 0
print("Errate die Geheimzahl!")
while eingabe != geheimzahl:
eingabe = int(input())
print("Richtig geraten!")@Pyodide.eval
Dieses Programm wiederholt so lange die Frage nach der Geheimzahl, bis die richtige Zahl erraten wird.
Das ist ein Beispiel für eine Bedingungsschleife mit while.
Sie haben bereits den Algorithmus zur Berechnung der Fakultät gesehen.
Hier ist der Algorithmus in Python implementiert:
n = 5
i = 1
fak = 1
while i <= n:
fak = fak * i
i = i + 1
print(fak)@Pyodide.eval
Auch wenn hier eine Bedingung verwendet wird, handelt es sich eigentlich um eine Zählschleife, da die Schleife genau i realisiert, die bei 1 beginnt und in jedem Schleifendurchlauf um 1 erhöht wird.
Berechnen Sie
[[1405006117752879898543142606244511569936384000000000]]
ändern sie den obigen Algorithmus so ab, dass er die Summe der Zahlen von 1 bis 1000 berechnet.
[[500500]]
[[?]] Verwenden Sie direkt das obige Code-Fenster um den Algorithmus zu ändern.
[[?]] Beachten Sie: Während das leere Produkt
n = 1000
i = 1
summe = 0
while i <= n:
summe = summe + i
i = i + 1
print(summe)@Pyodide.eval
Von syntactic sugar oder auch syntaktischem1 Zucker spricht man, wenn eine Programmiersprache eine spezielle Syntax für eine häufige Operation bereitstellt. Diese Kurzschreibweisen sind nicht notwendig, erleichtern aber das Schreiben von Code.
Im Algorithmus zur Berechnung der Fakultät, sah der Schleifenrumpf so aus:
fak = fak * i
i = i + 1Die Kombination aus arithmetischer Operation und Zuweisung ist so häufig, dass Python eine Kurzschreibweise dafür anbietet. Wir können einfach
fak *= i
i += 1schreiben
Die Kurzschreibweise += und *= sind nur zwei Beispiele. Analog gibt es auch -=, /=, **=, //= und %= und mehr.
Hier sehen Sie ein Beispiel, das einige dieser Operatoren einsetzt:
x = 5
x += 5
x *= 2
x -= 4
x **= 0.5
x %= 3Lesen Sie eine Ganzzahl
für
- Die Summe der ersten
$2$ ungeraden Zahlen ist$1+3=4$ , - die Summe der ersten
$3$ ungeraden Zahlen ist$1+3+5=9$ , - die Summe der ersten
$4$ ungeraden Zahlen ist$1+3+5+7=16$ .
Es fällt auf, dass die Summe der ersten
Schreiben Sie ein Programm, das überprüft, ob diese Vermutung stimmt. Es reicht wenn Sie es für alle
Die alternierende Reihe ist eine mathematische Reihe, die sich durch das Vorzeichen der Summanden auszeichnet. Die Summe der alternierenden Reihe ist definiert als:
Die Summe der alternierenden Reihe konvergiert gegen den natürlichen Logarithmus von 2.
Schreiben Sie ein Programm, das die Summe der alternierenden Reihe und damit
Fizzbuzz ist ein Kinderspiel, bei dem Kinder abwechseln von 1 auf 100 zählen. Dabei ersetzen sie jedes Vielfache von 3 durch "Fizz", jedes Vielfache von 5 durch "Buzz" und jedes Vielfache von 15 durch "FizzBuzz"1.
Man zählt also:
"1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz"
und so weiter.
Schreiben Sie ein Programm, das von 1 bis 100 zählt und dabei die Zahlen durch "Fizz", "Buzz" oder "FizzBuzz" ersetzt, wenn sie die entsprechenden Bedingungen erfüllen.
In der Mathematik definiert man die Quadratwurzel einer Zahl folgendermaßen
Diese Definition erlaubt uns nicht, auf direktem Weg einen Algorithmus aus ihr herzuleiten.
Zwar kann man mit ihr überprüfen, ob
Ein erster Ansatz könnte also sein, einfach verschiedene Werte für
Wollen wir beispielsweise
-
$2$ ,$3$ und$4$ sind zu klein, da ihre Quadrate$4$ ,$9$ und$16$ alle kleiner als$21$ sind. -
$5$ ist zu groß, da$5^2=25$ . -
$\sqrt{21}$ muss also zwischen$4$ und$5$ liegen.
Nun haben wir den Suchbereich eingegrenzt.
Betrachten wir die Mitte zwischen
Nun wissen wir also
Eine solche Vorgehensweise nennt man Näherungsverfahren.
Ein Näherungsverfahren zur Berechnung der Wurzel einer Zahl nennt man auch „Babylonisches Wurzelziehen“ oder das „Heron-Verfahren“
Auf dieser Keilschrifttafel aus dem alten Babylon ist ein Quadrat mit Diagonalen und der Wert von
Im Jahr 60 n. Chr. beschrieb Heron von Alexandria dann dieses Verfahren zum ersten Mal in einem Buch, weshalb es auch „Heron-Verfahren“ genannt wird.
Die Wurzel einer Zahl S können wir mit dieser Methode folgendermaßen bestimmen:
- Wir setzen einen Schätzwert für die Wurzel
$x_0\approx \sqrt{S}$ - im nächsten Schritt bilden wir den Durchschnitt unseres aktuellen Schätzwertes
$x_n$ mit$\frac{S}{x_n}$ und gewinnen so eine verbesserte Näherung der Wurzel$x_{(n+1)}$ : $$ x_{(n+1)}=\frac{1}{2}\left(x_n+\frac{S}{x_n}\right) $$ - Berechne
$x_n^2$ und wiederhole Schritt 2 bis der Wert nahe genug an S ist.
Hier können Sie beobachten, wie effizient dieser Algorithmus arbeitet. Sie haben die Möglichkeit, den Wert von
@embed(style="height: 1000px; width:100%; border: none")
Schreiben Sie ein Programm, das die Quadratwurzel einer Zahl nach der babylonischen Methode berechnet.
zur Erinnerung: Die nächste Näherung
Wie nahe sie an der richtigen Lösung sind, sehen Sie an der Differenz zwischen
Ist diese Differenz kleiner als
Hier ist ein Codegerüst als Ausgangspunkt. Dieses setzt
S = 1764
x = 50
while # Fügen Sie hier die Bedingung ein
# Fügen Sie hier den Schleifenrumpf ein
print("Die Wurzel von", S, "ist", x)@Pyodide.eval
Schreiben Sie ein Programm, das überprüft, ob eine gegebene Zahl eine Primzahl ist.
Eine Primzahl ist eine natürliche Zahl, die größer als
Die Collatz-Folge ist eine mathematische Folge, die durch folgende Regeln definiert ist:
- Wir starten mit einer beliebigen natürlichen Zahl
$n>0$ . - Ist die aktuelle Zahl gerade, so teilen wir sie durch
$2$ . - Ist die aktuelle Zahl ungerade, so multiplizieren wir sie mit
$3$ und addieren$1$ .
Die Folge endet, wenn die Zahl
Hier die Folge für den Startwert
sehr viel länger ist die Folge für
$$ 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1$$
Schreiben Sie ein Programm, das die Collatz-Folge für eine gegebene Zahl berechnet und die Anzahl der Schritte ausgibt, die benötigt wurden, um
Die Collatz-Vermutung besagt, dass die Collatz-Folge für jede natürliche Zahl
Schreiben Sie ein Programm, das die Collatz-Vermutung für alle Zahlen bis
[[ 525 ]]
Die längste Folge unter einer Million beginnt mit der Zahl
Footnotes
-
in vielen Ländern isst man gefüllte Teigtaschen, man nennt sie z.B. Maultaschen, Пельмени, 饺子, ხინკალი, Ravioli, Mantı, Pierogi usw. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8
-
Da wir Auflistungen oder Mengen noch nicht in Python darstellen können, werden wir uns zunächst auf die Bedingungsschleife und die Zählschleife konzentrieren. Im nächsten Kapitel werden wir dann die Mengenschleife kennenlernen. ↩ ↩2 ↩3