Ενότητα 1. Αλγοριθμική
Διαδραστική Εξερεύνηση της Αναδρομής Εξερευνώντας την Αναδρομή Μια διαδραστική προσέγγιση σε θεμελιώδεις έννοιες της πληροφορικής. Τι Είναι η Αναδρομή; Η αναδρομή είναι μια ισχυρή τεχνική όπου μια συνάρτηση καλεί τον εαυτό της για να λύσει ένα πρόβλημα. Φανταστείτε να φωτογραφίζετε έναν καθρέφτη: η εικόνα περιέχει τον καθρέφτη, που περιέχει την εικόνα, και ούτω καθεξής. Στην πληροφορική, χωρίζουμε ένα μεγάλο πρόβλημα σε μικρότερα, πανομοιότυπα υπο-προβλήματα μέχρι να φτάσουμε σε μια απλή, βασική περίπτωση που μπορούμε να λύσουμε άμεσα. Η αναδρομή είναι σαν ένα σετ από ρωσικές κούκλες. Κάθε κούκλα περιέχει μια μικρότερη, πανομοιότυπη κούκλα, μέχρι να φτάσεις στην τελευταία, η οποία είναι πολύ μικρή και δεν περιέχει τίποτα άλλο. Αυτό ακριβώς κάνει και ένας αναδρομικός αλγόριθμος: Παίρνει ένα μεγάλο πρόβλημα. Το σπάει σε ένα μικρότερο κομμάτι που είναι ακριβώς ίδιο με το αρχικό. Το επαναλαμβάνει αυτό ξανά και ξανά, μέχρι να φτάσει σε ένα τόσο μικρό και απλό κομμάτι που μπορεί να το λύσει αμέσως. Αυτό το μικρό κομμάτι είναι η βασική περίπτωση. Με αυτόν τον τρόπο, το πρόβλημα λύνεται βήμα-βήμα, ξεκινώντας από το πιο απλό. Το Τρίγωνο Sierpinski Το Τρίγωνο Sierpinski είναι ένα παράδειγμα ενός σχήματος που «περιέχει τον εαυτό του». Ξεκινάμε με ένα απλό τρίγωνο. Μετά, το χωρίζουμε σε τέσσερα μικρότερα τρίγωνα και αφαιρούμε το μεσαίο. Τώρα, έχουμε τρία μικρά τρίγωνα, που το καθένα μοιάζει ακριβώς με το αρχικό μεγάλο. Η διαδικασία αυτή επαναλαμβάνεται ξανά και ξανά, σε κάθε ένα από τα μικρότερα τρίγωνα. Αυτό ακριβώς είναι η αναδρομή: η επανάληψη της ίδιας διαδικασίας σε μικρότερη κλίμακα, ξανά και ξανά. Αυξάνοντας το «βάθος» στην εφαρμογή, απλά δείχνουμε πόσες φορές επαναλαμβάνεται αυτή η διαδικασία. Όσο μεγαλύτερο το βάθος, τόσο περισσότερο «βαθιά» βλέπουμε την αναδρομή. - Βάθος: 1 + Οι Πύργοι του Ανόι Ένα κλασικό παζλ που λύνεται κομψά με αναδρομή. Ο στόχος είναι να μεταφερθούν όλοι οι δίσκοι από τον στύλο Α στον Γ, χρησιμοποιώντας τον Β ως βοηθητικό, χωρίς ποτέ ένας μεγαλύτερος δίσκος να μπει πάνω από μικρότερο. Επιλέξτε αριθμό δίσκων και παρακολουθήστε την αναδρομική λύση. Δίσκοι: 3 Έναρξη Επαναφορά Η Εκρηκτική Αύξηση των Κινήσεων Η ομορφιά της αναδρομικής λύσης για τους Πύργους του Ανόι κρύβει μια εκθετική πολυπλοκότητα. Ο ελάχιστος αριθμός κινήσεων είναι $2^N - 1$, όπου Ν είναι ο αριθμός των δίσκων. Χρησιμοποιήστε τον παρακάτω slider για να δείτε πώς ο αριθμός των κινήσεων αυξάνεται δραματικά με κάθε επιπλέον δίσκο. Αριθμός Δίσκων (N): 3 Σύνολο Κινήσεων: 7 Αναδρομή στο Παραγοντικό (N!) Ο υπολογισμός του παραγοντικού ενός αριθμού είναι ένα κλασικό παράδειγμα χρήσης της αναδρομής. Το παραγοντικό του N ($N!$) είναι το γινόμενο όλων των θετικών ακεραίων μέχρι το N. Για παράδειγμα, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. Μια αναδρομική συνάρτηση το λύνει ως εξής: $N! = N \times (N-1)!$. Η βασική περίπτωση είναι το $1! = 1$. Εισάγετε αριθμό (N): Υπολογισμός Αποτέλεσμα: 120 Βήμα-βήμα Αναδρομική Κλήση: τώρα παίξε μόνο σου!!! Οι Πύργοι του Ανόι Οι Πύργοι του Ανόι Μoves: 0 Πύργος 1 Πύργος 2 Πύργος 3 Επαναφορά Κανόνες: Μετακινήστε όλους τους δίσκους από τον πρώτο στον τρίτο πύργο. Δεν μπορείτε…