Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
gf_informatik:algorithmen_ii [2023-12-08 09:46] – [Auftrag zu Primzahlen] hofgf_informatik:algorithmen_ii [2025-12-11 09:14] (aktuell) – hof
Zeile 2: Zeile 2:
  
 =====  Struktogramme und Python ===== =====  Struktogramme und Python =====
 +<html><script type="module" src="https://bottom.ch/ksr/ed/bottom-editor.js"></script></html>
  
 ==== Aufgaben A ==== ==== Aufgaben A ====
Zeile 11: Zeile 12:
 === Aufgabe A1: Maximum === === Aufgabe A1: Maximum ===
  
-   * Teil 1: Zwei Zahlen sollen eingegeben und die grössere der beiden Zahlen ausgegeben werden. +   * 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 _zurückgibt_. Die _Ausgabe_ (`print`) soll ausserhalb der Funktion erfolgen. +   * 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 3: Schreibe eine Funktion `max3(a, b, c)`, die das Maximum von **drei** Zahlen zurückgibt. _Verwende dazu die `max2` Funktion!_
  
 <nodisp 1> <nodisp 1>
 ++++Lösung| ++++Lösung|
-<code python>+<html><bottom-editor>
 def max2(a, b): def max2(a, b):
     if a > b:     if a > b:
Zeile 27: Zeile 28:
     return max2(max2(a, b), c)     return max2(max2(a, b), c)
  
-print(max(input('a'), input('b'), input('c'))) +print(max3(int(input('a')), int(input('b')), int(input('c')))) 
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 35: Zeile 36:
    * Teil 1: Drei Zahlen sollen eingegeben werden und danach in absteigender Reihenfolge der Grösse ausgegeben werden.    * Teil 1: Drei Zahlen sollen eingegeben werden und danach in absteigender Reihenfolge der Grösse ausgegeben werden.
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung:| ++++Lösung:|
-<code python>+<html><bottom-editor>
 def sort(a, b, c): def sort(a, b, c):
     if a > b:     if a > b:
Zeile 55: Zeile 56:
  
 sort(input(), input(), input()) sort(input(), input(), input())
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
  
 <nodisp 2> <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.+++++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> </nodisp>
  
Zeile 89: Zeile 92:
 ===== Mathematische Algorithmen ===== ===== 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.
  
-==== Primzahlen ==== +**Beispiel**: Summe aller natürlicher Zahlen
-=== Theorie ===+
  
-   * Was ist eine Primzahl? +<html><bottom-editor> 
-     * Wenn nötig: Nachlesen auf [[wpde>Primzahl]] (erster Satz)! +def summe_aller_zahlen(n): 
-   * Primzahl-Test: +    # Berechnet die Summe aller natürlicher Zahlen von 1..n 
-     * Eine Funktion, die herausfindet (_zurückgibt_), ob eine Zahl prim ist. +    resultat = 0  # Akkumulator, zu Beginn auf Null 
-     * Wieviele Parameter hat die Funktion `is_prime`? +     
-   * Teiler-Test: +    # Klassische Schleife mit Zähler-Variable 
-     * Eine Funktion, die herausfindet (_zurückgibt_), ob eine Zahl `t` ein Teiler ist der Zahl `n`. +    zahl = 1 
-     * Wieviele Parameter hat die Funktion `is_divisor`? +    while zahl <= n: 
- +        resultat = resultat + zahl 
-=== Auftrag zu Primzahlen === +        zahl = zahl + 1 
- +    return resultat
-   * in 2er-Gruppen auf Papier (kein Python!) +
-   * Vorgehen: +
-     * Algorithmus ü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:| +
-<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 i <= math.sqrt(n): +
-        if is_divisor(n, i): +
-            # Wir haben einen Teiler gefunden -> keine Primzahl, beenden. +
-            return False +
-        i = i + 1 +
-    # Keinen Teiler gefunden -> wir haben eine Primzahl! +
-    return True +
-</code> +
-++++ +
-</nodisp>+
  
 +print(summe_aller_zahlen(10))
 +</bottom-editor></html>
 ==== Aufgaben B ==== ==== Aufgaben B ====
  
-=== Aufgabe B1: Einfache (math.) Algorithmen ===+=== Aufgabe B1: Iterative Algorithmen ===
  
 Schreibe für jede Aufgabe eine Funktion, die passende Argumente entgegennimmt und das Resultat zurück gibt. Schreibe für jede Aufgabe eine Funktion, die passende Argumente entgegennimmt und das Resultat zurück gibt.
Zeile 165: Zeile 121:
    - Ganzzahldivision mit Rest mit Addition und Subtraktion    - Ganzzahldivision mit Rest mit Addition und Subtraktion
    - Entscheiden ob eine beliebige Zahl eine Zweierpotenz ist oder nicht    - 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> <nodisp 1>
 ++++Lösung:| ++++Lösung:|
-<code python>+<html><bottom-editor>
 def multiply(a, b): def multiply(a, b):
     """Multipliziert zwei natürliche Zahlen ohne Verwendung der Python-Multiplikation."""     """Multipliziert zwei natürliche Zahlen ohne Verwendung der Python-Multiplikation."""
Zeile 204: Zeile 167:
     return test == n     return test == n
    
-a = input("a") +a = int(input("a")) 
-b = input("b")+b = int(input("b"))
 print(str(a) + " * " + str(b) + " = " + str(multiply(a, b))) print(str(a) + " * " + str(b) + " = " + str(multiply(a, b)))
 print(str(a) + " ^ " + str(b) + " = " + str(exponentiate(a, b))) print(str(a) + " ^ " + str(b) + " = " + str(exponentiate(a, b)))
Zeile 214: Zeile 177:
 print(str(a) + " ist eine Zweierpotenz: " + str(is_power_of_2(a))) print(str(a) + " ist eine Zweierpotenz: " + str(is_power_of_2(a)))
 print(str(b) + " ist eine Zweierpotenz: " + str(is_power_of_2(b))) print(str(b) + " ist eine Zweierpotenz: " + str(is_power_of_2(b)))
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 229: Zeile 192:
 ++++ ++++
  
-<nodisp 1>+<nodisp 2>
 ++++Lösung:| ++++Lösung:|
-<code python>+<html><bottom-editor>
 def quersumme(x): def quersumme(x):
     summe = 0     summe = 0
Zeile 241: Zeile 204:
  
 print(quersumme(413)) print(quersumme(413))
-</code>+</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> </nodisp>
  
-==== Anspruchsvolle Algorithmen ==== 
  
 === Aufgabe B3: Primfaktorzerlegung === === Aufgabe B3: Primfaktorzerlegung ===
Zeile 254: Zeile 281:
    * Schreibe eine Funktion `prime_factors(x)`, die eine Zahl x entgegennimmt und deren (geordnete) Primfaktoren von x ausgibt.    * Schreibe eine Funktion `prime_factors(x)`, die eine Zahl x entgegennimmt und deren (geordnete) Primfaktoren von x ausgibt.
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung:| ++++Lösung:|
-Mit den Funktionen `is_prime` und `is_divisor` von oben:+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> <code python>
 def next_prime(n): def next_prime(n):
Zeile 275: Zeile 302:
         while is_divisor(remainder, factor):         while is_divisor(remainder, factor):
             remainder = remainder / factor             remainder = remainder / factor
-            print factor+            print(factor)
             # yield factor             # yield factor
                  
Zeile 281: Zeile 308:
         factor = next_prime(factor)         factor = next_prime(factor)
  
-prime_factors(input())+prime_factors(int(input()))
 </code> </code>
 ++++ ++++
 </nodisp> </nodisp>
 +
 +==== Weitere anspruchsvolle Algorithmen ====
  
 === Aufgabe B4: ggT bestimmen === === Aufgabe B4: ggT bestimmen ===
Zeile 291: Zeile 320:
    * Schreibe eine Funktion `ggT(x,y)`, die zwei Zahlen `x` und `y` entgegennimmt und den ggT der beiden zurückgibt.    * Schreibe eine Funktion `ggT(x,y)`, die zwei Zahlen `x` und `y` entgegennimmt und den ggT der beiden zurückgibt.
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung:| ++++Lösung:|
-<code python>+<html><bottom-editor>
 def ggt(a, b): def ggt(a, b):
     """Berechnet den grössten gemeinsamen Teiler von a und b."""     """Berechnet den grössten gemeinsamen Teiler von a und b."""
Zeile 303: Zeile 332:
  
 print(ggt(544, 391)) print(ggt(544, 391))
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
Zeile 315: Zeile 344:
 <nodisp 1> <nodisp 1>
 ++++Lösung:| ++++Lösung:|
-<code python>+<html><bottom-editor>
 def wurzel(n, precision=0.0001): def wurzel(n, precision=0.0001):
     """Quadratwurzel nach Heron."""     """Quadratwurzel nach Heron."""
Zeile 330: Zeile 359:
    
 print(wurzel(225)) print(wurzel(225))
-</code>+</bottom-editor></html>
 ++++ ++++
 </nodisp> </nodisp>
  
  
  • gf_informatik/algorithmen_ii.1702028789.txt.gz
  • Zuletzt geändert: 2023-12-08 09:46
  • von hof