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 στα ελληνικά

Βίντεο

 

 

 

ν-οστό ψηφίο

Πρόβλημα

Γράψτε μία συνάρτηση με δύο ακέραιες παραμέτρους η οποία επιστρέφει έναν ακέραιο ο οποίος ισούται με το ψηφίο της πρώτης παραμέτρου στην θέση από δεξιά που υποδεικνύει η δεύτερη παράμετρος (η πρώτη θέση από δεξιά θεωρείται η 0)*. Υποθέστε ότι κατά την κλήση της συνάρτησης τα ορίσματα είναι φυσικοί αριθμοί. Για παράδειγμα το πρώτο ψηφίο από δεξιά (το τελευταίο από αριστερά ή το ψηφίο στην θέση 0) του 167 είναι το 7, ενώ το τρίτο (θέση 2) είναι το 1.

Προκειμένου να λύσουμε το πρόβλημα θα λύσουμε προηγούμενα δύο “ενδιάμεσα” προβλήματα.

Ενδιάμεσο πρόβλημα 1: πρώτο ψηφίο από δεξιά ενός φυσικού αριθμού

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

Λύση

ΣΥΝΑΡΤΗΣΗ last_digit(k): ΑΚΕΡΑΙΑ

  ΜΕΤΑΒΛΗΤΕΣ

    ΑΚΕΡΑΙΕΣ: k

ΑΡΧΗ

  last_digit <- k MOD 10

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

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

Θα πρέπει να αποδείξουμε ότι το τελευταίο από αριστερά ψηφίο ενός αριθμού είναι το υπόλοιπο της ευκλείδειας διαίρεσης αυτού του αριθμού με το 10. Έστω ένας φυσικός αριθμός dk-1dk-2…d0 με k ψηφία όπου dk-1, dk-2, … , d0 είναι δεκαδικά ψηφία στην θέση από δεξιά του αριθμού που δείχνει ο δείκτης. Τότε ο αριθμός αυτός γράφεται, ως γνωστό, ως άθροισμα δυνάμεων του 10 ως εξής:

dk-110k-1 + dk-210k-2 + … + d1101 + d0100 = dk-110k-1 + dk-210k-2 + … + d110 + d0

Με άλλα λόγια ένας φυσικός αριθμός είναι ένα άθροισμα με όρους το ψηφίο στην θέση 0 επί το 1, το ψηφίο στην θέση 1 επί το 10, το ψηφίο στην θέση 2 επί το 100 κοκ. Εξαιρώντας τον d0, οι όροι του παραπάνω αθροίσματος που απομένουν διαιρούνται ο καθένας (ακριβώς) με το 10. Επομένως, υπάρχει φυσικός αριθμός m τέτοιος ώστε dk-110k-1 + dk-210k-2 + … +d110 = 10m. Άρα, κάθε φυσικός αριθμός μπορεί να γραφτεί ως 10m+d0. Από το τελευταίο και το ότι για το d0 ισχύει 0≤ d≤ 9, συνεπάγεται ότι το d0 είναι το υπόλοιπο της ευκλείδειας διαίρεσης του αριθμού με το 10. Το d0 όμως είναι και το τελευταίο ψηφίο του αριθμού.

Ενδιάμεσο πρόβλημα 2: περικοπή κατά m ψηφία από δεξιά ενός φυσικού αριθμού

Γράψτε μία συνάρτηση με δύο ακέραιες παραμέτρους η οποία επιστρέφει έναν ακέραιο ο οποίος προκύπτει αν από την πρώτη παράμετρο αφαιρεθούν τόσα ψηφία από δεξιά όσα υποδεικνύει η δεύτερη παράμετρος. Θεωρείστε ότι κατά την κλήση της συνάρτησης τα ορίσματα είναι φυσικοί αριθμοί. Για παράδειγμα, με πρώτη παράμετρο 21745 και δεύτερη 2, η συνάρτηση πρέπει να επιστρέφει τον αριθμό 217 (με περικοπή των 2 τελευταίων ψηφίων του 21745).

Λύση

ΣΥΝΑΡΤΗΣΗ digit_trunc(k, m): ΑΚΕΡΑΙΑ

  ΜΕΤΑΒΛΗΤΕΣ

    ΑΚΕΡΑΙΕΣ: k, m

ΑΡΧΗ

  digit_trunc <- k DIV Α_Μ(10^m)

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

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

Εάν λ το πλήθος των ψηφίων του αριθμού k, διακρίνουμε τις περιπτώσεις:

α) m < λ

Όπως είδαμε παραπάνω ο k μπορεί να γραφτεί στην μορφή:

dλ-110λ-1 + dλ-210λ-2 + … + d110 + d0

Οι όροι του παραπάνω αθροίσματος που αντιστοιχούν σε ψηφία του k σε θέσεις μεγαλύτερες ή ίσες του m διαιρούνται (ακριβώς) με το 10m. Άρα υπάρχει φυσικός αριθμός α τέτοιος ώστε k = α 10m + dm-110m-1 + dm-210m-2 + … +d0

Μπορεί να αποδειχτεί ότι dm-110m-1 + dm-210m-2 + … +d0 < 10m. Επομένως, το α είναι το πηλίκο της ακέραιας διαίρεσης του k με το 10m. Ακόμη έχουμε:

ld

Όμως η τελευταία μορφή του α είναι ο φυσικός αριθμός που απομένει αν αποκόψουμε από τον k τα τελευταία m ψηφία.

β) Αν m ≥ λ (επειδή όπως είδαμε παραπάνω dλ-110λ-1 + dλ-210λ-2 + … +d0 < 10m) τότε το πηλίκο της ευκλείδειας διαίρεσης του k με το 10m είναι 0. Δηλαδή, σύμφωνα με το παραπάνω πρόγραμμα, ο αριθμός που απομένει αν περικόψουμε από δεξιά έναν φυσικό αριθμό κατά πλήθος ψηφίων μεγαλύτερο ή ίσο από το πλήθος των ψηφίων του είναι ο 0. Καμία παραβίαση της ορθότητας του προγράμματος, αφού είναι γνωστό ότι μπορούμε να προσθέσουμε όσα 0 θέλουμε στα αριστερά ενός φυσικού αριθμού χωρίς αυτός ο αριθμός να αλλάξει.

Λύση του αρχικού προβλήματος με χρήση των λύσεων των ενδιάμεσων προβλημάτων

ΣΥΝΑΡΤΗΣΗ nth_digit(k, m): ΑΚΕΡΑΙΑ

  ΜΕΤΑΒΛΗΤΕΣ

    ΑΚΕΡΑΙΕΣ: k, m

ΑΡΧΗ

  nth_digit <- last_digit( digit_trunc(k, m))

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

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

Είναι προφανές ότι το ν-οστό ψηφίο από δεξιά ενός φυσικού αριθμού είναι το πρώτο ψηφίο από δεξιά του αριθμού που προκύπτει από την περικοπή του αρχικού αριθμού από δεξιά κατά ν ψηφία.

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

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

* Συνηθίζεται στα μαθηματικά να χρησιμοποιούνται οι φυσικοί αριθμοί προκειμένου να καθοριστεί η διάταξη διακριτών στοιχείων. Ο πρώτος φυσικός αριθμός είναι ο 0, όχι ο 1.