Benutzer-Werkzeuge

Webseiten-Werkzeuge


schule:rekursion

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
schule:rekursion [2017-01-26 14:26]
marco.bakera +Übung Flachklopfen.
schule:rekursion [2021-06-10 07:15] (aktuell)
pintman [Beispiel: Anzahl Elemente einer Liste]
Zeile 37: Zeile 37:
  
 <code python> <code python>
-anzahl(liste):+def anzahl(liste):
   anzahl = 0   anzahl = 0
   for element in liste:   for element in liste:
Zeile 48: Zeile 48:
  
 <code python> <code python>
-anzahl(liste):+def anzahl(liste):
   if liste ist leer:   if liste ist leer:
     return 0     return 0
  
   else:   else:
-    liste_kleiner = liste.entferneErstesElement()+    liste_kleiner = liste[1:]  #  entferne erstes Element
     return 1 + anzahl(liste_kleiner)     return 1 + anzahl(liste_kleiner)
 </code> </code>
 +
 +Erinnerung: mit ''liste[a:b]'' wird der Teil von Index a bis zum Index b-1 aus einer Liste ausgelesen. 
 +Wird a oder b weggelassen, werden der Anfang Anfang bzw. das Ende der Liste verwendet. Dies nennt man
 +[[https://www.learnbyexample.org/python-list-slicing/|list slicing]].
  
  
Zeile 112: Zeile 116:
 {{:schule:prog:strecke_zwischen_zwei_punkten.png?direct|}} {{:schule:prog:strecke_zwischen_zwei_punkten.png?direct|}}
  
-In den [[https://tbs1.de/owncloud/index.php/s/al3BJaHnhXS7WlM|Materialien]] findest du Informationen darüber, wie eine Strecke zwischen zwei Punkten A und B mit einem rekursiven Verfahren auf dem Bildschirm ausgegeben werden kann. +Bei den Materialien findest du Informationen darüber, wie eine Strecke zwischen zwei Punkten A und B mit einem rekursiven Verfahren auf dem Bildschirm ausgegeben werden kann. 
  
 Wie sieht der einfache Fall aus? Wie sieht der einfache Fall aus?
  
-Vervollständige den Algorithmus in dem VisualStudio-Projekt entsprechend.+Vervollständige den folgenden Algorithmus zum Zeichnen einer Strecke. 
 + 
 +<code python> 
 +from tkinter import Tk, Canvas 
 + 
 +class App: 
 +    def __init__(self): 
 +        fenster = Tk() 
 +         
 +        self.canv = Canvas(fenster, width=200, height=200) 
 +        self.canv.pack() 
 + 
 +        self.strecke(10, 10, 150, 180) 
 +        fenster.mainloop() 
 + 
 +    def markiere(self, x, y): 
 +        self.canv.create_rectangle(x,y,x+1,y+1) 
 + 
 + 
 +    def strecke(self, ax, ay, bx, by): 
 +        # Hier muss eine Strecke rekursiv gezeichnet werden 
 +        # if Punkte a und b benachbart: 
 +        #   zeichne Pixel a und b 
 +        # else: 
 +        #   berechne mittelpunkt m 
 +        #   zeichne Strecke von a bis m 
 +        #   zeichne Strecke von m bis b 
 +        pass 
 + 
 +app = App() 
 +</code> 
 + 
 +===== Übung Kochkurve ===== 
 + 
 +{{:schule:prog:kochkurve.png|}} 
 + 
 +Eine weitere Anwendung von Rekursion findet sich in selbst-ähnlichen Kurven aus der Mathematik und der Natur. Die [[wpde>Koch-Kurve]] ist eine solche Figur, die mit Turtle-Grafiken erstellt werden kann. 
 + 
 +Verwende die folgende Vorlage und zeichne damit eine Kochkurve. 
 + 
 +<code python kockurve.py> 
 +import turtle 
 + 
 +""" 
 +Die Turtle kann mit folgenden Befehlen bewegt werden: 
 + 
 +tutle.forward(distanz) bewegt die Schildkröte in Blickrichtung 
 +turtle.right(winkel) dreht die Schildkröte nach rechts. 
 +tirtle.left(winkel) dreht die Schildkröte nach links. 
 +""" 
 + 
 +def kochkurve(laenge, tiefe): 
 +    """Zeichnet eine Kochkurve. 
 +    laenge beschreibt die Länge des aktuellen Streckenabschnitts 
 +    tiefe steht für die Rekursionstiefe.""" 
 +    if tiefe == 0: 
 +        """Gehe nach vorn.""" 
 +    else: 
 +        """Zeichne eine Kochkurve, drehe nach links, zeichne wieder eine Kurve,  
 +        drehe nach rechts, zeichne erneut, drehe nach links und zeichne den Schluss.  
 +        _/\_ """ 
 + 
 +# Starte das Programm 
 +turtle.reset() 
 +turtle.speed(5) 
 + 
 +kochkurve(300, 2) 
 + 
 +</code>
  
 ===== Übung Grundrechenarten ===== ===== Übung Grundrechenarten =====
Zeile 153: Zeile 225:
 ===== Übung Flachklopfen ===== ===== Übung Flachklopfen =====
  
-Die Methode ''flach_klopfen'' nimmt eine Liste aus Listen entgegen und gibt eine flache Liste zurück, die nur noch die Elemente der Einzellisten enthält.+Die Methode ''flach_klopfen'' nimmt eine Liste aus Listen entgegen und gibt eine flache Liste zurück, die nur noch die Elemente der Einzellisten enthält. Diese Listen könnten z.B. Verzeichnisse und Dateien in diesen Verzeichnissen in einem Dateisystem darstellen. Jeder Liste innerhalb einer Liste steht dann für ein Unterverzeichnis.
  
 <code> <code>
Zeile 171: Zeile 243:
 [1,2,3] [1,2,3]
 </code> </code>
 +
 +===== Übung umdrehen =====
 +
 +Die Methode ''umdrehen'' nimmt eine Liste entgegen und dreht diese Liste um, so dass anschließend alle Elemente in umgedrehter Reihenfolge in der Liste auftauchen.
 +
 +<code>
 +>>> umdrehen([])
 +[]
 +>>> umdrehen([1,2,3])
 +[3, 2, 1]
 +</code>
 +
 +===== Live Coding mit Fluxus =====
 +
 +Die Programmierumgebung [[live_coding#teil_1fluxus|Fluxus]] kann für das Live-Coding verwendet werden und nutzt in der Programmiersprache rekursive Mechanismen.
 +
 +<html>
 +<iframe width="560" height="315" src="https://www.youtube.com/embed/sS7WpYWm8PQ?rel=0" frameborder="0" allowfullscreen></iframe>
 +</html>
 +
 +
 ===== Probleme rekursiver Algorithmen ===== ===== Probleme rekursiver Algorithmen =====
  
Zeile 177: Zeile 270:
   * Hoher Speicherplatzbedarf - Jeder Aufruf benötigt Speicherplatz für lokale Variablen   * Hoher Speicherplatzbedarf - Jeder Aufruf benötigt Speicherplatz für lokale Variablen
   * Unendliche Rekursion - Wenn man nicht aufpasst, enden die rekursiven niemals.   * Unendliche Rekursion - Wenn man nicht aufpasst, enden die rekursiven niemals.
 +===== Rekursive Abkürzungen =====
 +
 +Auch in anderen Gebieten der Informatik hat sich die Rekursion etabliert. So gibt es [[wpde>Rekursives Akronym|rekursive Abkürzungen]]: 
 +
 +  * PHP (PHP Hypertext Preprocessor)
 +  * LAME (LAME Ain’t an Mp3 Encoder)
 +  * WINE (WINE Is Not an Emulator)
 +  * YAML (YAML Ain't Markup Language)
 +
 ===== Links ===== ===== Links =====
  
-  * [[https://tbs1.de/owncloud/index.php/s/al3BJaHnhXS7WlM|Materialien]] 
   * [[https://www.youtube.com/watch?v=gYpMz63WAjM|Ein Kran trägt einen Kran trägt einen Kran (Video)]]   * [[https://www.youtube.com/watch?v=gYpMz63WAjM|Ein Kran trägt einen Kran trägt einen Kran (Video)]]
schule/rekursion.1485437181.txt.gz · Zuletzt geändert: 2017-04-19 08:39 (Externe Bearbeitung)