Ψηφιακή ρίζα

Πρόβλημα

Η ψηφιακή ρίζα ενός αριθμού είναι ο μονοψήφιος αριθμός που προκύπτει αν αθροίσουμε αναδρομικά τα ψηφία του. Θεωρείστε ως δεδομένο ότι αυτή η διαδικασία καταλήγει πάντα σε μονοψήφιο αριθμό σε πεπερασμένο πλήθος βημάτων. Για παράδειγμα, η ψηφιακή ρίζα του 217 είναι:

2+1+7=10→1+0=1

Γράψτε μία συνάρτηση με μια ακέραια παράμετρο η οποία αντιστοιχεί στον αριθμό του οποίου την ψηφιακή ρίζα επιστρέφει.

Λύση

! χρησιμοποιούνται οι συναρτήσεις digit_trunc και nth_digit οι οποίες
!ορίζονται στην δημοσίευση «ν-οστό ψηφίο»
dr

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

Η απόδειξη ορθότητας είναι (σχεδόν) προφανής εφαρμογή του ορισμού της ψηφιακής ρίζας που χρησιμοποιείται στην διατύπωση του προβλήματος (βλ. Σχόλια, για κάποιες τεχνικές λεπτομέρειες σχετικά με την παραπάνω συνάρτηση). Αν θέλουμε βέβαια να είμαστε περισσότερο τυπικοί μπορούμε να αποδείξουμε με επαγωγή τόσο την ορθότητα του εξωτερικού όσο και του εμφωλευμένου βρόγχου, όπως στην περίπτωση του προγράμματος σχετικά με την ακολουθία Fibonacci.

Σχόλια

-Χρησιμοποιούμε την μεταβλητή της παραμέτρου προκειμένου να αποθηκεύσουμε το αποτέλεσμα του προγράμματος (για λόγους οικονομίας – φυσικά, θα μπορούσαμε δηλώσουμε μια επιπλέον μεταβλητή γι’ αυτόν τον σκοπό την οποία θα αρχικοποιούσαμε στην τιμή ν). Επειδή πρόκειται για συνάρτηση (και όχι για διαδικασία) αν κατά την κλήση της συνάρτησης το όρισμα είναι μια μεταβλητή (η οποία έχει πάρει τιμή, για παράδειγμα, με εισαγωγή από το πληκτρολόγιο), η τιμή αυτής της μεταβλητής στο πρόγραμμα που καλεί αυτήν την συνάρτηση δεν θα μεταβληθεί (παρόλο που εντός της συνάρτησης η μεταβλητή ν μεταβάλλεται – πρόκειται για αντίγραφο της μεταβλητής που περνιέται ως όρισμα και όχι η μεταβλητή του ορίσματος καθαυτή).

– Η συνθήκη ν > 9 σημαίνει ότι ο αριθμός ν έχει περισσότερα από 1 ψηφία (αφού είναι μεγαλύτερος του 9).

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

-Στην αρχή του εξωτερικού βρόγχου μηδενίζεται το άθροισμα των ψηφίων του ν (μεταβλητή αθροισμα_ψηφίων) και η μεταβλητή ι η οποία εκφράζει το πλήθος των ψηφίων του ν που περικόπτονται κάθε φορά. Επειδή η μεταβλητή ι ξεκινάει με αρχική τιμή 1, ενώ η θέση του ψηφίου ξεκινάει από το 0 (με βάση τον ορισμό της συνάρτησης nth_digit), η θέση του ψηφίου εκφράζεται σε κάθε επανάληψη του εμφωλευμένου βρόγχου ως ν-1.

– Στη δομή επανάληψης ΟΣΟ…ΜΕΧΡΙΣ_ΟΤΟΥ πρώτα εκτελείται το σώμα του βρόγχου και μετά ελέγχεται η συνθήκη εξόδου από αυτόν, σε αντίθεση με την δομή επανάληψης ΟΣΟ…ΕΠΑΝΑΛΑΒΕ, όπου πρώτα ελέγχεται η συνθήκη εξόδου και μετά εκτελείται το σώμα του βρόγχου (ως συνέπεια: η δομή επανάληψης ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ…ΜΕΧΡΙΣ_ΟΤΟΥ εκτελείται τουλάχιστον μία φορά, ενώ η δομή επανάληψης ΟΣΟ…ΕΠΑΝΑΛΑΒΕ είναι δυνατό να μην εκτελεστεί καμία φορά). Η επιλογή της πρώτης μορφής δομής επανάληψης στον εμφωλευμένο βρόγχο της παραπάνω λύσης είναι αναγκαία καθώς η τελευταία επανάληψη του βρόγχου θα είναι όταν το ι πάρει τιμή ίση με το πλήθος ψηφίων του ν, οπότε η έκφραση digit_trunc(ν, ι) παίρνει τιμή 0. Για αυτήν την τιμή όμως θέλουμε να εκτελεστεί το σώμα του βρόγχου όπου προσθέτεται το τελευταίο ψηφίο του ν, αυτό στην θέση ι-1, πριν ελεγχθεί η συνθήκη εξόδου.

– Ο,τιδήποτε εμφανίζεται στα δεξιά του συμβόλου “!” θεωρείται σχόλιο, δηλαδή δεν θεωρείται “ενεργό” κομμάτι του προγράμματος.

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

Δίνεται η παρακάτω συνάρτηση:

ΣΥΝΑΡΤΗΣΗ x(ν): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ν
ΑΡΧΗ
  ν <- ν MOD 9
  ΑΝ ν <> 0 ΤΟΤΕ
    x <- ν
  ΑΛΛΙΩΣ
    x <- 9
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Υπολογίστε (χωρίς την χρήση του διερμηνευτή) την τιμή που επιστρέφει αυτή η συνάρτηση και η συνάρτηση της λύσης για τα ορίσματα του παρακάτω συνόλου:

{99, 78, 44, 35, 29}

Τι παρατηρείτε;

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

Βίντεο