Fibonacci και Motzkin

Πρόβλημα

Η ακολουθία Fibonacci (F(n)) είναι μια διάταξη από φυσικούς αριθμούς, η οποία ορίζεται αναδρομικά ως εξής:

Στην θέση 0 είναι ο αριθμός 0. Στην θέση 1 είναι ο αριθμός 1. Σε κάθε άλλη θέση είναι το άθροισμα των αριθμών που βρίσκονται στις δύο προηγούμενες θέσεις. Ή :

F(0) = 0

F(1)= 1

F(n) = F(n – 1) + F(n – 2), n ≥  2

Οι πρώτοι 10 αριθμοί της ακολουθίας είναι: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

Γράψτε μία συνάρτηση με μία ακέραια παράμετρο (θεωρείστε κατά την κλήση της συνάρτησης ότι το όρισμα είναι πάντα φυσικός αριθμός) η οποία επιστρέφει τον αριθμό της ακολουθίας Fibonacci που βρίσκεται στην θέση την οποία υποδεικνύει η παράμετρος.

Λύση

fib

Απόδειξη ορθότητας

Για ν=0 και ν= 1 η ορθότητα είναι προφανής (F <- ν).

Θα αποδείξουμε την ορθότητα του προγράμματος με ισχυρή επαγωγή στον φυσικό αριθμό ν για ν > 1:

Σημείωση: η ισχυρή επαγωγή είναι ίδια με την απλή επαγωγή, με την διαφορά ότι στην επαγωγική υπόθεση αντί να υποθέσουμε ότι το ζητούμενο ισχύει για ν = κ β, υποθέτουμε ότι ισχύει για ν με βνκ, όπου β η βάση της επαγωγής.

Βάση επαγωγής:

Για ν= 2 η επαναληπτική δομή ΓΙΑ θα εκτελεστεί μία φορά, οπότε το αποτέλεσμα είναι προηγούμενος + προ_προηγούμενος = 0 + 1 = 1, σωστά.

Επαγωγική υπόθεση:

Υποθέτουμε ότι το πρόγραμμα είναι σωστό για 2 ν κ.

Επαγωγικό βήμα:

Θα δείξουμε ότι αν ισχύει η επαγωγική υπόθεση το πρόγραμμα είναι σωστό και για ν = κ +1:

Στην επαναληπτική δομή Για κατά την επανάληψη εκείνη όπου ν = κ+1 το αποτέλεσμα δίνεται (όπως σε κάθε επανάληψη) από το άθροισμα προηγούμενος + προ_προηγούμενος. Για ν = κ η μεταβλητή προ_προηγούμενος πήρε την τιμή της μεταβλητής προηγούμενος, ενώ αμέσως μετά η μεταβλητή προηγούμενος πήρε την τιμή νιοστός. Οπότε, αμέσως πριν την εκτέλεση της επανάληψης με ν=κ+1 η μεταβλητή προηγούμενος διατηρεί τον αριθμό Fibonacci στην θέση κ, ο οποίος είναι πράγματι ο αριθμός Fibonacci στην θέση κ με βάση την επαγωγική υπόθεση, ενώ η μεταβλητή προ_προηγούμενος διατηρεί την τιμή της μεταβλητής προηγούμενος πριν αυτή μεταβληθεί κατά την επανάληψη με ν=κ, δηλαδή… τον αριθμό Fibonacci στην θέση κ-1, ο οποίος είναι σωστός και πάλι με βάση την επαγωγική υπόθεση. Επομένως, για την θέση κ+1 το πρόγραμμα δίνει ως αποτέλεσμα το άθροισμα του αριθμού Fibonacci στην θέση κ και στην θέση κ-1. Αυτό που έπρεπε να αποδείξουμε.

Σχόλια

Η σειρά με την οποία γίνονται τα πράγματα στον προγραμματισμό μετράει! Στην παραπάνω επαναληπτική δομή ΓΙΑ πριν εκχωρήσουμε την τιμή της μεταβλητής νιοστός στην προηγούμενος, εκχωρούμε την τιμή της προηγούμενος στην μεταβλητή προ_προηγούμενος. Αν οι δύο αυτές εκχωρήσεις γίνονταν με διαφορετική σειρά, το αποτέλεσμα θα ήταν διαφορετικό.

Άσκηση για εμβάθυνση

Η ακολουθία Motzkin (M(n)) δίνεται από τον εξής αναδρομικό τύπο, για n φυσικό αριθμό:

fib2

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

Οι πρώτοι 10 αριθμοί Motzkin είναι: 1, 1, 2, 4, 9, 21, 51, 127, 323, 835

Γράψτε μία συνάρτηση με μία ακέραια παράμετρο (θεωρείστε ότι κατά την κλήση της συνάρτησης το όρισμα είναι πάντα φυσικός αριθμός μικρότερος ή ίσος από το 10.000) η οποία επιστρέφει τον αριθμό της ακολουθίας Motzkin που βρίσκεται στην θέση την οποία υποδεικνύει η παράμετρος.

Σχετικοί σύνδεσμοι

https://en.wikipedia.org/wiki/Motzkin_number

Άρθρο της wikipedia σχετικά με την ακολουθία Fibonacci στα ελληνικά

Βίντεο