Ψηφιακή ρίζα

Πρόβλημα

Η ψηφιακή ρίζα ενός αριθμού είναι ο μονοψήφιος αριθμός που προκύπτει αν αθροίσουμε αναδρομικά τα ψηφία του. Θεωρείστε ως δεδομένο ότι αυτή η διαδικασία καταλήγει πάντα σε μονοψήφιο αριθμό σε πεπερασμένο πλήθος βημάτων. Για παράδειγμα, η ψηφιακή ρίζα του 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}

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