Show pageOld revisionsBacklinksBack to top This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong. ====== Rekursion ====== to be written * Fakultät rekursiv (schon bei Funktionen) * divide et impera / divide and conquer / teile und herrsche [[https://de.wikipedia.org/wiki/Rekursion#Rekursive_Grafiken|Wikipedia Rekursion]] Sierpinski rekursiv ist schon gut, eventuell turtle Grafik, Bilder von Wikipedia? Hanoi? <WRAP round todo> [[https://de.wikipedia.org/wiki/Cantor-Menge|Cantor-Menge]] im Textmodus: <code python> def cantor(x): if x == 0: return "*" else: s = cantor(x - 1) return s + (3**(x-1)) * "-" + s for i in range(5): print(cantor(i)) </code> </WRAP> <WRAP round todo> <code python> from gpanel import * def zeichne(x, y, l, xr, yr, rekursionstiefe): if rekursionstiefe == 0: line(x, y, x + l * xr, y + l * yr) else: xl = -yr yl = xr zeichne(x, y, l/3, xr, yr, rekursionstiefe - 1) zeichne(x + 2*l/3 * xr, y + 2*l/3 * yr, l/3, xr, yr, rekursionstiefe - 1) zeichne(x + l/3 * xr, y + l/3 * yr, l/3, xl, yl, rekursionstiefe - 1) zeichne(x + l/3 * (xr + xl), y + l/3 * (yr + yl), l/3, xr, yr, rekursionstiefe - 1) zeichne(x + l/3 * (2 * xr + xl), y + l/3 * (2 * yr + yl), l/3, -xl, -yl, rekursionstiefe - 1) makeGPanel(Size(1000, 1000)) window(-10, 1010, -10, 1010) title("Key 'Esc': escape") zeichne (0,0, 1000, 1, 0, 6) </code> </WRAP> <WRAP round todo> Das folgende Programm findet alle magischen 3x3-Quadrate durch stupides Ausprobieren. Die am Ende ausgegebene Zahl ist die Fakultät welcher Zahl? Wenn man die Variable n auf den Wert 4 endet, braucht das Programm sehr lange - grob überschlagen auf meinem Rechner 3 Jahre! Wer kann das Programm verbessern? <code python> # Erzeuge magisches Quadrat import time n = 3 def magisch(): for x in range(0,n): zeilensumme = 0 spaltensumme = 0 for y in range(0,n): spaltensumme = spaltensumme + a[x][y] zeilensumme = zeilensumme + a[y][x] if zeilensumme != summe or spaltensumme != summe: return False erste_diagonalsumme = 0 zweite_diagonalsumme = 0 for x in range(0,n): erste_diagonalsumme = erste_diagonalsumme + a[x][x] zweite_diagonalsumme = zweite_diagonalsumme + a[x][n - 1 - x] if erste_diagonalsumme != summe or zweite_diagonalsumme != summe: return False return True def trage_ein(e): global anzahl for x in range(0, n): for y in range(0, n): if a[x][y] == 0: a[x][y] = e if e > 1: trage_ein(e - 1) else: anzahl = anzahl + 1 if anzahl % 100000 == 0: print(anzahl) print(time.clock() - startzeit) if magisch(): print(a) a[x][y] = 0 a = [[0 for y in range(0,n)] for x in range(0,n)] anzahl = 0 summe = n * (n * n + 1) // 2 startzeit = time.clock() trage_ein(n * n) print(anzahl) print(time.clock() - startzeit) </code> </WRAP> ===== Link zur Kursseite ===== [[lehrkraefte:snr:informatik:glf21|Zur Kursseite]] lehrkraefte/snr/informatik/python/rekursion.txt Last modified: 2021/12/03 14:59by Olaf Schnürer