Ασκηση στην Δομη Επαναληψης

Ξεκίνησε από SifisZap, 11 Οκτ 2013, 12:32:03 ΠΜ

« προηγούμενο - επόμενο »

SifisZap

Καλησπέρα

Παρακάτω δίνω μια ασκηση που με εχει δυσκολέψει αρκετά

Ασκηση
__________________________________________________________________________________________________________

Οι αριθμοί Fibonacci ορίζονται ως εξής : F0 = 0, F1 = 1 και Fk = Fk - 1 + Fk - 2. Κάθε αριθμός είναι ίσος με το άθροισμα
των δυο προηγούμενων του. Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ το οποίο για ένα δεδομένο θετικό αριθμό Ν που
διαβάζεται,να υπολογίζει τον Ν-οστό όρο της ακολουθίας. Άν ο αριθμός που διαβάστηκε ειναι αρνητικός, θα εμφανίζει μήνυμα λάθους.
__________________________________________________________________________________________________________

Αυτή ειναι η άσκηση..καθε συμβουλή, γνώμη ή βοήθεια ειναι ευπρόσδεκτη.

Ευχαριστώ πολύ για τον χρόνο σας.

petrosp13

Σκέψου ότι θα έχεις 2 μεταβλητές που θα ξεκινήσουν με τις τιμές 1 και 2 (2ος και 3ος όρος) και μια βοηθητική
Σκέψου ότι στην βοηθητική θα βάζεις πάντα το άθροισμα των 2
Σκέψου ότι μετά θα βάζεις την τιμή της δεύτερης στην πρώτη και την τιμή της βοηθητικής στην δεύτερη
Και τέλος σκέψου πόσες φορές θα θέλεις να γίνεται αυτό
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

dpa2006

#2
Το πρόγραμμα σου, καλό θα είναι να ξεκινά διαβάζοντας το πλήθος της ακολουθίας Fibonacci(αν και δεν είναι απαραίτητο πάντοτε),
οι δύο πρώτοι όροι Fibonacci θεωρούνται δεδομένοι,με βάση αυτά η αναδρομή θα υπολογίζει τον Fibonacci για το εκάστοτε Ν που δόθηκε.
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

pgrontas

Μόλις την κάνεις αυτή την άσκηση ίσως μπορείς να δοκίμασεις το επόμενο βήμα σε επίπεδο δυσκολίας.

Παράθεση από: evry στις 17 Δεκ 2010, 05:23:29 ΜΜ

Να γίνει αλγόριθμος ο οποίος θα διαβάζει αριθμούς και θα ελέγχει αν αποτελούν διαδοχικούς όρους της ακολουθίας Fibonacci.  Ο αλγόριθμος θα σταματάει όταν διαπιστώσει ότι η ακολουθία δεν είναι Fibonacci ή όταν δοθεί ο αριθμός -1.


Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

chzisi

Η ακολουθία Fibonacci δεν είναι κλασικό παράδειγμα αναδρομής που είναι εκτός?

sstergou

Λύνεται και επαναληπτικά οπότε δεν υπάρχει θέμα.

itt

#6
Παράθεση από: SifisZap στις 11 Οκτ 2013, 12:32:03 ΠΜ
Καλησπέρα

Παρακάτω δίνω μια ασκηση που με εχει δυσκολέψει αρκετά

Ασκηση
__________________________________________________________________________________________________________

Οι αριθμοί Fibonacci ορίζονται ως εξής : F0 = 0, F1 = 1 και Fk = Fk - 1 + Fk - 2. Κάθε αριθμός είναι ίσος με το άθροισμα
των δυο προηγούμενων του. Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ το οποίο για ένα δεδομένο θετικό αριθμό Ν που
διαβάζεται,να υπολογίζει τον Ν-οστό όρο της ακολουθίας. Άν ο αριθμός που διαβάστηκε ειναι αρνητικός, θα εμφανίζει μήνυμα λάθους.
__________________________________________________________________________________________________________

Αυτή ειναι η άσκηση..καθε συμβουλή, γνώμη ή βοήθεια ειναι ευπρόσδεκτη.

Ευχαριστώ πολύ για τον χρόνο σας.

O αριθμοί Fibonacci παράγονται από τον απλό κανόνα :

Fn =             

  •   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 επειδή υπολογίζει πολλές φορές το ίδιο πρόβλημα



Ένας πιο αποδοτικός τρόπος θα ήταν να χρησιμοποιήσουμε έξυπνη αναδρομή, διατηρώντας έναν πίνακα με τα προηγούμενα αποτελέσματα( Xρησιμοποιώντας 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)


Οπότε τώρα το δέντρο της αρχικής συνάρτησης αποσυντίθεται σε μια λίστα και θα υπολογίσει το Fn bottom-up



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]


Τώρα λοιπόν έχουμε έναν πολύ ωραίο γραμμικό αλγόριθμο για να υπολογίζουμε το Fn. Ένα κομμάτι που μπορούμε να βελτιώσουμε ακόμα είναι η μνήμη που απαιτεί η fibArray. Η ιδέα είναι ότι χρειαζόμαστε απλώς δύο προηγούμενους όρους και όχι αναγκαστικά όλη την ακολουθία. Πιστεύω ότι μπορείς να το υλοποιήσεις εύκολα και μόνος σου τώρα και θα σε βοηθούσε να το προσπαθήσεις.

Θα τελειώσω λοιπόν αναφέροντας ότι υπάρχει και μια O(log(n)) υλοποίηση για να λύσεις το πρόβλημα. Αυτό είναι εφικτό με τη χρήση πινάκων.

Έστω F ο πίνακας 

|1   1|
|1   0|

Τότε το Fn [1,2] είναι ισο με τον ν-οστο όρο της ακολουθίας. Οπότε χρειάζεσαι έναν αλγόριθμο για την ύψωση πίνακα που να έχει χρονική πολυπλοκότητα O(log(n)), κάτι που υφίσταται για έναν πίνακα σταθερού μεγέθους και υψωμένο σε ακέραια δύναμη.

                 

pgrontas

Οι μαθητές δεν κάνουν αναδρομή στην ΑΕΠΠ (ίσως θα έπρεπε αλλά αυτό είναι μια άλλη συζήτηση).
Ο επαναληπτικός αλγόριθμος είναι γραμμικός πάντως.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson