Προβλήματα Μαθηματικών

Οκτώβριος 19, 2012

Υπολογίστε γρήγορα τους αριθμούς Fibonacci

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 11:39 μμ

Αν θέλουμε να υπολογίσουμε γρήγορα τη δύναμη K^n ενός φυσικού αριθμού K (όπου ο εκθέτης n είναι ένας πολύ μεγάλος αριθμός) τότε δε χρειάζεται να κάνουμε n πολλαπλασιασμούς. Αρκούν O(\log n) αριθμητικές πράξεις (πάντα μεταξύ ακεραίων): η πιο απλή περίπτωση όπου αυτό φαίνεται είναι όταν n=2^r είναι δύναμη του 2. Τετραγωνίζοντας κάθε φορά το προηγούμενό μας αποτέλεσμα μπορούμε με r=O(\log n) πράξεις να πάρουμε το αποτέλεσμά μας.

Βρείτε ένα αντίστοιχα γρήγορο τρόπο υπολογισμού του n-οστού αριθμού Fibonacci F_n. Οι αριθμοί Fibonacci ορίζονται από τον αναδρομικό τύπο:

F_n = \begin{cases} 1 & (n=1,2)\\ F_{n-1}+F_{n-2} & (n\ge 3).\end{cases}

Μόνο πράξεις ανάμεσα σε ακεραίους είναι επιτρεπτές.

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

Advertisements

