Arbeitsblatt · Studium
Rekursionen, Siebformel und Mastertheorem: Aufgaben mit Lösungen
Der Generator stellt Aufgaben zu Rekursionen und Zählproblemen: Glieder berechnen, charakteristische Gleichung, geschlossene Formel, Siebformel, fixpunktfreie Permutationen, Münzprobleme, Mastertheorem und Türme von Hanoi. Mit Lösungen.
Kostenlos für Unterricht und Lernen (Bedingungen). Im Unterricht ohne Werbung: Unterrichtsansicht · Sie unterrichten?
Erklärung: Rekursionen und erzeugende Funktionen: Zählen, Lösen, WachstumHier rechnest du mit Rekursionen und zählst mit der Siebformel. Wähle oben eine Aufgabenart oder lass sie gemischt. Mit „Neue Aufgaben“ entsteht ein neues Blatt.
Das brauchst du
- Charakteristische Gleichung: Zu an = c1 an−1 + c2 an−2 gehört λ² = c1 λ + c2. Bei zwei verschiedenen Nullstellen ist an = α λ1n + β λ2n, α und β folgen aus a0 und a1.
- Siebformel: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Die Vielfachen von p bis N sind ⌊N/p⌋, die gemeinsamen Vielfachen von p und q sind ⌊N/(pq)⌋.
- Fixpunktfreie Permutationen: Dn = n! Σ (−1)k/k!, also 1, 0, 1, 2, 9, 44, 265, 1.854 für n = 0, …, 7. Es gilt Dn = (n−1)(Dn−1 + Dn−2). Genau k Fixpunkte haben (n über k) · Dn−k Permutationen, mindestens einen Fixpunkt n! − Dn.
- Münzen: Der Koeffizient von xn in 1/((1−x)(1−x2)…) zählt die Möglichkeiten. Rechne die Faktoren nacheinander: Mit jeder neuen Münze m gilt w(n) = w(n) + w(n−m).
- Mastertheorem: Bei T(n) = a T(n/b) + nd vergleichst du d mit logb a. Ist d größer, überwiegt nd, ist es kleiner, überwiegt nlogb a. Sind beide gleich, tragen alle Ebenen gleich viel bei und es kommt ein Faktor log n dazu: T(n) = Θ(nd · log n). Das gilt für a ≥ 1 und b > 1.
Alles steht auf der Seite Rekursionen und erzeugende Funktionen bei den linearen Rekursionen, den erzeugenden Funktionen, der Inklusion und Exklusion und der O-Notation.
Arbeitsblatt von geschichtedermathematik.de/rekursionen-aufgaben/ · kostenlos für Unterricht und Lernen
Fehler entdeckt oder einen Wunsch? Schreib uns eine kurze Nachricht, wir kümmern uns darum.
