Πολλαπλάσια και ημίτονα

Τελευταία ενημέρωση 18/10/2016

Πρόβλημα

Χωρίς να χρησιμοποιήσετε τους τελεστές MOD, DIV και /, αλλά ούτε και την ενσωματωμένη συνάρτηση Α_Μ (Ακέραιο Μέρος), να συμπληρώσετε την εντολή στην παρακάτω συνάρτηση ώστε να επιστρέφει “Αληθές” αν η παράμετρος είναι άρτιος φυσικός αριθμός και “Ψευδές” αν είναι περιττός.

ΣΥΝΑΡΤΗΣΗ is_even(n): ΛΟΓΙΚΗ

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: n

ΑΡΧΗ

is_even <- …

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

Λύση

is_even <-  ΗΜ(n*90) = 0

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

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

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

Συμπληρώστε την εντολή στην παρακάτω συνάρτηση ώστε να επιστρέφει “Αληθές” αν η παράμετρος n διαιρείται (ακριβώς) με την m και “Ψευδές” αν δεν διαιρείται. Θεωρείστε ότι κατά την κλήση της συνάρτησης τα ορίσματα είναι φυσικοί αριθμοί.

ΣΥΝΑΡΤΗΣΗ div_n_by_m(n, m): ΛΟΓΙΚΗ

ΜΕΤΑΒΛΗΤΕΣ

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

ΑΡΧΗ

div_n_by_m <-  ΗΜ(…) = …

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

Βίντεο

ν παραγοντικό (ν!)

Πρόβλημα

Το ν! παραγοντικό ορίζεται για κάθε φυσικό αριθμό ν ως εξής:

για ν=0: 0! = 1

για ν>0: ν! = 1⋅2⋅3⋅ …⋅ν

Γράψτε μια συνάρτηση με μία ακέραια παράμετρο η οποία επιστρέφει το παραγοντικό που υποδεικνύει η παράμετρος. Για παράδειγμα με όρισμα 0 η συνάρτηση πρέπει να επιστρέφει 0!= 1 ενώ με όρισμα 3 πρέπει να επιστρέφει 3! = 1⋅2⋅3 = 6.

Λύση

parag1

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

Για n=0 η συνάρτηση εκχωρεί στην μεταβλητή π την τιμή 1, ενώ η δομή επανάληψης δεν εκτελεί καμία επανάληψη, αφού η συνθήκη 1<=0 είναι ψευδής (βλ. Ακριβής). Επομένως, τελικά επιστρέφει 1, το οποίο είναι σωστό με βάση τον ορισμό του παραγοντικού.

Για ν>1 είναι εύκολο να δούμε ότι ν! = 1⋅2⋅3⋅ …⋅(ν-1) ⋅ν = (1⋅2⋅3⋅ …⋅(ν-1) )⋅ν = (ν-1)! ⋅ ν, το τελευταίο ισχύει και για ν=1 αφού 0!=1, δηλαδή το παραγοντικό ενός θετικού αριθμού είναι το παραγοντικό του προηγούμενου αριθμού επί τον αριθμό. Αυτή είναι και η λειτουργία της δομής επανάληψης στην παραπάνω συνάρτηση.

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

Το πρωτοντικό (primorial), το οποίο συμβολίζουμε με pn#, όπου n θετικός ακέραιος, ορίζεται ως εξής:

pn# = p1⋅ p2⋅ … ⋅pn, όπου, p1 , ο πρώτος “πρώτος” αριθμός (βλ. Πρώτοι αριθμοί), δηλαδή ο 2, p2 ο δεύτερος πρώτος αριθμός, δηλαδή ο 3, p3 ο τρίτος πρώτος αριθμός, δηλαδή ο 5 κοκ. Γράψτε μια συνάρτηση με μία ακέραια παράμετρο που επιστρέφει το πρωτοντικό που υποδεικνύει η παράμετρος.

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.