Hauptinhalt
Kurs: Informatik > Lerneinheit 1
Lektion 6: Rekursive Algorithmen- Rekursion
- Die Fakultät
- Challenge: Iterative Fakultät
- Rekursive Fakultät
- Challenge: Rekursive Fakultät
- Eigenschaften von rekursiven Algorithmen
- Verwende Rekursion zum bestimmen ob ein Wort ein Palindrom ist
- Challenge: Ist ein String ein Palindrome?
- Die Potenzen einer Zahl berechnen
- Challenge: Rekursive Potenzen
- Mehrere Rekursionen mit dem Sierpinski-Dreieck
- Die Effizienz von rekursiven Funktionen verbessern
- Projekt: Rekursive Kunst
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Die Fakultät
Für unser erstes Rekursionbeispiel, betrachten wir die Berechnung der Fakultätsfunktion. Wir geben die Fakultät von mit an. Das ist das das Produkt der natürlichen Zahlen von 1 bis . Zum Beispiel ist 5! gleich gleich 120 . (Anmerkung: Wo immer wir über die Fakultätsfunktion sprechen, beziehen sich alle Ausrufezeichen auf die Fakultätsfunktion und sind nicht auf die Betonung.)
Du fragst, dich vielleicht warum wir so einen großen Wirbel um die Fakultätsfunktion machen. Sie ist sehr nützlich für, wenn wir bestimmen möchten wie viele verschiedene Möglichkeiten es gibt Dinge zu kombinieren. Zum Beispiel, auf wie viele Arten können wir Dinge arrangieren? Wir haben Entscheidungen für die erste Sache. Für jede dieser Entscheidungen haben wir Entscheidungen für die zweite Sache, so dass wir Entscheidungen für die ersten beiden Dinge haben. Nun, für jede dieser ersten beiden Entscheidungen, haben wir Entscheidungen für die dritte Sache, was Entscheidungen für die ersten drei Dinge ergibt. Und so weiter, bis nur noch eine Sache übrig bliebt. Insgesamt haben wir verschiedene Kombinationsmöglichkeiten von Dingen. Und das Produkt ist einfach (gesprochen Fakultät), aber mit dem Produkt geschrieben von bis zu 1 anstatt von 1 bis zu .
Eine weitere Verwendung der Fakultätsfunktion besteht darin, zu bestimmen, wie viele Möglichkeiten es gibt Dinge aus einer Sammlung von Dingen auszuwählen. Zum Beispiel, nehmen Sie an, du gehst auf eine Reise und du willst T-Shirts du mitnehmen. Nehmen wir an, dass du T-Shirts besitzt, aber du hast nur für davon Platz im Koffern. Wie viele verschiedene Möglichkeiten gibt es, T-Shirts aus einer Menge von T-Shirts auszuwählen? Die Antwort (die wir hier nicht tiefer begründen werden) entpuppt sich als . So kann die Fakultätsfunktion ziemlich nützlich sein. Du kannst mehr über Permutationen und Kombinatorik lernen, aber du musst sie nicht verstehen, um einen Fakutäts-Algorithmus zu implementieren.
Die Fakultätsfunktion ist für alle natürlichen Zahlen definiert, einschließlich der 0 . Welchen Wert sollte 0! haben? Es ist das Produkt aller ganzen Zahlen größer oder gleich 1 und kleiner oder gleich 0 . Aber es gibt keine solchen ganzen Zahlen. Deshalb definieren wir 0! als 1 . (0! = 1 zu definieren passt auch gut zu der Formel für die Auswahl von Sachen aus Sachen Angenommen, wir wollen wissen, wie viele Möglichkeiten es gibt Dinge aus Dingen zu wählen. Das ist einfach, weil es nur einen Weg gibt: Wähle alle Dinge. Also jetzt wissen wir dass, mit unserer Formel, gleich 1 ist. Aber is 0!. Damit wissen wir, dass gleich 1 sein muß. Wenn wir die sowohl im Zähler als auch im Nenner kürzen, sehen wir, dass gleich 1 sein sollte, und das ist so, weil 0! gleich 1 ist.)
So jetzt können wir uns unter etwas vorstellen. Es ist gleich 1 wenn , und es ist wenn positiv ist.
Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.