Προγραμματιστική πρόκληση Νο 7: Ακολουθία Φιμπονάτσι

Στις προκλήσεις που κάνουμε εδώ κριτής είναι μόνο ο εαυτός μας. Προσπαθώ να βάζω ενδιαφέροντα προβλήματα, που να είναι βατά από κόσμο που δεν έχει εμπειρία στον προγραμματισμό, αλλά που θα τα βρουν ενδιαφέροντα ακόμα και όσοι έχουν δεκαετή εμπειρία. Είτε ξέρεις είτε δεν ξέρεις προγραμματισμό λοιπόν, είτε θέλεις να μάθεις μια καινούργια γλώσσα , είτε θέλεις να ξεσκουρίασεις κάτι υπάρχει για σένα. Ακόμα και αν δεν ξέρεις προγραμματισμό, μπορείς να λύσεις κάποια με καθαρή λογική και λίγα μαθηματικά.

image

Στη σημερινή πρόκληση θέλουμε να υπολογίσουμε τον n όρο της ακολουθίας του Φιμπονάτσι . Η ακολουθία είναι οι αριθμοί

1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;

Θα την βρούμε παντού όπου στην φύση και πίσω απο την χρυσή τομή. Παρουσιάζω το πρόβλημα σε επίπεδα. Συνιστώ να γράψεις πρώτα κώδικα πριν αποκαλύψεις το επόμενο επίπεδο. Δεν μας ζορίζει κανένας χρονικός περιορισμός.

Επίπεδο δυσκολίας 1: Η παραγωγική μέθοδος

Είναι ο τρόπος που θα την υπολόγιζες με το χέρι ξεκινάς με 1,\;1 και παράγεις τον επόμενο αριθμό, αθροίζοντας τους δύο προηγούμενους.

Επίπεδο δυσκολίας 2: Διαίρει και βασίλευε

Αν έχουμε ένα δύσκολο πρόβλημα μια καλή τακτική είναι να καταφέρουμε να το σπάσουμε σε μικρότερα προβλήματα και να λύσουμε τα ποιο μικρά. Ιδανικά συνεχίζουμε αυτή την στρατηγική μέχρι να φτάσουμε σε ένα εύκολο πρόβλημα που ξέρουμε την λύση του.

Μαθηματικά μπορούμε να πούμε πως

F_n = \begin{cases} 1, &\text{εαν}\: n=1\:ή \ 2 \\ F_{n-1} + F_{n-2} & αλλιώς \end{cases}


και βλέπουμε πως εύκολα αυτή η στρατηγική εφαρμόζετε με μια συνάρτηση που καλεί τον εαυτό της. Μια τέτοια συνάρτηση την λέμε αναδρομική. Στους υπολογισμούς εδώ πάμε ανάποδα απο τον τελευταίο αριθμό προς τα κάτω.
Προσωπικά βρίσκω τον αναδρομικό τρόπο σκέψης καλύτερο και ποιο φυσικό στο να συλλογιστω την φύση ενός προβλήματος και να το λύσω. Εσείς;
.

Επίπεδο δυσκολίας 3: Υπολογισμοί και μνήμη

Αν έφτασες μέχρι εδώ μπράβο. Αλλά ίσως είδες η ξέρεις το πρόβλημα. Κάνουμε τους ίδιους και τους ίδιους υπολογισμούς πολλές φορές. Ένας τρόπος να το λύσουμε είναι να κρατάμε κάπου στην μνήμη τους παλιούς υπολογισμούς. Μια τεχνική που την λέμε memoization.
Φτιάξε ένα αντικείμενο με όνομα fibonacci_cache που να κρατάει τους προηγούμενους υπολογισμούς. Θα πρέπει να υποστηρίζει δυο βασικές πράξεις. Την προσθήκη ενός νέου υπολογισμού και την ανάκτηση ενος παλιού.

Επίπεδο δυσκολίας 5: Που πήγε το 4;

Όποιος ξέρει για την αναδρομή συνήθως ξέρει πως θέλει πολύ μνήμη, και δεν μπορείς να λύσεις μεγάλα προβλήματα. Οπότε η λύση του επιπέδου 1 αν μπορεί να βρεθεί θα είναι πάντα καλύτερη από μια αναδρομική. Αυτό έχει όμως και να κάνει και με την γλώσσα προγραμματισμού. Κάποιες γλώσσες σε κάποιες περιπτώσεις θα μετατρέψουν την αναδρομή σε παραγωγική μέθοδο σε κάποιες περιπτώσεις. Υπάρχουν και γλώσσες που δεν έχουν καν βρόχους μόνο αναδρομή!!

