Algorithmen II [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Algorithmen II ======

=====  Struktogramme und Python =====
<html><script type="module" src="https://bottom.ch/ksr/ed/bottom-editor.js"></script></html>

==== 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 (`input`) und die grössere der beiden Zahlen ausgegeben werden. Sind die Zahlen gleich gross, soll einfach die Zahl ausgegeben (`print`) werden.
   * Teil 2: Schreibe Code um als Funktion `max2(a, b)`, die das Maximum von `a` und `b` mit `return` _zurückgibt_. Die Eingabe und die Ausgabe 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|
<html><bottom-editor>
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'))))
</bottom-editor></html>
++++
</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:|
<html><bottom-editor>
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())
</bottom-editor></html>
++++
</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 =====

Mit _iterativen_ Algorithmen berechnen wir Schritt für Schritt das gewünschte Resultat. Das Resultat wird in einer Variable sukzessive akkumuliert. In einer Schleife wird jede Runde ein Wert hinzugefügt, beispielsweise durch Addition oder Multiplikation.

**Beispiel**: Summe aller natürlicher Zahlen

<html><bottom-editor>
def summe_aller_zahlen(n):
    # Berechnet die Summe aller natürlicher Zahlen von 1..n
    resultat = 0  # Akkumulator, zu Beginn auf Null
    
    # Klassische Schleife mit Zähler-Variable
    zahl = 1
    while zahl <= n:
        resultat = resultat + zahl
        zahl = zahl + 1
    return resultat

print(summe_aller_zahlen(10))
</bottom-editor></html>
==== Aufgaben B ====

=== Aufgabe B1: Iterative 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:|
<html><bottom-editor>
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 = int(input("a"))
b = int(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)))
</bottom-editor></html>
++++
</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:|
<html><bottom-editor>
def quersumme(x):
    summe = 0
    while x > 0:
        ziffer = x % 10
        summe = summe + ziffer
        x = x // 10
    return summe

print(quersumme(413))
</bottom-editor></html>
++++
</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 1>
++++Lösung:|
<html><bottom-editor>
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
    t = 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
</bottom-editor></html>
++++
</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 1>
++++Lösung:|
Mit den Funktionen `is_prime` und `is_divisor` von oben ([[https://wtp.ethz.ch/#?code=NobwRAdghgtgpmAXGGUCWEB0AHAnmAGjABMoAXKJMNGbAewCcyACVMgCwB0Jnvi4AZszQBnAPrE0AN1GMAFJJn8IxAs0WyGASkTdm-3mE5GwAcTQAjFgBUGAVzjMAXnYYAfgMYBrNQHc4EDwaIozMcBjMAOZQEE5OUOwANmiRcAzM1uGJacxSdEHSaMrEwiJkaiEQZcwAYlCJInCYxi1GPAYMcGSuBUoBJQCk6oUh6QC8Y8wADHp8gqVi2Aw0cHIQOnoGrcbmVhn2ji7u3moC9Q3MPOEQjgAKyzDxSaXlzJXVdQ1N220GwkI8AA8zAATLp2n99J1ugweJ9Gpt9CxJiDEcwAMTMACiImYnTQHnYrwsomcrmYAHVXE44IlcvlLmTmGQ4GUAswALRRAAnFkcrLCGHZkQYADeRI1OjxMmhsukWCF1FAJWjMWQAFQAD2YE0ualIgVYbglLOY2q82SF6UaEXquKpDBpiTWWmYdhUzF8aHS7G5ZBZPG1fPxZFxqQE7uUzQhnvYsscLEBkzY7EwIgAjkwXeDIQY0EJRBIRvIIGoyBsY7n9JiKd7mOwoHyrkLpVkcuHI-yOQA-Zhea53B5PRJqPn9ALRquQ6E9Wp2uBov7I5nMADUzAAjKrmABpAet-PpDsqLu9r0-xvsgfMe40YcAQjRM9h-wcaLmALgmrIiweq3WOZbCYOyWCwkiOBA3KEmUIripKg53gkdKwRKOR2oyRyeF4zTAb8Bg3N-OqMuuW4xr4cbZJcdAsIWSwrGsX7loBuYEcurFrpuT5dLOrGzCeQh0fAYhnB4ZCMCI2bvrhuxgWgCEwBydReGJUr0jwPC2nYAhsik47pDUdCJKkZLHNhPxoiJKlESC1bMAI3rVIJC4xp0qAYPw4yXNuAAihT8IyFi4My7COBgHidMqGCRMwTmXHYMDBri7pkLKnqOBFhKbpOBjkfGeJwG5J7pL2G7MZCmIGekcBQJlTn6n5CYhflhUecwyrMIk-TRe1HCOLFoiLgYmJQMMMijNlua5ZRhbBPIrnoEVpw1SpFZTn883uTkkwbUVzAAPR2ctjCDbmdEQGQciWYwWgneVzC4HJiQlFdDB8VOmI7a1HgxFRHVdTkfKjUUcAlIFh2iaEPbMgwQVehwwUQYxMV_hNkIvURrG_vRL03Tw3BOcJR0MBJGAXRg2B2BdWjU2AAC-AC6QA&layout=%5B%22Editor%22%2C%22Console%22%5D|hier in WTP]]):
<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 1>
++++Lösung:|
<html><bottom-editor>
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))
</bottom-editor></html>
++++
</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 1>
++++Lösung:|
<html><bottom-editor>
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))
</bottom-editor></html>
++++
</nodisp>