Στις προκλήσεις που κάνουμε εδώ κριτής είναι μόνο ο εαυτός μας. Προσπαθώ να βάζω ενδιαφέροντα προβλήματα, που να είναι βατά από κόσμο που δεν έχει εμπειρία στον προγραμματισμό, αλλά που θα τα βρουν ενδιαφέροντα ακόμα και όσοι έχουν δεκαετή εμπειρία. Είτε ξέρεις είτε δεν ξέρεις προγραμματισμό λοιπόν, είτε θέλεις να μάθεις μια καινούργια γλώσσα , είτε θέλεις να ξεσκουρίασεις κάτι υπάρχει για σένα. Ακόμα και αν δεν ξέρεις προγραμματισμό, μπορείς να λύσεις κάποια με καθαρή λογική και λίγα μαθηματικά.
Στη σημερινή πρόκληση θέλουμε να υπολογίσουμε τον n όρο της ακολουθίας του Φιμπονάτσι . Η ακολουθία είναι οι αριθμοί
Θα την βρούμε παντού όπου στην φύση και πίσω απο την χρυσή τομή. Παρουσιάζω το πρόβλημα σε επίπεδα. Συνιστώ να γράψεις πρώτα κώδικα πριν αποκαλύψεις το επόμενο επίπεδο. Δεν μας ζορίζει κανένας χρονικός περιορισμός.
Επίπεδο δυσκολίας 1: Η παραγωγική μέθοδος
Είναι ο τρόπος που θα την υπολόγιζες με το χέρι ξεκινάς με 1,\;1 και παράγεις τον επόμενο αριθμό, αθροίζοντας τους δύο προηγούμενους.
Επίπεδο δυσκολίας 2: Διαίρει και βασίλευε
Αν έχουμε ένα δύσκολο πρόβλημα μια καλή τακτική είναι να καταφέρουμε να το σπάσουμε σε μικρότερα προβλήματα και να λύσουμε τα ποιο μικρά. Ιδανικά συνεχίζουμε αυτή την στρατηγική μέχρι να φτάσουμε σε ένα εύκολο πρόβλημα που ξέρουμε την λύση του.
Μαθηματικά μπορούμε να πούμε πως
και βλέπουμε πως εύκολα αυτή η στρατηγική εφαρμόζετε με μια συνάρτηση που καλεί τον εαυτό της. Μια τέτοια συνάρτηση την λέμε αναδρομική. Στους υπολογισμούς εδώ πάμε ανάποδα απο τον τελευταίο αριθμό προς τα κάτω.
Προσωπικά βρίσκω τον αναδρομικό τρόπο σκέψης καλύτερο και ποιο φυσικό στο να συλλογιστω την φύση ενός προβλήματος και να το λύσω. Εσείς;
.
Επίπεδο δυσκολίας 3: Υπολογισμοί και μνήμη
Αν έφτασες μέχρι εδώ μπράβο. Αλλά ίσως είδες η ξέρεις το πρόβλημα. Κάνουμε τους ίδιους και τους ίδιους υπολογισμούς πολλές φορές. Ένας τρόπος να το λύσουμε είναι να κρατάμε κάπου στην μνήμη τους παλιούς υπολογισμούς. Μια τεχνική που την λέμε memoization.
Φτιάξε ένα αντικείμενο με όνομα fibonacci_cache που να κρατάει τους προηγούμενους υπολογισμούς. Θα πρέπει να υποστηρίζει δυο βασικές πράξεις. Την προσθήκη ενός νέου υπολογισμού και την ανάκτηση ενος παλιού.
Επίπεδο δυσκολίας 5: Που πήγε το 4;
Όποιος ξέρει για την αναδρομή συνήθως ξέρει πως θέλει πολύ μνήμη, και δεν μπορείς να λύσεις μεγάλα προβλήματα. Οπότε η λύση του επιπέδου 1 αν μπορεί να βρεθεί θα είναι πάντα καλύτερη από μια αναδρομική. Αυτό έχει όμως και να κάνει και με την γλώσσα προγραμματισμού. Κάποιες γλώσσες σε κάποιες περιπτώσεις θα μετατρέψουν την αναδρομή σε παραγωγική μέθοδο σε κάποιες περιπτώσεις. Υπάρχουν και γλώσσες που δεν έχουν καν βρόχους μόνο αναδρομή!!
Αλλά ας αφήσουμε τα θεωρητικά για την ώρα. Όχι μόνο η αναδρομή χρησιμοποιεί περισσότερη μνήμη, αλλά με με το memoization χρησιμοποιήσαμε πολύ περισσότερη. Για να υπολογίσουμε το F_{1000} θα πρέπει να κρατάμε κοντά 1000 προηγούμενους υπολογισμούς. Τα χρειαζόμαστε όλα αυτά ή μπορούμε με λιγότερη μνήμη; Μια ανάλυση τως υπολογισμών λέει πως μπορούμε με λιγότερους. Δεν ξέρω πόσους, αλλά στην αρχή έπρεπε να κρατάμε μόνο 2 αριθμούς πίσω. Χωρίς καμία αλλαγή στην διασύνδεση δοκίμασε να μειώσεις την μνήμη που χρησιμοποιεί η fibonacci_cache στο ελάχιστο δυνατό.
Πόσο μακρυά κατάφερες να φτάσεις;