Υπολογιστής Γραμμής Τριγώνου Pascal

Τύπος

How this is calculated

Το τρίγωνο Pascal είναι ο πίνακας των διωνυμικών συντελεστών, όπου κάθε καταχώριση ισούται με το άθροισμα των δύο καταχωρίσεων ακριβώς από πάνω της. Η μοναδική είσοδος n είναι ο αριθμός γραμμής με δείκτη που ξεκινά από το 0: η γραμμή 0 είναι [1], η γραμμή 1 είναι [1, 1], η γραμμή 2 είναι [1, 2, 1], και ούτω καθεξής. Ο υπολογιστής χτίζει τη γραμμή επαναληπτικά αντί να υπολογίζει κάθε παραγοντικό ξεχωριστά. Ξεκινά με C(n,0) = 1 και εφαρμόζει την αναδρομή C(n,k) = C(n,k−1) · (n−k+1) / k για k = 1 έως n. Επειδή κάθε ενδιάμεση τιμή είναι ακριβής ακέραιος, αυτή η πολλαπλασιαστική μέθοδος αποφεύγει την υπερχείλιση που θα παίρνατε από τον άμεσο υπολογισμό του n! και είναι πολύ ταχύτερη.

Η γραμμή έχει n + 1 όρους, είναι συμμετρική (C(n,k) = C(n,n−k)), και σχηματίζει μια κατανομή σχήματος καμπάνας που κορυφώνεται στη μέση. Το άθροισμα όλων των συντελεστών στη γραμμή n ισούται με 2^n, που προκύπτει από το διωνυμικό θεώρημα με x = y = 1: (1 + 1)^n = Σ C(n,k). Αυτοί οι συντελεστές είναι ακριβώς οι πολλαπλασιαστές που εμφανίζονται όταν αναπτύσσετε το (x + y)^n.

Η είσοδος πρέπει να είναι μη αρνητικός ακέραιος. Μη ακέραιες, αρνητικές ή κενές τιμές δεν παράγουν αποτέλεσμα. Για πολύ μεγάλα n οι συντελεστές υπερβαίνουν την ακρίβεια της κινητής υποδιαστολής διπλής ακρίβειας, οπότε αποτελέσματα πάνω από μερικές εκατοντάδες θα πρέπει να αντιμετωπίζονται ως προσεγγιστικά.