Το παραγοντικό ενός αριθμού είναι μια σημαντική μαθηματική έννοια. Μπορείτε να το χρησιμοποιήσετε για να εκτελέσετε μεταθέσεις και συνδυασμούς, να γράψετε εκθετικές και λογαριθμικές εκφράσεις και να υπολογίσετε την πιθανότητα.
Το χρησιμοποιείτε για να βρείτε τον αριθμό των διαφορετικών τρόπων με τους οποίους μπορείτε να σχεδιάσετε μια διάταξη καθισμάτων ή να επιλέξετε μπλουζάκια για τις διακοπές σας στις Μαλδίβες. Πώς όμως μπορείς να υπολογίσεις το παραγοντικό ενός αριθμού;
Τι είναι το παραγοντικό ενός αριθμού;
Το παραγοντικό ενός θετικού αριθμού είναι το γινόμενο όλων των θετικών ακεραίων μικρότερων ή ίσων με την τιμή του ίδιου του αριθμού. Ένας αριθμός ακολουθούμενος από ένα θαυμαστικό(!) δηλώνει το παραγοντικό ενός αριθμού. Αντιπροσωπεύετε το παραγοντικό του πέντε ως 5! και υπολογίστε το ως:
5! = 5 * 4 * 3 * 2 * 1 = 120
Ένας άλλος τρόπος για να το οπτικοποιήσετε είναι:
5! = 5 * 4! που 4! = 4 * 3!, 3! = 3 * 2! και ούτω καθεξής μέχρι να πάρετε 1! = 1 * 0! που είναι 1.
Θα χρησιμοποιήσετε αυτήν την έννοια για να δημιουργήσετε το παραγοντικό μας πρόγραμμα χρησιμοποιώντας μια δημοφιλή έννοια που ονομάζεται αναδρομή.
Τι είναι η αναδρομή;
Η αναδρομή είναι μια διαδικασία κατά την οποία μια συνάρτηση καλεί τον εαυτό της. Ένα από τα κύρια πλεονεκτήματα αυτής της διαδικασίας είναι ότι χωρίζει ένα μεγαλύτερο πρόβλημα σε μικρότερα κομμάτια. Αυτό διευκολύνει την επίλυση του προβλήματος.
Μπορείτε να χρησιμοποιήσετε την αναδρομή για να λύσετε κατάλληλα προβλήματα σε τρία απλά βήματα:
- Βρείτε τη βασική θήκη: Εάν μια συνάρτηση καλεί πάντα τον εαυτό της, η διαδικασία θα είναι άπειρη. Για να μην συμβεί αυτό, ορίστε μια βασική περίπτωση που γίνεται το λογικό σημείο διακοπής για τη λειτουργία σας. Για παράδειγμα, σε ένα παραγοντικό πρόγραμμα, σταματήστε τον υπολογισμό στο μηδέν. Αυτό γίνεται η βασική περίπτωση του προβλήματος.
- Βρείτε τη σχέση μεταξύ του προβλήματος και των υποπροβλημάτων: Αναλύστε το μεγαλύτερο πρόβλημα σε υποπρόβλημα. Για παράδειγμα, το πρόβλημα είναι να βρεθεί το παραγοντικό του πέντε. Ας υποθέσουμε ότι έχετε την απάντηση του παραγοντικού των τεσσάρων, δηλαδή 24. Πώς θα πάρετε το παραγοντικό του πέντε χρησιμοποιώντας το 24; Πολλαπλασιάζοντας το πέντε σε αυτό. Αυτή είναι η σχέση μεταξύ του προβλήματος και του υποπροβλήματος.
- Γενικεύστε τη σχέση που βρέθηκε στο Βήμα 2: Τώρα που έχετε τη σχέση, γενικεύστε την ως n. Άρα, το παραγοντικό ενός αριθμού n είναι το γινόμενο του n και το παραγοντικό του n-1.
Μπορείτε να χρησιμοποιήσετε αυτήν την έννοια για να βρείτε το άθροισμα n φυσικών αριθμών, υπολογίστε το GCD, το LCM, τη σειρά Fibonacci και ελέγξτε τους πρώτους αριθμούς.
Ψευδοκώδικας για την παραγοντική συνάρτηση με χρήση αναδρομής
Αυτό είναι πώς χρησιμοποιείτε την αναδρομή και γράψτε τον ψευδοκώδικα για να δημιουργήσετε το πρόγραμμά σας σε οποιαδήποτε γλώσσα. Με διαφορετικές γλώσσες, η σύνταξη και η εκτέλεση αλλάζουν, αλλά η λογική παραμένει άθικτη.
λειτουργίαΓεγονός(n)
Αν n == 0 έπειτα // βασικό σενάριο
ΕΠΙΣΤΡΟΦΗ1
ΕΠΙΣΤΡΟΦΗ n * Γεγονός κλήσης (n - 1) // γενικευμένη σχέση
Πρόγραμμα Factorial στο Γ
Η C ήταν η πρώτη γλώσσα προγραμματισμού υψηλού επιπέδου, ανεξάρτητη από πλατφόρμα. Έχει αυστηρή σύνταξη, έχει διάκριση πεζών-κεφαλαίων και εκτελεί κώδικα με τη μεγαλύτερη ταχύτητα. Είναι μια διαδικαστική γλώσσα προγραμματισμού και ως εκ τούτου δηλώνετε οποιαδήποτε συνάρτηση πάνω από το κύριος λειτουργία. Δείτε πώς μπορείτε να δημιουργήσετε το παραγοντικό πρόγραμμα χρησιμοποιώντας αναδρομή στη γλώσσα C:
Μπορείτε να βρείτε ολόκληρο τον πηγαίο κώδικα του παραγοντικού προγράμματος χρησιμοποιώντας αναδρομή σε C, Java και Python σε αυτό Αποθετήριο GitHub.
- Εισαγάγετε το τυπικό αρχείο κεφαλίδας εξόδου εισόδου για την εμφάνιση της εξόδου στην οθόνη.
#περιλαμβάνω <stdio.h> - Ορισμός συνάρτησης γεγονός και πάρτε ακέραιο αριθμό n ως επιχείρημα.
ενθγεγονός(ενθ ιδ){ - Γράψτε τη βασική περίπτωση της συνάρτησης χρησιμοποιώντας το αν δήλωση και ελέγξτε την ισότητά της χρησιμοποιώντας ==. Αν το n ισούται με μηδέν, επιστρέψτε ένα.
αν (n == 0)
ΕΠΙΣΤΡΟΦΗ1; - Γράψτε τη γενικευμένη εξίσωση και επιστρέψτε το γινόμενο του n με μια κλήση συνάρτησης υποπροβλήματος n-1.
ΕΠΙΣΤΡΟΦΗ n * γεγονός (n - 1);
} - Δηλώστε την κύρια συνάρτηση και αρχικοποιήστε μια μεταβλητή ακέραιου τύπου για να αποθηκεύσετε τον αριθμό του οποίου το παραγοντικό θέλετε να βρείτε.
ενθκύριος(){
ενθ αριθμός = 5; - Εμφανίστε το παραγοντικό του αριθμού χρησιμοποιώντας το printf() λειτουργία. %ρε είναι ο προσδιοριστής δεκαδικής μορφής. Χρησιμοποιήστε κάθε έναν από τους προσδιοριστές μορφής για να τον αντικαταστήσετε με τον αριθμό του οποίου το παραγοντικό θέλετε να βρείτε και να λάβετε το αποτέλεσμα καλώντας τη συνάρτηση.
printf("Το παραγοντικό του %d είναι %d", αριθμός, γεγονός (αριθμός));
ΕΠΙΣΤΡΟΦΗ0;
}
Factorial πρόγραμμα σε Java
Η Java είναι μια μεταγλωττισμένη γλώσσα προγραμματισμού και είναι ανεξάρτητη από πλατφόρμα. Αποθηκεύετε όλο τον κώδικα μέσα στο α τάξη και η εκτέλεση αρχίζει από το κύριος λειτουργία. Έχει διάκριση πεζών-κεφαλαίων και αυστηρή σύνταξη. Ο κώδικας είναι λίγο μεγαλύτερος αλλά πιο γρήγορος σε σύγκριση με την Python. Δείτε πώς μπορείτε να δημιουργήσετε το παραγοντικό πρόγραμμα χρησιμοποιώντας αναδρομή στην Java:
- Ορίστε την κύρια τάξη.
τάξηΚύριος{ - Ορίστε μια στατική συνάρτηση με τύπο επιστροφής int που δέχεται μια μεταβλητή n ακέραιου τύπου. Δηλώσατε μια στατική μέθοδο καθώς η κύρια μέθοδος στην Java δηλώνεται επίσης ως στατική. Επιπλέον, δεν μπορείτε να καλέσετε μια μη στατική μέθοδο από μια στατική παρουσία.
στατικόςενθγεγονός(ενθ ιδ){ - Γράψτε τη βασική περίπτωση της συνάρτησης χρησιμοποιώντας το αν δήλωση και ελέγξτε την ισότητά της χρησιμοποιώντας ==. Αν το n ισούται με μηδέν, επιστρέψτε ένα.
αν (n == 0)
ΕΠΙΣΤΡΟΦΗ1; - Γράψτε τη γενικευμένη εξίσωση και επιστρέψτε το γινόμενο του n με μια κλήση συνάρτησης υποπροβλήματος n-1.
ΕΠΙΣΤΡΟΦΗ n * γεγονός (n - 1);
} - Δηλώστε την κύρια συνάρτηση στην Java. Δηλώστε τον τροποποιητή πρόσβασης ως δημόσιο, ώστε να είναι προσβάσιμο από όλες τις άλλες κλάσεις και μεθόδους. Δηλώνετε την κύρια λειτουργία ως στατικός έτσι ώστε ο μεταγλωττιστής να μπορεί να το καλέσει χωρίς να δημιουργήσει την κλάση. Ο τύπος επιστροφής είναι κενός, και δέχεται ορίσματα τύπου Σειρά. Αποθηκεύστε τον αριθμό του οποίου το παραγοντικό θέλετε να βρείτε.
δημόσιοστατικόςκενόςκύριος(String[] args){
ενθ αριθμός = 5; - Χρησιμοποιήστε το println() μέθοδος, ένα παράδειγμα του PrintStream κλάση, που ορίζεται στο Σύστημα κλάση για να εμφανίσετε το παραγοντικό του αριθμού.
System.out.println("Παραγοντική του " + αριθμός + " είναι " + γεγονός (αριθμός));
}
}
Factorial πρόγραμμα σε Python
Η σύνταξη κώδικα σε Python είναι εξαιρετικά εύκολη και διασκεδαστική. Καθώς είναι μια ερμηνευμένη γλώσσα ανεξάρτητη από την πλατφόρμα, δεν χρειάζεται να δηλώσετε τον τύπο δεδομένων των μεταβλητών. Αποφεύγετε επίσης να χρειάζεται να δηλώσετε κλάσεις και να εισάγετε βιβλιοθήκες για ένα τόσο απλό πρόγραμμα. Η παιδική χαρά είναι έτοιμη για να ξεκινήσετε την κωδικοποίηση.
Η σύνταξη είναι πιο εύκολη, με μικρό μήκος κώδικα, αλλά χρειάζεται λίγο περισσότερο χρόνο για να εκτελεστεί από τις άλλες γλώσσες. Δείτε πώς μπορείτε να δημιουργήσετε το παραγοντικό πρόγραμμα χρησιμοποιώντας αναδρομή στην Python:
- Ορίστε το γεγονός της συνάρτησης που δέχεται ως όρισμα n.
defγεγονός(n): - Γράψτε τη βασική περίπτωση της συνάρτησης χρησιμοποιώντας το αν δήλωση και ελέγξτε την ισότητά της χρησιμοποιώντας ==. Αν το n ισούται με μηδέν, επιστρέψτε ένα.
αν n == 0:
ΕΠΙΣΤΡΟΦΗ1 - Γράψτε τη γενικευμένη εξίσωση και επιστρέψτε το γινόμενο του n με μια κλήση συνάρτησης υποπροβλήματος n-1.
ΕΠΙΣΤΡΟΦΗ n * γεγονός (n-1) - Αποθηκεύστε τον αριθμό του οποίου το παραγοντικό θέλετε να βρείτε και εμφανίστε τον χρησιμοποιώντας τη δήλωση εκτύπωσης.
αριθμός = 5;
Τυπώνω("Παραγοντική του", αρ. "είναι", γεγονός (αριθμός))
Υπάρχουν πολλές εφαρμογές της αναδρομής
Η αναδρομή είναι ένας αποτελεσματικός τρόπος επίλυσης προβλημάτων. Είναι η ουσία της Τεχνητής Νοημοσύνης και έχει πραγματικές χρήσεις σε παιχνίδια παζλ όπως το σκάκι ή το Sudoku.
Είναι επίσης μια ισχυρή μέθοδος για την ταξινόμηση δομών δεδομένων όπως το δέντρο ή τους αλγόριθμους ταξινόμησης όπως η Γρήγορη ταξινόμηση και η ταξινόμηση συγχώνευσης. Μπορείτε επίσης να χρησιμοποιήσετε την αναδρομή σε αλγόριθμους αναζήτησης όπως η δυαδική αναζήτηση, μαθηματικές εκφράσεις όπως η σειρά Fibonacci και άλλα.