ν-οστό ψηφίο

Πρόβλημα

Γράψτε μία συνάρτηση με δύο ακέραιες παραμέτρους η οποία επιστρέφει έναν ακέραιο ο οποίος ισούται με το ψηφίο της πρώτης παραμέτρου στην θέση από δεξιά που υποδεικνύει η δεύτερη παράμετρος (η πρώτη θέση από δεξιά θεωρείται η 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.