9 Σχόλια »

  1. Υπόδειξη: Υπολογίστε τα F_n με ένα τύπο της μορφής
    g_n = M^n g_0,
    όπου το «αντικείμενο» g_n περιέχει μέσα του το F_n και όπου το «αντικείμενο» M δεν εξαρτάται από το n.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 30, 2012 @ 1:22 πμ

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

    Για τους πρώτους όρους της ακολουθίας Fibonacci έχουμε: F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8

    Τώρα, προκειμένου να λυθεί το θέμα, αρκεί να αποδειχτεί πως ισχύει:

    F_{2k+1} = F_k^2 + F_{k+1}^2

    και

    F_{2k} = F_{k}(F_{k-1} + F_{k+1})

    Επιβεβαιώνουμε πως αυτές οι σχέσεις ισχύουν για k = 2, με επαγωγή και κάνοντας τις πράξεις χρησιμοποιώντας τις εξισώσεις F_{n} = F_{n-1} + F_{n-2} αποδεικνύεται πως ισχύει γενικά. Ξαναγράφοντας την πρώτη από τις 2 εξισώσεις αντικαθιστώντας το k με k-1 παίρνουμε τις τρεις εξισώσεις:

    F_{2k+1} = F_k^2 + F_{k+1}^2
    F_{2k} = F_{k}(F_{k-1} + F_{k+1})
    F_{2k-1} = F_k^2 + F_{k-1}^2

    Παρατηρούμε πως οι τρεις συνεχόμενοι όροι F_{2k+1}, F_{2k}, F_{2k-1} δίνονται ως συνάρτηση μόνο των συνεχόμενων όρων F_{k+1}, F_{k}, F_{k-1}, άρα οι υπόλοιποι όροι της ακολουθίας Fibonacci μπορούν να παραλειφθούν.

    Έτσι, αν ξεκινήσουμε από τους όρους F_1, F_2, F_3, με τις προηγούμενες εξισώσεις διαδοχικά θα υπολογίζουμε τους όρους:

    Βήμα 1: F_1, F_2, F_3
    Βήμα 2: F_3, F_4, F_5
    Βήμα 3: F_7, F_8, F_9
    Βήμα 4: F_{15}, F_{16}, F_{17}
    Βήμα 5: F_{31}, F_{32}, F_{33}
    Βήμα 6: F_{63}, F_{64}, F_{65}
    κλπ.

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

    Μου αρέσει!

    Σχόλιο από fotisgiagkoylas — Νοέμβριος 26, 2012 @ 10:25 μμ

  3. Καλή κατεύθυνση αλλά δεν έχω πειστεί ακόμη.

    Ναι, τα βήματα που περιγράφεις παραπάνω μας δίνουν κάποιους μεγάλους αριθμούς Fibonacci F_n σε χρόνο O(\log n), αλλά μας δίνει το τυχόν F_n σε τόσο χρόνο; Γι’ αυτό θα πρέπει να δοθεί ένας αλγόριθμος που να βρίσκει το F_n για κάθε n.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Νοέμβριος 27, 2012 @ 12:38 πμ

  4. Σωστό. Πρώτα-πρώτα μια διόρθωση. Εφόσον προσπαθούμε να βελτιστοποιήσουμε τον χρόνο, δεν χρειάζεται να υπολογίζουμε και τα τρία F_{2x+1}, F_{2x}, F_{2x-1} με τους τύπους που έδωσα, καθώς το F_{2x+1} προκύπτει μόνο με μια πρόσθεση από τα 2 προηγούμενα.

    Τώρα, ψυλλιασμένος απ’ το νόημα του προηγούμενου σχολίου βρήκα τους τύπους:

    F_{k+n-1} = F_k F_n + F_{k-1} F_{n-1}
    F_{k+n} = F_{k+1} F_n + F_k F_{n-1}

    Xρησιμοποιούντας αυτούς, αφού υπολογίσουμε όλες τις «τριάδες» μέχρι το F_t (όπου t = [log_2n]), αποσυνθέτουμε τον n σε άθροισμα δυνάμεων του 2 και υπολογίζουμε σε O(logn) πολυπλοκότητα τον F_n.

    Μου αρέσει!

    Σχόλιο από fotisgiagkoylas — Νοέμβριος 27, 2012 @ 3:29 πμ

  5. Ωραία. (Νομίζω ότι ένα μόνο από τους δύο τύπους χρειάζεσαι.)

    Γενικεύεται;

    Μήπως μπορείτε να βρείτε ένα τρόπο υπολογισμού σε O(\log n) χρόνο μιας αναδρομικής ακολουθίας a_n που ικανοποιεί μια τυχαία αναδρομική σχέση

    a_n = c_1 a_{n-1}+\cdots+c_r a_{n-r}

    όπου r σταθερά και επίσης c_1,\ldots,c_r επίσης σταθερές;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Νοέμβριος 27, 2012 @ 12:28 μμ

  6. Θα μπορούσαμε (?) να βάζαμε τον αλγόριθμο να λύνει αριθμητικά την παραπάνω εξίσωση διαφορών, βρίσκοντας τον γενικό τύπο, ο οποίος περιέχει μόνο ν-οστές δυνάμεις σταθερών καθώς και προσθέσεις και πολλαπλασιασμούς αυτών με σταθερές. Μετά από αυτό είναι Ο(logn) πολυπλοκότητα. Είναι βέβαια κάπως μπακάλικη η λύση καθώς ενδεχομένως να απαιτείται μεγάλη ακρίβεια στις σταθερές για μεγάλα n.

    Μου αρέσει!

    Σχόλιο από fivosk7 — Φεβρουαρίου 7, 2013 @ 7:13 μμ

  7. Η αριθμητική (numerical) προσέγγιση δε νομίζω ότι μπορεί να δουλέψει. Κατ’αρχήν θα πρέπει να βρεις τις ρίζες ενός πολυωνύμου με μεγάλη ακρίβεια (δύσκολο) κι όταν τις βρείς κάποιες από αυτές θα είναι πιο μεγάλες κι άλλες μικρές κι αυτό είναι συνήθως συνταγή για αριθμητικά προβλήματα. Επίσης η μέθοδος αυτή δε δουλεύει παρά μόνο στους πραγματικούς/μιγαδικούς ενώ το αρχικό πρόβλημα λύνεται κι αν ακόμη τα στοιχεία της ακολουθίας είναι στοιχεία ενός δακτυλίου, π.χ. οι αριθμοί mod m.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Φεβρουαρίου 7, 2013 @ 8:32 μμ

  8. Μια πιο σύντομη λύση χρησιμοποιώντας την αρχική υπόδειξη. Ισχύει:
    F_{n+1} = F_n + F_{n-1}
    F_n = F_n
    Με μορφή πίνακα το παραπάνω γράφεται:
    \left(\begin{array}{cc}F_{n+1}\\ F_n\end{array}\right)=\left(\begin{array}{cc}1 & 1\\1 & 0\end{array}\right)\left(\begin{array}{cc}F_n \\ F_{n-1}\end{array}\right)
    Προκύπτει συνεπώς εύκολα ότι:
    \left(\begin{array}{cc}F_{n+1}\\ F_n\end{array}\right)=\left(\begin{array}{cc}1 & 1\\1 & 0\end{array}\right)^n\left(\begin{array}{cc}1 \\ 0\end{array}\right)
    Οπότε το πρόβλημα ανάγεται σε γρήγορο υπολογισμό των δυνάμεων του πίνακα \left(\begin{array}{cc}1 & 1\\1 & 0\end{array}\right) και η διαδικασία από εδώ και πέρα είναι παρόμοια με αυτήν για τον υπολογισμό δυνάμεων φυσικού αριθμού.

    Μου αρέσει!

    Σχόλιο από xatzial1 — Οκτώβριος 7, 2013 @ 1:44 πμ

  9. Πολύ σωστά. Και ο γρήγορος υπολογισμός των δυνάμεων ενός πίνακα γίνεται, όπως και για τις δυνάμεις αριθμών, με διαδοχικούς τετραγωνισμούς (έτσι σε n βήματα υπολογίζει κανείς τη δύναμη M^{2^n} του πίνακα n, και δεν είναι δύσκολο να δει κανείς ότι όταν ο εκθέτης δεν είναι δύναμη του 2 τότε μπορεί να τον γράψει στο δυαδικό του ανάπτυγμα και να χρησιμοποιήσει το προηγούμενο τρικ).

    Επίσης αυτή η μέθοδος είναι τελείως γενική, δουλεύει δηλ. για οποιαδήποτε γραμμική αναδρομική σχέση, όπου δηλ. ο n-οστός όρος μιας ακολουθίας δίνεται ως ένας σταθερός (δεν εξαρτάται από το n) γραμμικός συνδυασμός κάποιων (πεπερασμένων το πλήθος) προηγούμενων όρων.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 7, 2013 @ 7:19 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: