Each new term in the Fibonacci sequence is generated by adding the previous
two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed
four million, find the sum of the even-valued terms.
Να βρεθεί το άθροισμα των ζυγών όρων της ακολουθίας Fibonacci που δεν υπερβαίνουν τα 4.000.000
O υπολογισμός της ακολουθίας Fibonacci είναι ένα από τα κλασσικά παραδείγματα εφαρμογής της αναδρομής (recursion).
def fib_rec(n):
if n < 2:
return n
else:
return fib_rec(n-1) + fib_rec(n-2)Το πρόβλημα με την αναδρομή είναι ότι είναι εξαιρετικά αργή για μεγάλους όρους της ακολουθίας.
H αναδρομική διαδικασία μπορεί να βελτιωθεί αν χρησιμοποιηθεί ένα dictionary στο οποίο αποθηκεύονται οι προηγούμενοι όροι της ακολουθίας, ώστε να μη χρειάζεται να επαναϋπολογίζονται.
memo = {0:0, 1:1}
def fib(n):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
Μια διαφορετική προσέγγιση είναι οι όροι της ακολουθίας να μην υπολογιστούν αναδρομικά αλλά επαναληπτικά (iteratively) μέσω ενός loop. O κώδικας είναι πολύ απλός, και αρκετά αποδοτικός για μικρά N, αλλά για μεγάλα N δεν είναι και ότι καλύτερο.
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
Μια τρίτη προσέγγιση είναι να χρησιμοποιηθούν generators. Ο τρόπος αυτός είναι με διαφορά ο πιο αποδοτικός από τους προηγούμενους. Οι τιμές που προκύπτουν από το generator είναι εύκολο να αποθηκευτούν σε μια λίστα ή σε ένα dictionary.
def fib():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
Η τάξη μεγέθους της διαφοράς στην απόδοση φαίνεται εδώ
recursive_dictionary => 0.0708091259003
iterator => 0.138380050659
generator_list => 0.0373520851135
Ολοκληρωμένη η λύση, μαζί με τον κώδικα τεκμηρίωσης και σύγκρισης μπορεί να βρεθεί
ΕΔΩ
Εκτός από τα παραπάνω, υπάρχουν και αποδοτικότεροι τρόποι για τον απευθείας υπολογισμό όρων της ακολουθίας fibonacci αλλά είναι αρκετά
μπλεγμένα τα μαθηματικά τους.
