Die Fakultät

Für unser erstes Rekursionbeispiel, betrachten wir die Berechnung der Fakultätsfunktion. Wir geben die Fakultät von $n$n mit $n!$n, ! an. Das ist das das Produkt der natürlichen Zahlen von 1 bis $n$n. Zum Beispiel ist 5! gleich $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5$1, dot, 2, dot, 3, dot, 4, dot, 5 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 $n$n Dinge arrangieren? Wir haben $n$n Entscheidungen für die erste Sache. Für jede dieser $n$n Entscheidungen haben wir $n-1$n, minus, 1 Entscheidungen für die zweite Sache, so dass wir $n \cdot (n-1)$n, dot, left parenthesis, n, minus, 1, right parenthesis Entscheidungen für die ersten beiden Dinge haben. Nun, für jede dieser ersten beiden Entscheidungen, haben wir $n-2$n, minus, 2 Entscheidungen für die dritte Sache, was $n \cdot (n-1) \cdot (n-2)$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis Entscheidungen für die ersten drei Dinge ergibt. Und so weiter, bis nur noch eine Sache übrig bliebt. Insgesamt haben wir $n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis, \@cdots, 2, dot, 1 verschiedene Kombinationsmöglichkeiten von $n$n Dingen. Und das Produkt ist einfach $n!$n, ! (gesprochen $n$n Fakultät), aber mit dem Produkt geschrieben von $n$n bis zu 1 anstatt von 1 bis zu $​​n$​, ​, n.

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 $n$n T-Shirts besitzt, aber du hast nur für $k$k davon Platz im Koffern. Wie viele verschiedene Möglichkeiten gibt es, $k$k T-Shirts aus einer Menge von $n$n T-Shirts auszuwählen? Die Antwort (die wir hier nicht tiefer begründen werden) entpuppt sich als $n! / (k! \cdot (n-k)!)$n, !, slash, left parenthesis, k, !, dot, left parenthesis, n, minus, k, right parenthesis, !, right parenthesis. 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 $k$k Sachen aus $n$n Sachen Angenommen, wir wollen wissen, wie viele Möglichkeiten es gibt $n$n Dinge aus $n$n Dingen zu wählen. Das ist einfach, weil es nur einen Weg gibt: Wähle alle $n$n Dinge. Also jetzt wissen wir dass, mit unserer Formel, $n! / (n! \cdot (n-n)!)$n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis gleich 1 ist. Aber $( n-n)!$left parenthesis, n, minus, n, right parenthesis, ! is 0!. Damit wissen wir, dass $n! / (n! \cdot 0!)$n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis gleich 1 sein muß. Wenn wir die $n!$n, ! sowohl im Zähler als auch im Nenner kürzen, sehen wir, dass $1/(0!)$1, slash, left parenthesis, 0, !, right parenthesis gleich 1 sein sollte, und das ist so, weil 0! gleich 1 ist.)

So jetzt können wir uns unter $n !$n, ! etwas vorstellen. Es ist gleich 1 wenn $n = 0$n, equals, 0, und es ist $1 \cdot 2 \cdots (n-1) \cdot n$1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, n wenn $n$n 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.