Επιλογή Σελίδας

Για καλύτερη κατανόηση της διαφοράς μεταξύ επαναληπτικών και αναδρομικών μεθόδων, στη συνέχεια θα εξετασθεί ένα τελευταίο παράδειγμα, όπου υπολογίζεται η ακολουθία αριθμών Fibonacci πρώτης τάξης, που ορίζεται ως εξής:

par383kef3vmath

ενώ οι πρώτοι όροι της ακολουθίας Fibonacci πρώτης τάξης είναι: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 κ.λπ.

ΛΥΣΗ:

Από τον ορισμό φαίνεται ανάγλυφα η αναδρομική φύση της συνάρτησης. Οι δύο επόμενοι αλγόριθμοι υπολογίζουν τον αριθμό Fibonacci πρώτης τάξης Fn με επαναληπτική και αναδρομική μέθοδο. Υποτίθεται ότι κατά την κλήση του αλγορίθμου μία μη αρνητική τιμή περνά ως όρισμα στη μεταβλητή n.

Αλγόριθμος Fibonacci1
 Δεδομένα // n //
 Αν n ≤ 1 τότε Fib ← n
 f0 ← 0
 f1 ← 1
 Για i από 2 μέχρι n
     fib ← f0+f1
     f0 ← f1
     f1 ← fib
 Τέλος_επανάληψης
 Αποτελέσματα // Fib //
 Τέλος Fibonacci1
  
 Αλγόριθμος Fibonacci2
 Δεδομένα // n //
 Αν n ≤ 1 τότε 
    Fib ← n
 αλλιώς
    Fib ← Fibonacci2(n-1) + Fibonacci2(n-2)
 Τέλος_Αν
 Αποτελέσματα // Fib //
 Τέλος Fibonacci2
Share This