12  Divide and Conquer

Das Prinzip divide and conquer (teile und herrsche) wurde am Beispiel von Mergesort gezeigt, aber nicht explizit erwähnt. Dieses Prinzip basiert auf der Idee, das kleine Probleme einfacher zu lösen sind als grosse. Deshalb versucht man, das zu lösende Problem in Teilprobleme aufzuteilen und diese, kleineren Probleme, zu lösen um anschliessend die Teillösungen zu einer Lösung für das Ursprungsproblem zusammenzusetzen.

Diese Idee wird oft durch Rekursion umgesetzt. Der Begriff Rekursion kann am besten am Beispiel einer Kindergeschichte erklärt werden:

Es isch e mal en Maa gsi, de hät en hole Zah gha. I dem Zah häts es Truckli gha und i däm Truckli häts es Briefli gha. I dem Briefli isch gstande, es isch e mal en Maa gsi, de hät en hole Zah gha. I dem Zah häts es Truckli gha und id däm Truckli häts es Briefli gha…

Rekursive Funktionen sind entsprechend Funktionen, die sich selber aufrufen. Mergesort rief sich selber auf, um die Liste zu sortieren.

12.1 Fibonacci-Folge

Die Fibonacci-Folge - benannt nach dem Italienischen Mathematiker Leonardo Fibonacci - ist eine Zahlenfolge, in welcher die nächste Zahl die Summe der beiden vorangegangenen Zahlen bildet. In Zahlen sieht das folgendermassen aus:

\[ 1, 1, 2, 3, 5, 8, 13, \dots \]

Die Fibonacci-Folge wird rekursiv deifiniert:

\[ f_n = f_{n-1} + f_{n-2},\ \text{sofern}\ n \geq 3 \]

Sie haben die Fibonacci-Folge bei den Listen bereits programmiert. Obwohl die Programmiung als Liste viel effizienter ist, machen wir hier eine Übung, Fibonacci als rekursive Funktion zu programmieren:

"""Beispiel: fibonacci rekursiv definiert mit Printstatement"""
def fibonacci(n: int) -> int:
    print(f"Es wird fibonacci({n}) ausgeführt.")
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

12.1.1 Aufgabe: Fibonacci-Folge

1. Lesen Sie die Funktion fibonacci. Denken Sie im Kopf durch, was passiert, wenn Sie fibonacci(0) oder fibonacci(1) ausführen. Schreiben Sie Ihre Vermutung auf und führen Sie erst dann die Funktion aus. Vergleichen Sie Ihre Vermutung mit dem Resultat.
2. Denken Sie im Kopf durch, was passiert, wenn Sie fibonacci(2) ausführen. Schreiben Sie Ihre Vermutung auf und führen Sie erst dann die Funktion aus. Vergleichen Sie Ihre Vermutung mit dem Resultat.
3. Bonus: Denken Sie im Kopf durch, was passiert, wenn Sie fibonacci(3) ausführen. Schreiben Sie Ihre Vermutung auf und führen Sie erst dann die Funktion aus. Vergleichen Sie Ihre Vermutung mit dem Resultat.

12.2 Endlose Rekursion

Wenn wir bei der Funktion fibonacci die Zeilen

    if n < 2:
        return 1

weglassen würden, so würde die Funktion endlos sich selber aufrufen, wie im Beispiel der Kindergeschichte.

Meistens wird dieses Problem mit Basisfälle gelöst.

12.3 Beispiel: Anstossen

Gestern assen wir mit 6 Personen zu Abend. Vorgestern mit 140 Personen. Wie oft schlagen die Gläser zusammen wenn alle miteinander anstossen?

Die Aufgabe können wir einfach reduzieren. Wenn ich die 6. Person am Tisch bin, stosse ich mit 5 Personen an. Die 5 Personen müssen untereinander noch anstossen. Das heisst \(a_n = a_{n-1} + (n-1)\).

Für die Rekursive Funktion, brauchen wir somit nur noch die Basisfälle. In unserem Beispiel ist es: Wenn nur 0, 1 oder 2 Personen da sind, wie oft wird angestossen?

Personen	Anstossen
0	0
1	0
2	1

"""Aufgabe: finden Sie 2 Fehler"""
def anstossen(n: int) -> int:
    ## Basisfälle
    if n <= 1:
        return 0
    if n == 2:
        return 2

    return anstossen(n-1) + (n + 1)

"""Test"""
for i in range(10):
    print(f"{i} Personen stossen {anstossen(i)} Mal an.")

i = 140
print(f"{i} Personen stossen {anstossen(i)} Mal an.")

12.3.1 Bonus: Die Gausssche Summenformel

Der Deutsche Mathematiker Carl Friedich Gauss soll nach der Legende seinen Mathematiklehrer bei einer Strafaufgabe überlistet haben. Gemäss dieser Legende soll der Lehrer Gauss (und seinen Klassenkameraden) den Auftrag gegen haben, die Zahlen von 1 bis 100 zusammenzuzählen.

Gauss soll nach kurzer Zeit mit der Lösung zum Lehrer gegangen sein. Gauss’ Lösung basierte auf folgender Formel:

\[ 1 + 2 + 3 + ... + (n-1) + n = \sum_{k=1}^{n}k = \frac{n(n+1)}{2} \]

Diese Formel kann direkt als Funktion implementiert werden. Das entsprechende Beispiel finden sie in der folgenden Zelle.

def gauss_direct(n : int) -> int:
    return int((n*(n+1))/2)

print(f'Die Summe der Zahlen von 1 '
      f'bis 100 ist {gauss_direct(100)}.')

Alternativ kann die Formel aber auch rekursiv implementiert werden. Entsprechend stellt sich die Frage, was wäre ein kleineres, aber grundsätzlich gleichartiges Problem?
Im vorliegenden Fall wäre das einfachste gleichartige Problem, die Summe aus einer Liste von Zahlen mit der Länge 1 und dem Wert 1 zu bilden. Dann ist die Summe auch 1. Als Formel könnte man das so schreiben:

\[ \sum_{k=1}^{n}k = 1, \text{ sofern } n=1 \]

Daraus ergibt sich die Frage, wie man von \(n=100\) zu \(n=1\) kommt.

Für alle Fälle, in denen \(n>1\) ist, gilt

\[ \sum_{k=1}^{n}k = n + \sum_{k=1}^{n-1}k \]

In dieser Formel kann nun immer wieder \(n-1\) eingesetzt werden. Das ist die Rekursion.

Zusammengefasst kann dies folgendermassen dargestellt werden:

\[ \sum_{k=1}^{n}= \left\{ \begin{array}{lll} 1,&n=1&\text{Basisfall}\\ n+\sum\limits_{k=1}^{n-1}k,&\forall n > 1&\text{Rekursionsfall} \end{array} \right. \]

Der Basisfall ist einerseits der einfachste Fall und andererseits auch der letzte Fall, der bearbeitet werden muss.
Beides ist wichtig. Dass der Basisfall der einfachste Fall ist, hilft das Problem zu lösen. Dass der Basisfall der Lezte Fall ist, der bearbeitet werden muss, ermöglicht es, die Rekursion zu beenden.

Im Rekursionsfall steht “\(\forall n > 1\)”. Das \(\forall\) Zeichen ist der sogenannte Allquantor und bedeutet hier “für alle \(n\) grösser als \(1\).

Das eine Problemlösung rekursiv implementiert wird, bedeutet, dass die Funktion sich selber aufruft.
In der folgenden Zelle wird die gausssche Summenformel gemäss obiger Darstellung rekursiv implementiert.

"""Bonusaufgabe: Gauss Rekursiv"""
def gauss_recursive(n : int) -> int:
    # TODO: rekursive Implementation des kleinen Gauss
    pass
    
print(f'Die Summe der Zahlen von 1 '
      f'bis 100 ist {gauss_recursive(100)}.')

12.4 Fakultät

Mit Fakultät (\(n!\)) wird in der Mathematik jene Funktion bezeichnet mit der alle natürlichen Zahlen \(\leq n\) miteinander multipliziert werden.

\[ n! = 1 \cdot 2 \cdot ... \cdot (n-1) \cdot n = \prod\limits_{k=1}^{n} k \]

Als Besonderheit muss mann wissen, dass \(0! = 1\) gilt.

In Python kann dies mit einer for Schleife berechnet werden. In der folgenden Zelle wird eine entsprechende Funktion definiert.

def factorial_loop(n : int) -> int:
    """result wird gleich 1 gesetzt, 
    weil 1 das neutrale Element der
    Multiplikation ist """
    result = 1
    for i in range(1, n+1):
        result *= i
    
    return result

print(f'Das Resultat von 5! ist '
      f'{factorial_loop(5)}.')

Die Funktion kann allerdings auch rekursiv definiert werden. Die Definition sieht dann folgendermassen aus:

\[ n! = \left\{ \begin{array}{lll} 1,&n=0 \lor n=1&\text{Basisfall}\\ n \times (n - 1)!, &\forall n > 1& \text{Rekursionsfall}\\ \end{array} \right. \]

Entsprechend kann eine Funktion zur Berechnung von \(n!\) auch rekursiv implementiert werden.

"""Aufgabe: Fakultät"""
def factorial_recursive(n : int) -> int:
    # TODO: rekursive Implementation der Fakultätsfunktion
    pass
    
print(f'Das Resultat von 5! ist '
      f'{factorial_recursive(5)}.')

12.5 Wörter umdrehen

Gesucht ist eine rekursive Funktion, welche ein Wort rückwärts schreibt (bsp. Kantonsschule nach eluhcssnotnaK).

"""Aufgabe: umdrehen"""
def reverse(s : str) -> str:
    if len(s) == 0 or len(s) == 1:
        return ...
    else:
        head = s[0]
        tail = s[1:]
        return ...

print(reverse('Kantonsschule'))

12.6 Bonus: Anzahl Möglichkeiten zu Zahlen

Ich Verkaufe eine Heft für 6 CHF. Wie viele Möglichkeiten gibt es 5 CHF in Münzen (wir betrachten nur die Münzen 1, 2, 5 CHF).

• \(5+1\)
• \(2+2+2\)
• \(2+2+1+1\)
• \(2+1+1+1+1\)

Es gibt 4 Möglichkeiten.

Um die Frage zu beantworten, kann man die Frage auch aufteilen. Die grösste mögliche Münze ist 5. Also gibt es die Möglichkeiten mit einem 5 Fränkler zu bezahlen (1 Möglichkeit) oder ohne keinem 5 Fränkler zu bezahlen (3 Möglichkeiten). Diese Anzahl Möglichkeiten zusammen addiert ergibt die Möglichkeiten. Die Funktion benötigt 2 Argumente: Den zu bezahlenden Betrag und die grösste erlaubte Münze.

"""
Bonusaufgabe
Studieren Sie die Funktion und füllen Sie die Lücken mit den Auslassungspunkten.
"""
MUENZEN = [1000, 200, 100, 50, 20, 10, 5, 2, 1]
def anz_zahlmöglichkeiten(
    value: int,
    largest_index: int=0,
    ) -> int:
    """Rekursive Funktion"""
    if value < 0:
        return 0
    if value == 0:
        return 1
    if largest_index + 1 == len(MUENZEN):
        # Pay with smales coins
        return 1
    # Pay with largest Coin
    ret = ...

    # Pay without larges coin
    ret += ...
    return ret

print(anz_zahlmöglichkeiten(5))

print(anz_zahlmöglichkeiten(500))  # 6295434
# print(anz_zahlmöglichkeiten(700))  # 40208370
# print(anz_zahlmöglichkeiten(1000)) # 321335887

"""
Bonusaufgabe
Printen Sie die Möglichkeiten!

[5]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]
"""
MUENZEN = [1000, 200, 100, 50, 20, 10, 5, 2, 1]
def print_zahlmöglichkeiten(...)
    ...

print_zahlmöglichkeiten(5)