Ταληράκια

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο να επιλύει το ακόλουθο πρόβλημα:

Θεωρείστε δύο (ίσως φανταστικούς) τύπους κερμάτων αξίας α1 και α2 λεπτών, όπου α1 και α2 είναι οποιοιδήποτε θετικοί ακέραιοι με τον περιορισμό α1α2. Θεωρείστε ακόμη έναν μη-αρνητικό ακέραιο c. Υπάρχει τρόπος επιλέγοντας κάποια ποσότητα (ίσως 0) από το ένα κέρμα και κάποια ποσότητα (ίσως 0) από το άλλο, το άθροισμα των αξιών αυτών των κερμάτων να είναι ίσο με c;

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

Παράδειγμα:

Για αξίες κερμάτων 5 και 7 υπάρχει τρόπος να σχηματιστεί το ποσό 17, αλλά δεν υπάρχει τρόπος να σχηματιστεί το ποσό 23.

Λύση

psila

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ιστορικό σημείωμα

Το παραπάνω πρόβλημα στην γενική του μορφή, δηλαδή όχι μόνο για δύο τύπους κερμάτων, αλλά για οποιοδήποτε πεπερασμένο (θετικό ακέραιο) πλήθος κερμάτων (ανά δύο με άνισες αξίες) είναι γνωστό ως εκδοχή εφικτότητας του προβλήματος “κάνω ψιλά” (Change Making Problem – CMP). Ο καλύτερος αλγόριθμος ο οποίος έχει βρεθεί μέχρι τώρα για το τελευταίο αυτό πρόβλημα είναι πολύ αργός για την ανθρώπινη κλίμακα χρόνου για είναι χρήσιμος. Αν καταφέρνατε να βρείτε έναν «γρήγορο» αλγόριθμο γι’ αυτό το πρόβλημα, θα κερδίζατε το βραβείο του ενός εκατομμυρίου δολαρίων του Ινστιτούτου Μαθηματικών Clay, καθώς θα είχατε λύσει το μεγαλύτερο (ίσως) πρόβλημα πληροφορικής/μαθηματικών της εποχής μας και (ίσως) όλων των εποχών: το πρόβλημα “P versus NP”.

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

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

Ακριβής λειτουργία της δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ

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

Θεωρούμε τις ακέραιες* μεταβλητές ι, α, β, γ με τον περιορισμό γ≠0 και την γενική μορφή αυτής της δομής επανάληψης:

(*Σημείωση: Οι μεταβλητές ι, α, β και γ μπορεί να είναι και πραγματικές. Η γενική λογική παραμένει η ίδια με την διαφορά ότι ο τύπος α + (Α_Τ(α – β)  DIV  Α_Τ(γ) + 1) * γ ο οποίος παρουσιάζεται παρακάτω δεν ισχύει σ’ αυτήν την περίπτωση)

ΓΙΑ  ι  ΑΠΟ  α  ΜΕΧΡΙ  β  ΜΕ_ΒΗΜΑ  γ

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Η ακριβής λειτουργία αυτής της δομής επανάληψης είναι η εξής (με την αυστηρή σειρά βημάτων που υποδεικνύει ο παρακάτω αλγόριθμος):

1) Εκχώρησε στην μεταβλητή ι την τιμή της α.

2)

α) Εάν η μεταβλητή γ (βήμα) είναι θετική

Εάν η λογική συνθήκη ι <= β (η ι είναι μικρότερη ή ίση της β) είναι αληθής, τότε εκτέλεσε το σώμα του βρόγχου, αλλιώς τερμάτισε την δομή επανάληψης (οπότε το πρόγραμμα συνεχίζεται με τις εντολές που βρίσκονται ακριβώς μετά την εντολή “ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ”)

β) Εάν η μεταβλητή γ (βήμα) είναι αρνητική

Εάν η λογική συνθήκη ι >= β (η ι είναι μεγαλύτερη ή ίση της β) είναι αληθής, εκτέλεσε το σώμα του βρόγχου, αλλιώς τερμάτισε την δομή επανάληψης (οπότε το πρόγραμμα συνεχίζεται με τις εντολές που βρίσκονται ακριβώς μετά την εντολή “ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ”).

3) Εκχώρησε στην τιμή του ι την τρέχουσα τιμή του ι συν την τιμή του βήματος:

ι  <-  ι + γ

(Αν το γ (βήμα) είναι αρνητικό, πχ -4, έχουμε ι  <-  ι + (-4), ή ισοδύναμα    ι  <-  ι – 4 )

4) Πήγαινε στο βήμα 2).

Σημείωση 1:

Για την δομή επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ είναι δυνατό να μην εκτελεστεί καμία (!) επανάληψη, εάν η λογική συνθήκη που ελέγχεται είναι ψευδής χωρίς να έχει εκτελεστεί προηγούμενα καμία επανάληψη. Αυτό γενικά είναι “νόμιμο” και μάλιστα χρήσιμο σε πολλές περιπτώσεις τόσο στην Γλώσσα όσο και σε πραγματικές γλώσσες προγραμματισμού.

Σημείωση 2:

Ακριβώς μετά τον τερματισμό της δομής επανάληψης η μεταβλητή ι έχει τιμή:

α) Εάν δεν έχει εκτελεστεί καμία επανάληψη (δηλαδή αν ι =α )

Ίση με το α

Σημείωση:

Μετά το τέλος της  δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ δεν έχει εκτελεστεί καμία επανάληψη αν και μόνο αν η λογική συνθήκη ι=α είναι αληθής.

β) Εάν έχει εκτελεστεί τουλάχιστον μία επανάληψη (δηλαδή αν ι <> α)

Ίση με  α + (Α_Τ(α – β)  DIV  Α_Τ(γ) + 1) * γ

(όπου Α_Τ η ενσωματωμένη συνάρτηση που επιστρέφει την απόλυτη τιμή της παραμέτρου)

Σημείωση:

Μετά το τέλος της  δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ έχει εκτελεστεί τουλάχιστον μία επανάληψη αν και μόνο αν η λογική συνθήκη ι<>α είναι αληθής.

Παραδείγματα

A)

ΓΙΑ ι ΑΠΟ 5 ΜΕΧΡΙ 3
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = 5
β = 3
γ = 1

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή 5

2) Ελέγχεται η συνθήκη 5 <= 3 η οποία είναι ψευδής και η δομή επανάληψης τερματίζει.

Βλέπουμε δηλαδή ότι δεν εκτελείται καμία επανάληψη.

Κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή σύμφωνα με τα παραπάνω:
ίση με α, δηλαδή 5

Β)

ΓΙΑ ι ΑΠΟ 5 ΜΕΧΡΙ 15 ΜΕ_ΒΗΜΑ 5
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = 5
β = 15
γ = 5

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή 5

2) Ελέγχεται η συνθήκη 5 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 5.

3) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 10.

4) Ελέγχεται η συνθήκη 10 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 10.

5) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 15.

6) Ελέγχεται η συνθήκη 15 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 15.
.
7) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 20.

8) Ελέγχεται η συνθήκη 20 <= 15 η οποία είναι Ψευδής, άρα η δομή επανάληψης τερματίζει.

Άρα, κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή 20, αυτό όμως μπορεί να υπολογιστεί σύμφωνα με τον παραπάνω τύπο και χωρίς την προηγούμενη προσομοίωση εκτέλεσης του αλγορίθμου:

5 + (Α_Τ(5 – 15)  DIV  Α_Τ(5) + 1) * 5 = 5 + (Α_Τ(-10)  DIV  Α_Τ(5) + 1) * 5 =
5 + (10 DIV  5 + 1) * 5 = 5 + (2 + 1) * 5 = 5 + (2 + 1) * 5 = 5+3*15  = 5+15 = 20

Γ)

ΓΙΑ ι ΑΠΟ -5 ΜΕΧΡΙ -2 ΜΕ_ΒΗΜΑ -1
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = -5
β = -2
γ = -1

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή -5

2) Ελέγχεται η συνθήκη -5 >= -2 η οποία είναι ψευδής και η δομή επανάληψης τερματίζει.

Βλέπουμε δηλαδή ότι δεν εκτελείται καμία επανάληψη.

Κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή σύμφωνα με τα παραπάνω:
ίση με α, δηλαδή -5

Δ)

ΓΙΑ ι ΑΠΟ -5 ΜΕΧΡΙ -8 ΜΕ_ΒΗΜΑ -2
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = -5
β =  -8
γ = -2

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή -5

2) Ελέγχεται η συνθήκη -5 >= -8 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή -5.

3) Η τιμή του ι μειώνεται κατά 2, δηλαδή γίνεται -7.

4) Ελέγχεται η συνθήκη -7 >= -8 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή -7.

5) Η τιμή του ι μειώνεται κατά -2, δηλαδή γίνεται -9.

6) Ελέγχεται η συνθήκη -9 >= -8 η οποία είναι Ψευδής, άρα η δομή επανάληψης τερματίζει.

Άρα, κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή -9, αυτό όμως μπορεί να υπολογιστεί σύμφωνα με τον παραπάνω τύπο και χωρίς την προηγούμενη προσομοίωση εκτέλεσης του αλγορίθμου:

-5 + (Α_Τ(-5 – (-8))  DIV  Α_Τ(-2) + 1) * (-2) = -5 + (Α_Τ(-5 + 8)  DIV  Α_Τ(-2) + 1)* (-2)=
-5 + (Α_Τ(3)  DIV  Α_Τ(-2) + 1) * (-2) = -5 + (3  DIV 2 + 1) * (-2) = -5 + (1 + 1) * (-2) =
-5 + 2 * (-2) = -5-4 = -9

Ιστορικό σημείωμα

Μια πρώιμη μορφή της δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ εμφανίστηκε στον χώρο των μαθηματικών το 1931 με την ονομασία «πρωτόγονη αναδρομική συνάρτηση» κατά την δημοσίευση των αποδείξεων των θεωρημάτων μη-πληρότητας του Κουρτ Γκέντελ. Οι πρωτόγονες αναδρομικές συναρτήσεις είχαν προταθεί 8 χρόνια νωρίτερα από τον Σκόλεμ.

Ψηφιακή ρίζα

Πρόβλημα

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

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

ν-οστό ψηφίο

Πρόβλημα

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