Επαναληπτική Άσκηση ΑΕΠΠ 2019-α

Photo by Franck V. on Unsplash

Θεωρείστε ως δεδομένη (δεν χρειάζεται να την κατασκευάσετε) την συνάρτηση υποάθροισμα(A, ν) : Λογική, όπου Α μονοδιάστατος πίνακας ακεραίων με 1000 στοιχεία και ν ακέραια μεταβλητή. Η συνάρτηση υποάθροισμα επιστρέφει Αληθής αν από την θέση 1 ως και την θέση ν του Α υπάρχουν κάποια στοιχεία (ένα ή περισσότερα) τα οποία έχουν άθροισμα μηδέν, σε διαφορετική περίπτωση επιστρέφει Ψευδής. Για παράδειγμα, αν ο Α περιέχει τις τιμές 5, -2, -3 από την θέση 1 μέχρι και την θέση ν, τότε η υποάθροισμα θα επιστρέψει Αληθής, αφού 5-2-3=0, ενώ αν ο Α περιέχει μόνο θετικές τιμές από την θέση 1 μέχρι και την θέση ν, θα επιστρέψει, προφανώς, Ψευδής.

Κατασκευάστε ένα πρόγραμμα το οποίο να διαβάζει τις τιμές χιλίων ακεραίων, να τις καταχωρίζει στον πίνακα Α και – με την βοήθεια της συνάρτησης υποάθροισμα – αν υπάρχουν κάποιες τιμές στο πίνακα Α που έχουν άθροισμα μηδέν, να εμφανίζει έναν (οποιονδήποτε) συγκεκριμένο συνδυασμό στοιχείων που έχουν άθροισμα μηδέν, αλλιώς να εμφανίζει το μήνυμα “δεν υπάρχει συνδυασμός στοιχείων με άθροισμα 0”. Για παράδειγμα, στο πρώτο από τα παραπάνω δύο παραδείγματα αρκεί να εμφανίσει τις τιμές 5,-2 και -3, ενώ στο δεύτερο θα πρέπει να εμφανίσει το μήνυμα “δεν υπάρχει συνδυασμός στοιχείων με άθροισμα 0”.

Περικοπή στα ν δεκαδικά ψηφία

Πρόβλημα

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

Λύση

perikopi1

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

Σχόλιο

Η συνάρτηση Α_Τ χρησιμοποιείται παραπάνω στην περίπτωση της αρνητικής πραγματικής παραμέτρου, διότι από τα αναφερόμενα στο σχολικό βιβλίο προκύπτει ασάφεια για την συνάρτηση Α_Μ όταν η παράμετρος είναι αρνητική.

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

Χρησιμοποιώντας την λογική του αλγορίθμου της παραπάνω λύσης, γράψτε μια συνάρτηση που να στρογγυλοποιεί έναν δεδομένο πραγματικό αριθμό σε δεδομένο πλήθος δεκαδικών ψηφίων σύμφωνα με την μέθοδο «μισό-πάνω» (half -(round)up).

Ταληράκια

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

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

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

Παράδειγμα:

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

Λύση

psila

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

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

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

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

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

Το κόσκινο του Ερατοσθένη

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

Πρόβλημα

Το κόσκινο του Ερατοσθένη είναι ένας αλγόριθμος για την ανεύρεση όλων των πρώτων αριθμών οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον δεδομένο φυσικό αριθμό – σημειώνεται ότι δεν υπάρχει πρώτος αριθμός μικρότερος του 2. Ο αλγόριθμος αυτός για χαρτί και μολύβι, δεδομένου ενός φυσικού αριθμού n για τον οποίο ζητείται να βρεθούν όλοι οι πρώτοι οι οποίοι είναι μικρότεροι ή ίσοι από αυτόν, είναι ο εξής:

1. Αν n<2 τερμάτισε – δεν υπάρχει πρώτος αριθμός μικρότερος του 2.

2. Γράψε κατά αύξουσα σειρά διάταξης όλους τους φυσικούς αριθμούς οι οποίοι είναι μεγαλύτεροι ή ίσοι του 2 και μικρότεροι ή ίσοι του n.

3. Διάγραψε όλα τα πολλαπλάσια του 2 (πχ επισημαίνοντάς τα με μια διαγώνια μολυβιά) τα οποία είναι μεγαλύτερα από το 2.

4.Βρες τον πρώτο (όσο αφορά την διάταξη) αριθμό που είναι μεγαλύτερος του 2 και δεν έχει διαγραφτεί – αν δεν υπάρχει τέτοιος αριθμός πήγαινε στο βήμα 5. Πήγαινε στο βήμα 3 και εκτέλεσέ το, αυτό και το επόμενο (το 4, δηλαδή το τρέχον), θεωρώντας αντί για τον αριθμό 2, τον αριθμό που βρήκες στην αρχή αυτού του βήματος.

