====== Algorithmen II ======

=====  Struktogramme und Python =====

==== Aufgaben A ====

   * Folgende Aufgaben hast du ev. bereits mit [[gf_informatik:algorithmen_i#aufgaben_c|Struktogrammen gelöst]]. Studiere nochmals deine jeweiligen Lösungen und stelle sicher, dass du jeden Schritt verstehst.
   * Schreibe nachher den zugehörigen Python-Code.
   * Verwende keine vordefinierten Funktionen wie z.B. `max()` oder `sorted()`, programmiere alles selber.

=== Aufgabe A1: Maximum ===

   * Teil 1: Zwei Zahlen sollen eingegeben und die grössere der beiden Zahlen ausgegeben werden. Die grössere von zwei gleich grossen Zahlen ist einfach diese eine Zahl.
   * Teil 2: Schreibe Code um als Funktion `max2(a, b)`, die das Maximum von a und b mit `return` _zurückgibt_. Die _Eingabe_ (`input`) und die _Ausgabe_ (`print`) sollen ausserhalb der Funktion erfolgen.
   * Teil 3: Schreibe eine Funktion `max3(a, b, c)`, die das Maximum von drei Zahlen zurückgibt. _Verwende dazu die `max2` Funktion!_

<nodisp 1>
++++Lösung|
<code python>
def max2(a, b):
    if a > b:
        return a
    else:
        return b

def max3(a, b, c):
    return max2(max2(a, b), c)

print(max3(int(input('a')), int(input('b')), int(input('c'))))
</code>
++++
</nodisp>
=== Aufgabe A2: Sortieren ===

   * Teil 1: Drei Zahlen sollen eingegeben werden und danach in absteigender Reihenfolge der Grösse ausgegeben werden.

<nodisp 1>
++++Lösung:|
<code python>
def sort(a, b, c):
    if a > b:
        if b > c:
            print(a, b, c)
        elif a > c:
            print(a, c, b)
        else:
            print(c, a, b)
    elif b > c:
        if a > c:
            print(b, a, c)
        else:
            print(b, c, a)
    else:
        print(c, b, a)

sort(input(), input(), input())
</code>
++++
</nodisp>

<nodisp 2>
   * (Ausgeblendet): Teil 2: Schreibe Code um als Funktion `my_sort(a,b,c)`, die die drei Zahlen a,b,c sortiert und richtig geordnet in eine Liste schreibt. Die Liste wird zurückgegeben.
</nodisp>

=== Aufgabe A3: Subtraction Game ===

   * Spiele mit einer Kollegin/einem Kollegen nochmals das Subtraction Game (Spiel mit 21 Stiften).
   * Programmiere es dann in Python. Die Spielerin soll gegen den Computer spielen und beginnen dürfen. Der Computer soll immer gewinnen, wenn die Spielerin einen unklugen Zug macht.

=== Aufgabe A4: Ratespiel (optional: mittel) ===

Eine geheime Zahl zwischen 0 und 100 wird in einer Variablen gespeichert. Der Spieler versucht solange die geheime Zahl zu erraten, bis er erfolgreich ist.

Zusatzpunkte:
   * Das Programm gibt dem Spieler Tipps, z.B. ’Ausgabe: «Die eingegebene Zahl ist zu klein»’
   * Die Anzahl Fehlversuche wird gezählt und am Schluss ausgegeben.

=== Aufgabe A5: Ratespiel umgekehrt (optional: mittel) ===

Der Spieler merkt sich eine geheime Zahl zwischen 0 und 100, der Computer soll sie erraten. Der Spieler soll dem Computer bei jedem Versuch mitteilen, ob die gesuchte Zahl kleiner oder grösser als die Vermutung ist:
  * Ist die geheime Zahl kleiner als die Vermutung, muss der Spieler `<` eingeben.
  * Ist die geheime Zahl grösser als die Vermutung, muss der Spieler `>` eingeben.
  * Ist die geheime Zahl erraten, soll `=` eingegeben werden.

Zusatzpunkte:
  * Der Computer detektiert, wenn der Spieler gelogen hat.


===== Mathematische Algorithmen =====


==== Aufgaben B ====

=== Aufgabe B1: Einfache (math.) Algorithmen ===

Schreibe für jede Aufgabe eine Funktion, die passende Argumente entgegennimmt und das Resultat zurück gibt.
Schreibe alle Funktionen selbst und verwende nur ganz rudimentäre Sprachelemente und keine vordefinierten Funktionen.
   - Multiplikation durch Additionen ausdrücken
   - Hoch-Rechnen durch Multiplikation ausdrücken 
   - Hoch-Rechnen durch Additionen ausdrücken 
   - Ganzzahldivision mit Rest mit Addition und Subtraktion
   - Entscheiden ob eine beliebige Zahl eine Zweierpotenz ist oder nicht

++++Hinweise:|
  * $7*3 = 0 + 3 + 3 + 3 + 3 + 3 + 3 + 3$
  * Wir benötigen eine Schleife, die 7 mal 3 zum Resultat addiert.
  * Ausserhalb der Schleife deklarieren wir eine Variable, die das Resultat enthält und zu Beginn 0 ist, z.B. `result = 0`.
  * Wie lautet die Rechnung für das Hoch-Rechnen mit Multiplikation? Und was ist der Initialwert von `result`?
++++

<nodisp 1>
++++Lösung:|
<code python>
def multiply(a, b):
    """Multipliziert zwei natürliche Zahlen ohne Verwendung der Python-Multiplikation."""
    result = 0  # Null ist das neutrale Element bezüglich der Addition.
    while b > 0:
        result = result + a
        b = b - 1
    return result
 
def exponentiate(a, b):
    """Berechnet a hoch b nur mit Addition."""
    result = 1  # Eins ist das neutrale Element bezüglich der Multiplikation.
    while b > 0:
        result = multiply(result, a)
        b = b - 1
    return result
 
def divide(dividend, divisor):
    """Berechnet die Ganzzahldivision mit Rest nur mit Addition & Subtraktion."""
    quotient = 0
    while dividend >= divisor:
        dividend = dividend - divisor
        quotient = quotient + 1
 
    # Jetzt ist dividend kleiner als divisor - dividend ist nun der Rest.
 
    # In Python können wir mehrere Werte zurückgeben, durch Komma getrennt:    
    return quotient, dividend
 
def is_power_of_2(n):
    """Gibt True zurück, falls n eine Zweierpotenz ist, sonst False."""
    test = 1
    while test < n:
        test = multiply(test, 2)
    return test == n
 
a = input("a")
b = input("b")
print(str(a) + " * " + str(b) + " = " + str(multiply(a, b)))
print(str(a) + " ^ " + str(b) + " = " + str(exponentiate(a, b)))
 
quotient, rest = divide(a, b)
print(str(a) + "/" + str(b) + " = " + str(quotient) + " Rest " + str(rest))
 
print(str(a) + " ist eine Zweierpotenz: " + str(is_power_of_2(a)))
print(str(b) + " ist eine Zweierpotenz: " + str(is_power_of_2(b)))
</code>
++++
</nodisp>

=== Aufgabe B2: Quersumme ===
Die [[wpde>Quersumme]] einer Zahl ist die Summe all ihrer Ziffern. Die Quersumme beispielsweise von $413$ ist $4 + 1 + 3 = 8$.

Schreibe eine Funktion `quersumme(x)`, die die Quersumme von `x` zurückgibt!

++++Zuerst ohne diese Hinweise probieren!|
  * Benütze `x % 10` um den Wert der hintersten Ziffer zu berechnen!
  * Mit einer geeigneten Division kannst du auf die nächste Stelle vorrücken.
  * Wann muss die `while`-Schleife abbrechen?
++++

<nodisp 1>
++++Lösung:|
<code python>
def quersumme(x):
    summe = 0
    while x > 0:
        ziffer = x % 10
        summe = summe + ziffer
        x = x // 10
    return summe

print(quersumme(413))
</code>
++++
</nodisp>

==== Primzahlen ====
=== Theorie ===

   * Was ist eine Primzahl?
     * Wenn nötig: Nachlesen auf [[wpde>Primzahl]] (erster Satz)!
   * Primzahl-Test:
     * Eine Funktion, die herausfindet (Also `True` oder `False` _zurückgibt_), ob eine Zahl prim ist.
     * Wieviele Parameter hat die Funktion `is_prime`?
   * Teiler-Test:
     * Eine Funktion, die herausfindet (_zurückgibt_), ob eine Zahl `t` ein Teiler ist der Zahl `n`.
     * Wieviele Parameter hat die Funktion `is_divisor`?


=== Auftrag zu Primzahlen ===

   * in 2er-Gruppen auf Papier (kein Python!)
   * Vorgehen:
     * Algorithmus für Primzahltest überlegen, in 2er-Gruppe besprechen,Notizen machen: Variablen? Schleifen?
     * Mit Lehrperson besprechen
     * In Python: Funktion `is_prime(n)` implementieren
     * Fertig? siehe Zusatzauftrag und Aufgaben unten

++++Hinweise|
  * Schreibe zuerst die Funktion `is_divisor` und teste sie:
    * Wie finden wir heraus, ob `t` ein Teiler von `n` ist? Können wir das mit einer einzelnen Berechnung tun statt als [[gf_informatik:algorithmen_i#aufgabe_c4_zusatzaufgabeteilertest|Schleife]]?
      * **Hinweis**: Schau dir dir [[gf_informatik:programmieren_ii:variablen_verzweigungen_schleifen#einfache_rechnungen|mathematischen Operationen in Python]] nochmals an.
      * Welche Operation könnte praktisch sein, um die Teilbarkeit zu entscheiden?
      * **Hinweis 2**: `t` teilt `n` genau dann, wenn der Rest der Division $\frac{n}{t}$ null ist...
  * Schreibe `is_prime` erst, wenn `is_divisor` funktioniert.
    * Wie hilft uns `is_divisor` bei der Umsetzung des Primzahltests?
++++

**Zusatzauftrag:**

   * Wie kannst du den Algorithmus optimieren? Mache einen Plan und diskutiere diesen mit der Lehrperson.
   * Schreibe eine optimierte Version der Funktion unter dem Namen `is_prime_2`


<nodisp 2>
++++Lösung:|
<code python>
import math

def is_divisor(dividend, divisor):
    """Gibt True zurück, wenn divisor ein ganzzahliger Teiler von dividend ist, sonst False."""
    return dividend % divisor == 0

def is_prime(n):
    """Gibt True zurück, falls n eine Primzahl ist, sonst False."""
    if n < 2:
        return False
    i = 2
    # Es reicht, bis zur Wurzel von n zu testen - gäbe es einen grösseren Teiler t so dass
    # t*x == n, dann müsste x kleiner sein als Wurzel(n) und wir hätten x bereits gefunden.
    while t <= math.sqrt(n):
        if is_divisor(n, t):
            # Wir haben einen Teiler gefunden -> keine Primzahl, beenden.
            return False
        t = t + 1
    # Keinen Teiler gefunden -> wir haben eine Primzahl!
    return True
</code>
++++
</nodisp>


=== Aufgabe B3: Primfaktorzerlegung ===

   * Jede positive natürliche Zahl kann geschrieben werden als Multiplikation von Primzahlen. Diese Primfaktorzerlegung (PFZ) ist eindeutig.
   * Bsp. Primfaktoren für $45$ sind: $3,3,5$ (weil: $3\cdot3\cdot5 = 45$)
   * Primfaktorzerlegung ist extrem wichtig z.B. für Verschlüsselungsalgorithmen
   * Schreibe eine Funktion `prime_factors(x)`, die eine Zahl x entgegennimmt und deren (geordnete) Primfaktoren von x ausgibt.

<nodisp 2>
++++Lösung:|
Mit den Funktionen `is_prime` und `is_divisor` von oben:
<code python>
def next_prime(n):
    """Gibt die nächstgrössere Primzahl grösser als n zurück."""
    next = n + 1
    while not is_prime(next):
        next = next + 1
    return next

def prime_factors(n):
    """Gibt die Prim-Faktoren von n in aufsteigender Folge zurück."""
    factor = 2  # first prime
    remainder = n
    # Divide n by the increasing prime numbers until we reach 1.
    while remainder > 1:
        # For each prime, divide the remainder as long as the prime is
        # a divisor.
        while is_divisor(remainder, factor):
            remainder = remainder / factor
            print(factor)
            # yield factor
        
        # remainder can no longer be divided by factor -> try with the next prime.
        factor = next_prime(factor)

prime_factors(int(input()))
</code>
++++
</nodisp>

==== Weitere anspruchsvolle Algorithmen ====

=== Aufgabe B4: ggT bestimmen ===

   * siehe [[gf_informatik:programmieren_zusatzaufgaben#euklidischer_algorithmus|Euklidischer Algorithmus]]
   * Schreibe eine Funktion `ggT(x,y)`, die zwei Zahlen `x` und `y` entgegennimmt und den ggT der beiden zurückgibt.

<nodisp 2>
++++Lösung:|
<code python>
def ggt(a, b):
    """Berechnet den grössten gemeinsamen Teiler von a und b."""
    while b > 0:
        rest = a % b
        a = b
        b = rest
    return a

print(ggt(544, 391))
</code>
++++
</nodisp>


=== Aufgabe B5: Quadratwurzel ziehen ===

   * siehe [[wpde>Heron-Verfahren]]
   * Schreibe eine Funktion `wurzel(x)`, die die Wurzel von `x` auf `0.0001` genau berechnet.

<nodisp 2>
++++Lösung:|
<code python>
def wurzel(n, precision=0.0001):
    """Quadratwurzel nach Heron."""
    # Grundidee: Ein Rechteck mit Fläche n
    # wird schrittweise in ein Quadrat transformiert.
    # Invariante: a * b == n
    # Die wahre Quadratwurzel liegt zwischen a und b.
    a = n
    b = 1
    while a - b > precision:
        a = (a + b) / 2  # Mittelwert der beiden Seiten.
        b = n/a
    return a
 
print(wurzel(225))
</code>
++++
</nodisp>