Für wen soll die Seite passen? Alles hier ist kostenlos.

Kostenlos für Ihren Unterricht: Arbeitsblätter, Aufgaben, Texte und Grafiken ohne Rückfrage kopieren, anpassen und an die Klasse weitergeben (Bedingungen).

Im Unterricht ohne Werbung: Unterrichtsansicht Mehr für Lehrkräfte

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, Wachstum

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

Anzeige

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.

Fehler entdeckt oder einen Wunsch?

Deine Nachricht zur Seite „Rekursionen, Zählen und Wachstum üben“. Die Adresse der Seite schicken wir automatisch mit.

Bitte schreib keine weiteren persönlichen Daten hinein. Mehr dazu im Datenschutz.