5. Οι πρώτοι αριθμοί οι οποίοι είναι μικρότεροι ή ίσοι από τον n είναι οι αριθμοί που δεν είναι διαγραμμένοι.

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο με εφαρμογή του παραπάνω αλγόριθμου εμφανίζει στην οθόνη όλους τους πρώτους αριθμούς οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον φυσικό αριθμό n ≥ 2.

Λύση

eratosth

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

Ασκήσεις για εμβάθυνση

1) Γιατί θεωρείτε ότι ο παραπάνω αλγόριθμος ονομάζεται «κόσκινο»;

2) Τροποποιείστε το παραπάνω πρόγραμμα θεωρώντας ως δεδομένο ότι στο βήμα 3 του αλγόριθμου ο οποίος αναφέρεται στην διατύπωση του προβλήματος αρκεί να διαγραφτούν τα πολλαπλάσια του τρέχοντος αριθμού τα οποία είναι μεγαλύτερα ή ίσα από το τετράγωνο του τρέχοντος αριθμού, διότι τα υπόλοιπα έχουν ήδη διαγραφτεί πριν ο αλγόριθμος φτάσει σ’ αυτό το σημείο. Αν το τετράγωνο του τρέχοντος αριθμού είναι μεγαλύτερο από τον αριθμό n, ο αλγόριθμος πρέπει να μεταβαίνει στο βήμα 5.

Βίντεο

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

Τελευταία ενημέρωση 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 <-  ΗΜ(…) = …

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

Βίντεο

Τρίγωνο Pascal (-Khayyám-Yang Ηui)

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

Το τρίγωνο Πασκάλ n γραμμών κατασκευάζεται (μεταξύ άλλων) σύμφωνα με τον ακόλουθο αλγόριθμο:

1) Θεώρησε έναν τετραγωνικό πίνακα φυσικών αριθμών n × n – η θέση (κ,λ) στον πίνακα είναι η θέση στην γραμμή κ και στην στήλη λ. Θεώρησε ότι η πρώτη γραμμή και η πρώτη στήλη είναι η 0 (όπως συνηθίζεται γενικότερα στα μαθηματικά).

2) Αρχικοποίησε τον πίνακα θέτοντας την τιμή 0 σε κάθε θέση.

3) Για την γραμμή 0 θέσε την τιμή της θέσης (0,0) ίση με 1.

4) Για κάθε επόμενη γραμμή:

Για κάθε θέση της γραμμής ξεκινώντας από την θέση 0 (και μεταβαίνοντας κάθε φορά στην αμέσως επόμενη):

α) Αν πρόκειται για την πρώτη θέση της γραμμής (στήλη 0) θέσε την τιμή της θέσης ίση με 1.

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

γ) Αν πρόκειται για άλλη θέση από αυτή που περιγράφεται στα α), β) θέσε την τιμή της θέσης ίση με το άθροισμα της τιμής της πάνω αριστερά θέσης και της τιμής της θέσης ακριβώς πάνω από την τρέχουσα.

Πρόβλημα

Γράψτε μια διαδικασία με παράμετρο έναν τετραγωνικό πίνακα και έναν ακέραιο που εκφράζει τις διαστάσεις του πίνακα, η οποία κατασκευάζει το τρίγωνο Πασκάλ στον πίνακα της παραμέτρου. Θεωρείστε ότι κατά την κλήση της διαδικασίας η παράμετρος που εκφράζει τις διαστάσεις του πίνακα δεν ξεπερνάει το 500. Κάντε τον απαραίτητο μετασχηματισμό στον παραπάνω αλγόριθμο, λαμβάνοντας υπόψη ότι η πρώτη γραμμή και η πρώτη στήλη ενός πίνακα στην Γλώσσα του μαθήματος ΑΕΠΠ δεν είναι η 0, αλλά η 1.

Λύση

pascalt

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

Ασκήσεις για εμβάθυνση

1)

Σημείωση:

Στην παρακάτω διατύπωση του προβλήματος για όλες τις αναφερόμενες θέσεις πίνακα (κ,λ) θεωρείται ως πρώτη γραμμή και πρώτη στήλη η 0. Κάντε την απαραίτητη μετατροπή για τις θέσεις του πίνακα στην Γλώσσα (όπου πρώτη γραμμή και πρώτη στήλη είναι πάντα η 1).

