Algorithmen II

• Folgende Aufgaben hast du ev. bereits mit 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.

• 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!

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

• 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.

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.

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.

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

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))

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.

1. Multiplikation durch Additionen ausdrücken
2. Hoch-Rechnen durch Multiplikation ausdrücken
3. Hoch-Rechnen durch Additionen ausdrücken
4. Ganzzahldivision mit Rest mit Addition und Subtraktion
5. Entscheiden ob eine beliebige Zahl eine Zweierpotenz ist oder nicht

Hinweise:

Die 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!

• Was ist eine Primzahl?
  • Wenn nötig: Nachlesen auf 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?

• 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

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

• 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.

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()))

• siehe Euklidischer Algorithmus
• Schreibe eine Funktion ggT(x,y), die zwei Zahlen x und y entgegennimmt und den ggT der beiden zurückgibt.

• siehe Heron-Verfahren
• Schreibe eine Funktion wurzel(x), die die Wurzel von x auf 0.0001 genau berechnet.