Αλλά ας αφήσουμε τα θεωρητικά για την ώρα. Όχι μόνο η αναδρομή χρησιμοποιεί περισσότερη μνήμη, αλλά με με το memoization χρησιμοποιήσαμε πολύ περισσότερη. Για να υπολογίσουμε το F_{1000} θα πρέπει να κρατάμε κοντά 1000 προηγούμενους υπολογισμούς. Τα χρειαζόμαστε όλα αυτά ή μπορούμε με λιγότερη μνήμη; Μια ανάλυση τως υπολογισμών λέει πως μπορούμε με λιγότερους. Δεν ξέρω πόσους, αλλά στην αρχή έπρεπε να κρατάμε μόνο 2 αριθμούς πίσω. Χωρίς καμία αλλαγή στην διασύνδεση δοκίμασε να μειώσεις την μνήμη που χρησιμοποιεί η fibonacci_cache στο ελάχιστο δυνατό.

Πόσο μακρυά κατάφερες να φτάσεις;

2 Likes

Την Φιμπονάτσι την βρίσκω ιδανική για να δούμε την yield τής python

def fib():
    x_old = 0
    x = 1
    while True:
        yield x
        x, x_old = x + x_old, x
3 Likes

Σε γλώσσα C […]
είναι λάθος το πρόγραμμα :frowning:

Το διόρθωσα! έβαλα και long int.

#include <stdio.h>
#include <stdlib.h>

typedef struct {int n1; int n2; long int x1; long int x2;} savedfibs;

long int knownfib(int n, savedfibs *f)
{
    if (f->n1 == n) return f->x1;
    if (f->n2 == n) return f->x2;
    return -1;
}

long int fib(int n, savedfibs *f)
{
    long int x;
    if ((x = knownfib(n, f)) != -1) return x;
    if (n == 0) x = 0;
    if (n == 1) x = 1;
    if (n > 1) x = fib(n-1, f) + fib(n-2, f);
    if (f->n1 < f->n2) { 
        f->x1 = x;
        f->n1 = n;
    } else {
        f->x2 = x;
        f->n2 = n;
    }
    return x;
}
     
int main(int argc, char *argv[])
{
    savedfibs f;
    f.n1=-1;
    f.n2=-1;
    int n=atoi(argv[1]);
    printf("%li\n", fib(n, &f));
}
1 Like

Η δική μου ταπεινή προσπάθεια:

a,b = 0,1

while True:
    print(b, end=' ')
    a,b = b,a+b 
    
print(b)

την yield δεν την γνωρίζω καθόλου, αλλά θα την ψάξω…

1 Like

έχω βάλει μια σχετική πρόκληση, και τελικά ακόμα δεν έχω αναρτήσει τις καλύτερες απαντήσεις.

α, ok thanks… αποκλείεται να το βρω αλλά θα προσπαθήσω…

Έχει εδώ και αρκετό καιρό που έχω αναπτύξει μία θεωρητική προσέγγιση στο πρόβλημα, αλλά δεν έχω προλάβει να την εφαρμόσω. Επειδή όμως καίγομαι να μάθω αν είναι σωστή θα την παραθέσω σε ένα σπόιλερ και όποιος θέλει μπορεί να την δει.

Η προσέγγιση μου, αλλά πίσω από σπόιλερ να μην χαλάσω την άσκηση χωρίς να έχω υποβάλλει κάποιον αλγόριθμο

Λοιπόν το επίπεδο 3 είναι απλό. Χρησιμοποιούμε τη λογική του memoization για να αποθηκεύσεις κάθε αποτέλεσμα που έχει υπολογίσει, ώστε μετά με βάση το αντίστοιχο N να το βρίσκεις κατευθείαν.

Για το επίπεδο 5, φαντάζομαι μία λύση που αποτελεί παραλλαγή του επιπέδου 3, εφόσον γίνεται χρήση του fibonacci_cache , ωστόσο αυτή τη φορά αντί για το πλήρες δεν θα αποθηκεύονται όλα τα αποτελέσματα που έχουμε υπολογίσει, αλλά θα αποθηκεύονται κάποια από αυτά ( φαντάζομαι σε ζεύγη fib(n),fib(n-1) ή ως πράξη fib(n) = fib(n-1) + fib(n-2) ). Παράδειγμα θα αποθηκεύουμε κάθε δέκατο ή εκατοστό ή χιλιοστό αποτέλεσμα ή ζεύγος. Οπότε όταν θα θέλουμε να βρούμε ένα Ν-οστό fibonacci θα βρίσκουμε το κοντινότερο προηγούμενο αριθμό που έχουμε αποθηκεύσει και θα χτίζουμε το αποτέλεσμα που θέλουμε με αναδρομή, αλλά διανύοντας μία αρκετά μικρότερη απόσταση. Αντί να κάνουμε 1000 υπολογισμούς στο παράδειγμα του fib(1000), θα ξεκινάμε από το fib(900) ,που έχουμε αποθηκεύσει, κάνοντας μόνο 100 υπολογισμούς.