Θεωρείστε ένα “στιγμιότυπο” του προβλήματος Ζευγάρια με πλήθος μαθητών τάξης 20. Γράψτε ένα πρόγραμμα που εμφανίζει στην οθόνη την λύση του προβλήματος καλώντας την συνάρτηση pairs και αμέσως μετά κατασκευάζει ένα τρίγωνο Πασκάλ 21 γραμμών και εμφανίζει στην οθόνη την τιμή στην θέση (20, 2) του πίνακα του τριγώνου Πασκάλ. Εκτελέστε το πρόγραμμα στον διερμηνευτή. Τι παρατηρείτε; Σκεπτόμενοι επαγωγικά, ποια σημασία εικάζετε ότι έχει η τιμή του πίνακα, για παράδειγμα στις θέσεις (20,3), (19,4), (15,0);

2)

Γράψτε μία συνάρτηση με δύο ακέραιες παραμέτρους, από τις οποίες η πρώτη εκφράζει το πλήθος των γραμμών ενός τριγώνου Πασκάλ και η δεύτερη μια συγκεκριμένη γραμμή του τριγώνου, η οποία επιστρέφει το άθροισμα τιμών της διαγώνιας διάταξης θέσεων η οποία ορίζεται ως εξής:

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

Γράψτε ένα πρόγραμμα το οποίο εμφανίζει τις τιμές που επιστρέφει η προηγούμενη συνάρτηση με όρισμα που αντιστοιχεί στην δεύτερη παράμετρο διαδοχικά 1, 2, 3, … ,20. Στην συνέχεια εμφανίζει τις τιμές που επιστρέφει η συνάρτηση F(ν) (ακολουθία Fibonacci) με όρισμα διαδοχικά 1, 2, 3, … ,20. Τι παρατηρείτε;

3)

Στην γραμμή 2 (θεωρώντας εδώ ως πρώτη γραμμή την 0) του τριγώνου Πασκάλ υπάρχουν τρεις τιμές, οι 1, 2 και 1. Θεωρώντας την γνωστή ταυτότητα (α+β)2 = α2+2αβ+β2 = 1α2+2αβ+1β2, σκεπτόμενοι επαγωγικά ποια σημασία εικάζετε ότι έχει η ακολουθία τιμών κάθε γραμμής στο τρίγωνο Πασκάλ;

Σχετικοί σύνδεσμοι

https://en.wikipedia.org/wiki/Inductive_reasoning

https://en.wikipedia.org/wiki/Deductive_reasoning

https://en.wikipedia.org/wiki/Pascal%27s_triangle

http://mathworld.wolfram.com/PascalsTriangle.html

https://en.wikipedia.org/wiki/Omar_Khayyam

https://en.wikipedia.org/wiki/Yang_Hui

https://en.wikipedia.org/wiki/Blaise_Pascal

Βίντεο

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

Πρόβλημα

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

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

Ώρα χωρίς «αν»

Πρόβλημα

Σ’ ένα σύνηθες ηλεκτρονικό ρολόι το πρώτο δευτερόλεπτο κάθε λεπτού είναι το 0 και το τελευταίο το 59 (60 δευτερόλεπτα συνολικά). Γράψτε μια συνάρτηση με μια ακέραια παράμετρο, η οποία εκφράζει το προηγούμενο δευτερόλεπτο, η οποία επιστρέφει το τρέχον δευτερόλεπτο, χωρίς να χρησιμοποιήσετε καμία δομή επιλογής (ΑΝ…ΤΟΤΕ ή ΕΠΙΛΕΞΕ…ΠΕΡΙΠΤΩΣΗ). Θεωρείστε ότι κατά την κλήση της συνάρτησης το όρισμα είναι πάντα μεγαλύτερο ή ίσο του 0 και μικρότερο ή ίσο του 59. Για παράδειγμα με όρισμα 58 η συνάρτηση πρέπει να επιστρέφει 59, ενώ με όρισμα 59 πρέπει να επιστρέφει 0.

Λύση

ΣΥΝΑΡΤΗΣΗ next_sec(n): ΑΚΕΡΑΙΑ

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: n

ΑΡΧΗ

next_sec <- (n + 1) MOD 60

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

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

Εάν α < β, η ευκλείδεια διαίρεση του α με τον β δίνει υπόλοιπο ίσο με α, ενώ αν α = β δίνει 0.

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

