Καλησπέρα
Παρακάτω δίνω μια ασκηση που με εχει δυσκολέψει αρκετά
Ασκηση
__________________________________________________________________________________________________________
Οι αριθμοί Fibonacci ορίζονται ως εξής : F0 = 0, F1 = 1 και Fk = Fk - 1 + Fk - 2. Κάθε αριθμός είναι ίσος με το άθροισμα
των δυο προηγούμενων του. Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ το οποίο για ένα δεδομένο θετικό αριθμό Ν που
διαβάζεται,να υπολογίζει τον Ν-οστό όρο της ακολουθίας. Άν ο αριθμός που διαβάστηκε ειναι αρνητικός, θα εμφανίζει μήνυμα λάθους.
__________________________________________________________________________________________________________
Αυτή ειναι η άσκηση..καθε συμβουλή, γνώμη ή βοήθεια ειναι ευπρόσδεκτη.
Ευχαριστώ πολύ για τον χρόνο σας.
Σκέψου ότι θα έχεις 2 μεταβλητές που θα ξεκινήσουν με τις τιμές 1 και 2 (2ος και 3ος όρος) και μια βοηθητική
Σκέψου ότι στην βοηθητική θα βάζεις πάντα το άθροισμα των 2
Σκέψου ότι μετά θα βάζεις την τιμή της δεύτερης στην πρώτη και την τιμή της βοηθητικής στην δεύτερη
Και τέλος σκέψου πόσες φορές θα θέλεις να γίνεται αυτό
Το πρόγραμμα σου, καλό θα είναι να ξεκινά διαβάζοντας το πλήθος της ακολουθίας Fibonacci(αν και δεν είναι απαραίτητο πάντοτε),
οι δύο πρώτοι όροι Fibonacci θεωρούνται δεδομένοι,με βάση αυτά η αναδρομή θα υπολογίζει τον Fibonacci για το εκάστοτε Ν που δόθηκε.
Μόλις την κάνεις αυτή την άσκηση ίσως μπορείς να δοκίμασεις το επόμενο βήμα σε επίπεδο δυσκολίας.
Παράθεση από: evry στις 17 Δεκ 2010, 05:23:29 ΜΜ
Να γίνει αλγόριθμος ο οποίος θα διαβάζει αριθμούς και θα ελέγχει αν αποτελούν διαδοχικούς όρους της ακολουθίας Fibonacci. Ο αλγόριθμος θα σταματάει όταν διαπιστώσει ότι η ακολουθία δεν είναι Fibonacci ή όταν δοθεί ο αριθμός -1.
Η ακολουθία Fibonacci δεν είναι κλασικό παράδειγμα αναδρομής που είναι εκτός?
Λύνεται και επαναληπτικά οπότε δεν υπάρχει θέμα.
Παράθεση από: SifisZap στις 11 Οκτ 2013, 12:32:03 ΠΜ
Καλησπέρα
Παρακάτω δίνω μια ασκηση που με εχει δυσκολέψει αρκετά
Ασκηση
__________________________________________________________________________________________________________
Οι αριθμοί Fibonacci ορίζονται ως εξής : F0 = 0, F1 = 1 και Fk = Fk - 1 + Fk - 2. Κάθε αριθμός είναι ίσος με το άθροισμα
των δυο προηγούμενων του. Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ το οποίο για ένα δεδομένο θετικό αριθμό Ν που
διαβάζεται,να υπολογίζει τον Ν-οστό όρο της ακολουθίας. Άν ο αριθμός που διαβάστηκε ειναι αρνητικός, θα εμφανίζει μήνυμα λάθους.
__________________________________________________________________________________________________________
Αυτή ειναι η άσκηση..καθε συμβουλή, γνώμη ή βοήθεια ειναι ευπρόσδεκτη.
Ευχαριστώ πολύ για τον χρόνο σας.
O αριθμοί Fibonacci παράγονται από τον απλό κανόνα :
F
n =
- Fn-1 + Fn-2 Αν n > 1
- 1 Aν n = 1
- 0 Αν n = 0
To πρώτο πράγμα που βλέπει κανείς είναι ότι θα μπορούσε με μια αναδρομική υλοποίηση να παράγει τον αριθμό που θέλει, οπότε θα έχουμε:
function fib(n) =
if n = 0: return 0
if n = 1: return 1
return fib(n-1) + fib(n-2)
Δυστηχώς αυτή η υλοποίηση παρότι εύκολη και προφανής, είναι εκθετική στον χρόνο εκτέλεσης ως προς το n επειδή υπολογίζει πολλές φορές το ίδιο πρόβλημα
(http://i.picresize.com/images/2013/11/02/TtN1M.png)
Ένας πιο αποδοτικός τρόπος θα ήταν να χρησιμοποιήσουμε έξυπνη αναδρομή, διατηρώντας έναν πίνακα με τα προηγούμενα αποτελέσματα( Xρησιμοποιώντας memoization (https://en.wikipedia.org/wiki/Memoization)):
function fibMemo(n)
if n = 0 return 0
create a HashTable called terms and add the pairs (0 -> 0), (1 -> 1)
if n not in terms:
terms[n]= fibMemo(n-1) + fibMemo(n-2)
return terms(n)
Οπότε τώρα το δέντρο της αρχικής συνάρτησης αποσυντίθεται σε μια λίστα και θα υπολογίσει το F
n bottom-up
(http://i.stack.imgur.com/bj1cc.png)
Mπορούμε επίσης να γράψουμε και το εξής που δεν χρησιμοποιεί αναδρομή:
fibArray(n)
if n = 0: return 0
create an array f[0...n]
f[0] = 0, f[1] = 1
for i from 2 to n:
f[i] = f[i-1] + f[i-2]
return f[n]
Τώρα λοιπόν έχουμε έναν πολύ ωραίο γραμμικό αλγόριθμο για να υπολογίζουμε το F
n. Ένα κομμάτι που μπορούμε να βελτιώσουμε ακόμα είναι η μνήμη που απαιτεί η fibArray. Η ιδέα είναι ότι χρειαζόμαστε απλώς δύο προηγούμενους όρους και όχι αναγκαστικά όλη την ακολουθία. Πιστεύω ότι μπορείς να το υλοποιήσεις εύκολα και μόνος σου τώρα και θα σε βοηθούσε να το προσπαθήσεις.
Θα τελειώσω λοιπόν αναφέροντας ότι υπάρχει και μια O(log(n)) υλοποίηση για να λύσεις το πρόβλημα. Αυτό είναι εφικτό με τη χρήση πινάκων.
Έστω F ο πίνακας
|1 1|
|1 0|
Τότε το F
n [1,2] είναι ισο με τον ν-οστο όρο της ακολουθίας. Οπότε χρειάζεσαι έναν αλγόριθμο για την ύψωση πίνακα που να έχει χρονική πολυπλοκότητα O(log(n)), κάτι που υφίσταται για έναν πίνακα σταθερού μεγέθους και υψωμένο σε ακέραια δύναμη.
Οι μαθητές δεν κάνουν αναδρομή στην ΑΕΠΠ (ίσως θα έπρεπε αλλά αυτό είναι μια άλλη συζήτηση).
Ο επαναληπτικός αλγόριθμος είναι γραμμικός πάντως.