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 [2024-10-21 11:42] – [Aufgabe A1: Maximum] hofgf_informatik:algorithmen_ii [2024-12-16 11:19] (aktuell) – [Auftrag zu Primzahlen] hof
Zeile 27: Zeile 27:
     return max2(max2(a, b), c)     return max2(max2(a, b), c)
  
-print(max3(input('a'), input('b'), input('c')))+print(max3(int(input('a')), int(input('b')), int(input('c'))))
 </code> </code>
 ++++ ++++
Zeile 35: Zeile 35:
    * 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> <code python>
Zeile 89: Zeile 89:
 ===== Mathematische Algorithmen ===== ===== Mathematische Algorithmen =====
  
- 
-==== Primzahlen ==== 
-=== Theorie === 
- 
-   * Was ist eine Primzahl? 
-     * Wenn nötig: Nachlesen auf [[wpde>Primzahl]] (erster Satz)! 
-   * Primzahl-Test: 
-     * Eine Funktion, die herausfindet (_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 ü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> 
  
 ==== Aufgaben B ==== ==== Aufgaben B ====
Zeile 165: Zeile 101:
    - 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>
Zeile 245: Zeile 188:
 </nodisp> </nodisp>
  
-==== Anspruchsvolle Algorithmen ====+==== 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 === === Aufgabe B3: Primfaktorzerlegung ===
Zeile 275: Zeile 282:
         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 288:
         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 313: Zeile 322:
    * Schreibe eine Funktion `wurzel(x)`, die die Wurzel von `x` auf `0.0001` genau berechnet.    * Schreibe eine Funktion `wurzel(x)`, die die Wurzel von `x` auf `0.0001` genau berechnet.
  
-<nodisp 1>+<nodisp 2>
 ++++Lösung:| ++++Lösung:|
 <code python> <code python>
  • gf_informatik/algorithmen_ii.1729510953.txt.gz
  • Zuletzt geändert: 2024-10-21 11:42
  • von hof