Γράψτε μια διαδικασία με έξι ακέραιες παραμέτρους, από τις οποίες οι τρεις πρώτες εκφράζουν αντίστοιχα τις ώρες (0 ως 23), τα λεπτά (0 ως 59) και τα δευτερόλεπτα (0 ως 59). Η διαδικασία εκχωρεί στις τρεις τελευταίες παραμέτρους τις ώρες, τα λεπτά και τα δευτερόλεπτα μετά από ένα δευτερόλεπτο από την ώρα που υποδεικνύουν οι τρεις πρώτες παράμετροι. Για παράδειγμα, αν η ώρα που εκφράζουν οι τρεις πρώτες παράμετροι είναι 22:25:10, στις τρεις τελευταίες πρέπει να εκχωρηθούν κατάλληλες τιμές ώστε να εκφράζεται η ώρα 22:25:11, ενώ αν η αν η ώρα που εκφράζουν οι τρεις πρώτες παράμετροι είναι 22:59:59, στις τρεις τελευταίες πρέπει να εκχωρηθούν κατάλληλες τιμές ώστε να εκφράζεται η ώρα 23:00:00. Η διαδικασία δεν πρέπει να περιέχει καμία δομή επιλογής (ΑΝ…ΤΟΤΕ ή ΕΠΙΛΕΞΕ…ΠΕΡΙΠΤΩΣΗ). Θεωρείστε ότι τα πρώτα τρία ορίσματα κατά την κλήση της διαδικασίας είναι μέσα στα παραπάνω αναφερόμενα όρια.

Ψηφιακή ρίζα

Πρόβλημα

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

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

Ζευγάρια

Πρόβλημα

Ένας καθηγητής γυμναστικής ζητάει δύο εθελ-οντές/όντριες από την σχολική τάξη προκειμένου να παρουσιάσει μία άσκηση γυμναστικής για δύο άτομα. Γράψτε μία συνάρτηση με μια ακέραια παράμετρο η οποία αντιστοιχεί στο πλήθος των μαθητών της τάξης, η οποία επιστρέφει το πλήθος όλων των δυνατών επιλογών δύο ατόμων. Για παράδειγμα αν η τάξη έχει 3 άτομα με σύνολο ονομάτων {Μαρία, Νίκος, Ελένη} οι δυνατές επιλογές είναι 3: {Μαρία, Νίκος}, {Μαρία, Ελένη} και {Νίκος, Ελένη}.

Λύση

l1

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

Προκειμένου να βρούμε όλα τα δυνατά ζευγάρια ν διακεκριμένων στοιχείων χωρίς να μας ενδιαφέρει η διάταξη των ζευγαριών, δηλαδή τα υποσύνολα με πλήθος στοιχείων 2 των ν διακεκριμένων στοιχείων, μπορούμε να διατρέξουμε το σύνολο των στοιχείων συνδυάζοντας κάθε στοιχείο με όλα τα υπόλοιπα. Μ’ αυτό τον τρόπο σίγουρα δεν παραλείπουμε κάποιο υποσύνολο, όμως κάποια υποσύνολα θα συμπεριληφθούν περισσότερες από μία φορές. Ας εφαρμόσουμε αυτή τη μέθοδο στο παράδειγμα της διατύπωσης του προβλήματος:

1) Συνδυάζουμε την Μαρία με τα υπόλοιπα άτομα:

{Μαρία, Νίκος}, {Μαρία, Ελένη}

2) Συνδυάζουμε τον Νίκο με τα υπόλοιπα άτομα:

{Νίκος, Μαρία}, {Νίκος, Ελένη}

3) Συνδυάζουμε την Ελένη με τα υπόλοιπα άτομα:

{Ελένη, Μαρία}, {Ελένη, Νίκος}

Παρατηρούμε ότι μ’ αυτόν τον τρόπο κάθε ζευγάρι αναφέρεται δύο φορές. Ας δούμε πως μπορούμε να αποφύγουμε τα “διπλότυπα” στην γενική περίπτωση ν στοιχείων:

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

Εναλλακτική λύση 1

en1

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

Στο πρόγραμμα της αρχικής λύσης παρατηρούμε ότι για κάθε επανάληψη του εξωτερικού βρόγχου ο εμφωλευμένος βρόγχος προσθέτει στην μεταβλητή “πλήθος” την ποσότητα ν – (ι+1) + 1 = ν – ι (αφού ο τελευταίος βρόγχος εκτελείται για κ από ι+1 ως ν). Το ι όμως παίρνει τιμές από 1 ως ν, οπότε στην πρώτη επανάληψη του εξωτερικού βρόγχου αυξάνεται η τιμής της “πλήθος” κατά ν-1, στην δεύτερη κατά ν-2, στην τρίτη κατά ν-3 κοκ. Αυτή όμως είναι και η λειτουργία του παραπάνω προγράμματος.

Εναλλακτική λύση 2

ΣΥΝΑΡΤΗΣΗ count_2combination3(ν): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: ν
ΑΡΧΗ
count_2combination3 <- (ν*ν – ν) DIV 2
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Η απόδειξη ορθότητας αφήνεται ως άσκηση.

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

Υποθέστε ότι ο καθηγητής γυμναστικής ζητάει τρεις εθελ-οντές/όντριες. Πόσες είναι οι δυνατές επιλογές;

Υπόδειξη:

Στον εμφωλευμένο βρόγχο της βασικής λύσης εμφωλεύστε έναν ακόμα βρόγχο…