Ουσιαστικά είναι μία επιλογή ανάμεσα στην αντιστρόφως ανάλογη σχέση του χρόνου επεξεργασίας και χρήσης μνήμης. Μειώνουμε τα αποτελέσματα που αποθηκεύουμε, ωστόσο αυξάνεται ο χρόνος επεξεργασίας για να βρεθεί το αποτέλεσμα που θέλουμε. Το συγκεκριμένο παράδειγμα λοιπόν μας διδάσκει πως στη ζωή και στον προγραμματισμό δεν υπάρχει η μαγική λύση που τα φτιάχνει όλα πάντα, αλλά αντιθέτως κάποιες φορές ανάλογα με την περίπτωση χρήσης που θέλουμε, πρέπει να κάνουμε κάποιους συμβιβασμούς, που ταιριάζουν στην περίπτωση μας.

Αν η προσέγγιση μου είναι λάθος ή υπάρχει κάποιο “μαγικό” κόλπο που δεν γνωρίζω παρακαλώ θα ήθελα να μου το πείτε γιατί το συγκεκριμένο πρόβλημα το σκέφτομαι κοντά μισό μήνα τώρα. με στοιχειώνει τα βράδια!

EDIT: Διόρθωση μερικών λαθών και βελτίωση της εμφάνισης

Το πρόβλημα είναι βαθύ, αν και η λύση του μπορεί να βρεθεί αν καθίσεις να σκεφτείς σαν ένας compiler. Και η λύση είναι ότι θέλεις πάλι δυο θέσεις μνήμης. Αν ασχοληθείς σοβαρά με το τι είναι υπολογιστής και υπολογισμός θα πέσεις πάνω στην αναδρομή και στους υπολογιστές με στοίβα. Στα βιβλία συνήθως δείχνουν πως ένας απλός αναδρομικός αλγόριθμος όπως ο υπολογισμός του παραγοντικού μπορεί να μεταφραστεί σε ένα βρόχο for και υπό ποιες προϋποθέσεις. Η τεχνικές αυτές μόλις πρόσφατα κατάφεραν οι compilers να τις ενσώματώσουν. Δεν έχω βρει σε κανένα βιβλίο να αναλύουν την Fibonacci. Βρήκα μόνο σε ένα σχετικά άσχετο βιβλίο μια αναφορά.

Αλλά υπάρχουν και κάποιες άλλες γλώσσες προγραμματισμού που δεν έχουν καν μια εντολή FOR και το κάνουν με αυτόν τον τρόπο. Η δεύτερη γλώσσα προγραμματισμού που φτιάχτηκε LISP ποτέ ανήκει σε αυτή την κατηγορία. Ποιο πίσω ακόμα πάμε σε ένα μαθηματικό που έφτιαξε κάποια μαθηματικά, πρίν του υπολογιστές, και που μεταφέρονται αυτούσια σαν πρόγραμμα. Σήμερα αυτή η προσέγγιση έχει αρχίσει να γίνετε δημοφιλής.

Πολλά μπορούν να λεχθούν λοιπόν και σίγουρα θέλουν πάνω από μισό μήνα να τα λογιστεί κανείς. Αλλά αν κάνεις ένα δέντρο των υπολογισμών θα τα καταφέρεις να το λύσεις. Ο lucinos έδωσε μια λύση.

Αν θέλεις να ασχοληθείς περισσότερα, υπάρχουν κάποιες παλιές διαλέξεις του 1986 (από κάποια ιδρυτικά μέλη του FSF και οι μόνοι από τους ιδρυτές που είναι ακόμα ενεργοί). Από το πρώτο εξάμηνο του MIT σε μια γλώσσα προγραμματισμού που έχει λιγότερες από 10 εντολές. Θα καταλάβεις αρκετά αν δεις τις πρώτες 3 διαλέξεις. Ακολούθησε αυτόν το σύνδεσμο https://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

1 Like

Σε Fortran :

PROGRAM fibo
IMPLICIT NONE
INTEGER :: n
PRINT*,"Dwse poses fores na tre3ei i akolouthia : "
READ*,n
CALL fibonacci(n)
END PROGRAM fibo

SUBROUTINE fibonacci(n)
IMPLICIT NONE
INTEGER :: n,i,x1,x2,x
i=2
x1=0
x2=1
IF (n<0)THEN
	PRINT*,"Edwses akyri timi!"
ELSE IF (n==0)THEN
	PRINT*,"F",n," = ",x1
ELSE IF (n==1)THEN
	PRINT*,"F",n," = ",x2
ELSE IF (n>1)THEN
	DO WHILE (i<=n)
		x=x1+x2
		x1=x2
		x2=x
		PRINT*,"F",i," = ",x
		i=i+1
	END DO
END IF
END SUBROUTINE
2 Likes