Μετάβαση στο περιεχόμενο
Topos Uranos
Ελληνικά

Από το πρόβλημα στον αλγόριθμο

Περίληψη

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

Μαθησιακοί στόχοι

  1. Να προδιαγράφει κανείς ένα απλό πρόβλημα δηλώνοντας τις εισόδους του, τις εξόδους του και τις συνθήκες που πρέπει να ικανοποιούν.
  2. Να περιγράφει έναν αλγόριθμο σε αριθμημένα βήματα, χωρίς ασάφεια, με ρητές αποφάσεις και επαναλήψεις.
  3. Να εκτελεί με το χέρι έναν αλγόριθμο με έναν πίνακα ίχνους και να βρίσκει το αποτέλεσμά του για μια δεδομένη είσοδο.
  4. Να διακρίνει, σε μια δεδομένη διαδικασία, την ακολουθία, την απόφαση και την επανάληψη, και να αιτιολογεί ότι μια επανάληψη τερματίζει.

Τι είναι ένα υπολογιστικό πρόβλημα

Ένα υπολογιστικό πρόβλημα είναι μια σχέση ανάμεσα σε δύο κατηγορίες δεδομένων: αυτά που λαμβάνονται, που λέγονται είσοδος, και αυτά που πρέπει να δοθούν, που λέγονται έξοδος. Η επίλυσή του δεν συνίσταται στο να βρεθεί μια απάντηση για μία περίπτωση, αλλά στο να διαθέτουμε μια μέθοδο που, για κάθε αποδεκτή είσοδο, παράγει μια έξοδο που ικανοποιεί τη σχέση. «Πόσο κάνει το 17 διά 5;» είναι μια ερώτηση· «δεδομένων δύο ακεραίων, να βρεθούν το πηλίκο και το υπόλοιπό τους» είναι ένα πρόβλημα, επειδή μιλά για όλα τα ζεύγη ακεραίων ταυτόχρονα.

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

ΠαράδειγμαΤο μέγιστο τριών αριθμών

Καθημερινή διατύπωση: «να βρεθεί ο μεγαλύτερος από τρεις αριθμούς». Προδιαγραφή:

  • Είσοδος: τρεις αριθμοί xx, yy, zz (ακέραιοι ή δεκαδικοί, χωρίς άλλη συνθήκη).
  • Έξοδος: ένας αριθμός mm.
  • Σχέση: ο mm είναι ένα από τα τρία δεδομένα, και κανένα από αυτά δεν είναι μεγαλύτερο από τον mm· δηλαδή m≥xm \geq x, m≥ym \geq y και m≥zm \geq z.

Η σχέση δεν λέει «ο μεγαλύτερος από τους τρεις», που είναι ακριβώς αυτό που θέλαμε να διευκρινίσουμε, αλλά δύο ελέγξιμες συνθήκες. Η πρώτη απαιτεί ο mm να είναι ένα από τα δεδομένα (χωρίς αυτήν, ο αριθμός 1000 θα ικανοποιούσε τη δεύτερη για σχεδόν οποιαδήποτε είσοδο)· η δεύτερη, να μην τον ξεπερνά κανένα. Και η προδιαγραφή λύνει παρεμπιπτόντως μια αμφιβολία που η διατύπωση άφηνε ανοιχτή: αν δύο δεδομένα ισοβαθμούν στο μέγιστο, όπως στο (4,9,9)(4, 9, 9), η έξοδος είναι 99, και δεν υπάρχει κανένα σφάλμα σε αυτό.

Η ίδια διατύπωση επιδέχεται διαφορετικές προδιαγραφές, και η επιλογή ανάμεσά τους είναι απόφαση, όχι αμέλεια. Η πιο διδακτική περίπτωση είναι η ακέραια διαίρεση. Για ακεραίους a≥0a \geq 0 και b>0b > 0, όλοι συμφωνούν: το πηλίκο qq και το υπόλοιπο rr είναι οι μοναδικοί ακέραιοι που ικανοποιούν

a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

Έτσι, για a=17a = 17 και b=5b = 5 είναι q=3q = 3 και r=2r = 2, επειδή 17=5⋅3+217 = 5 \cdot 3 + 2. Η διατύπωση «να διαιρεθούν δύο ακέραιοι» όμως δεν λέει τι γίνεται αν ο aa είναι αρνητικός, και το ερώτημα δεν είναι αδιάφορο: για a=−7a = -7 και b=2b = 2 υπάρχουν δύο εύλογες απαντήσεις.

ΠαράδειγμαΔύο προδιαγραφές της διαίρεσης με αρνητικό διαιρετέο

Πρώτη προδιαγραφή: το υπόλοιπο δεν είναι ποτέ αρνητικό, 0≤r<b0 \leq r < b. Τότε −7=2⋅(−4)+1-7 = 2 \cdot (-4) + 1, και η έξοδος είναι q=−4q = -4, r=1r = 1. Αυτή μελετά η μαθηματική επιστήμη, στο μάθημα «Διαιρετότητα και διαίρεση με υπόλοιπο» του κύκλου μαθημάτων Άλγεβρα και γεωμετρία I.

Δεύτερη προδιαγραφή: το πηλίκο είναι το αποτέλεσμα της διαίρεσης με δεκαδικά, με το δεκαδικό του μέρος απορριμμένο, δηλαδή στρογγυλεμένο προς το μηδέν· το υπόλοιπο είναι ό,τι λείπει, και έχει το πρόσημο του διαιρετέου. Τότε το −7/2=−3,5-7 / 2 = -3{,}5 αποκόπτεται σε −3-3, και −7=2⋅(−3)+(−1)-7 = 2 \cdot (-3) + (-1): η έξοδος είναι q=−3q = -3, r=−1r = -1.

Και οι δύο ικανοποιούν a=b⋅q+ra = b \cdot q + r· διαφέρουν στη συνθήκη που επιβάλλεται στο υπόλοιπο. Καμία δεν είναι σφάλμα, αλλά ένα πρόγραμμα που χρησιμοποιεί τη μία νομίζοντας ότι χρησιμοποιεί την άλλη θα δίνει λάθος αποτελέσματα με τους αρνητικούς. Ας προλάβουμε ένα στοιχείο: η C++ υιοθετεί τη δεύτερη, όπως θα φανεί στο μάθημα Αριθμητικές πράξεις· όποιος περιμένει την πρώτη θα αιφνιδιαστεί.

Υπάρχει και τρίτη επιλογή, η συχνότερη στην πράξη: να αποκλειστεί η περίπτωση από την προσυνθήκη. Αν η προδιαγραφή απαιτεί a≥0a \geq 0, το πρόβλημα των αρνητικών εξαφανίζεται, όχι επειδή λύθηκε, αλλά επειδή όποιος χρησιμοποιεί τη λύση έχει δεσμευτεί να μην το θέσει. Αυτό που δεν μπορεί να γίνει είναι να μείνει το ζήτημα αναπάντητο. Και για τον ίδιο λόγο η προδιαγραφή απαιτεί b>0b > 0: με b=0b = 0 δεν υπάρχουν qq και rr που να ικανοποιούν τη σχέση, και η σύμβαση πρέπει να το λέει.

Ένα συχνό σφάλμα είναι η προδιαγραφή με ένα παράδειγμα: «η έξοδος για 17 και 5 είναι 3 και 2». Ένα παράδειγμα φωτίζει, αλλά δεν προδιαγράφει, επειδή δεν λέει τι συμβαίνει με τις υπόλοιπες εισόδους· άπειρες διαφορετικές σχέσεις συμπίπτουν σε μία περίπτωση. Η προδιαγραφή γράφεται ως γενική συνθήκη, και τα παραδείγματα χρησιμεύουν έπειτα για να την ελέγξουμε.

Αλγόριθμοι

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

  • Περατότητα. Ο αλγόριθμος γράφεται με πεπερασμένο αριθμό εντολών και, για κάθε αποδεκτή είσοδο, τερματίζει αφού εκτελέσει πεπερασμένο αριθμό από αυτές. Μια διαδικασία που για κάποια είσοδο συνεχίζει για πάντα δεν είναι αλγόριθμος για αυτή την είσοδο.
  • Σαφήνεια. Κάθε εντολή έχει μία μόνο σημασία, και όποιος την εκτελεί ξέρει σε κάθε στιγμή τι να κάνει και ποια είναι η επόμενη εντολή. Καμία απόφαση δεν αφήνεται στην κρίση εκείνου που εκτελεί.
  • Γενικότητα. Ο αλγόριθμος λύνει το πρόβλημα για όλες τις αποδεκτές εισόδους, όχι μόνο για μία περίπτωση.

Με κάποια ελευθερία, αλγόριθμος λέγεται και μια διαδικασία σαφής που τερματίζει, αλλά που για κάποια αποδεκτή είσοδο δεν ικανοποιεί τη μετασυνθήκη: αυστηρά είναι αλγόριθμος για άλλο πρόβλημα, και θα λέμε ότι είναι λανθασμένος για το προδιαγεγραμμένο πρόβλημα. Έτσι θα μιλάμε στα προβλήματα αυτού του μαθήματος, που ανασκευάζουν λανθασμένους αλγορίθμους με ένα αντιπαράδειγμα.

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

Οι αλγόριθμοι αυτού του κύκλου μαθημάτων γράφονται πρώτα σε αριθμημένα βήματα, στα ελληνικά, με ορισμένες συμβάσεις. Τα δεδομένα που αλλάζουν κατά τη διάρκεια του αλγορίθμου ονομάζονται με γράμματα ή λέξεις, όπως qq ή rr, και λέγονται μεταβλητές. Γράφουμε «η rr παίρνει την τιμή r−br - b» για να πούμε ότι υπολογίζεται η r−br - b με την τρέχουσα τιμή της rr και το αποτέλεσμα γίνεται η νέα τιμή της rr· η προηγούμενη τιμή χάνεται. Στη σύντομη γραφή, που χρησιμοποιείται όταν κρατάμε σημειώσεις, η ίδια εντολή γράφεται με ένα βέλος προς τα αριστερά, που στο πληκτρολόγιο είναι r <- r - b. Οι εντολές εκτελούνται με τη σειρά του αριθμού τους, εκτός αν κάποια από αυτές ορίζει κάτι άλλο.

ΠαράδειγμαΗ διαίρεση με διαδοχικές αφαιρέσεις

Το πρόβλημα είναι αυτό που προδιαγράφηκε στην προηγούμενη παράγραφο: είσοδος, δύο ακέραιοι a≥0a \geq 0 και b>0b > 0· έξοδος, δύο ακέραιοι qq και rr με a=b⋅q+ra = b \cdot q + r και 0≤r<b0 \leq r < b. Η ιδέα είναι η μοιρασιά: αφαιρούνται από τον aa ομάδες των bb όσο γίνεται, μετρώνται οι ομάδες που αφαιρέθηκαν, και ό,τι περισσεύει είναι το υπόλοιπο.

  1. Η qq παίρνει την τιμή 00, και η rr παίρνει την τιμή aa.
  2. Όσο ισχύει r≥br \geq b, επανάλαβε τα βήματα 3 και 4· όταν πάψει να ισχύει, συνέχισε στο βήμα 5.
  3. Η rr παίρνει την τιμή r−br - b.
  4. Η qq παίρνει την τιμή q+1q + 1· επίστρεψε στο βήμα 2.
  5. Δώσε ως αποτέλεσμα τις qq και rr, και τερμάτισε.

Το βήμα 2 είναι μια ερώτηση που γίνεται κάθε φορά: πριν από τον πρώτο γύρο και μετά από καθέναν. Τα βήματα 3 και 4 αποτελούν το σώμα της επανάληψης, αυτό που επαναλαμβάνεται. Τίποτα δεν αφήνεται στην κρίση εκείνου που εκτελεί: σε κάθε στιγμή υπάρχει μία μόνο επόμενη εντολή.

Ο αλγόριθμος είναι αργός (για να διαιρέσει ένα εκατομμύριο διά τρία κάνει πάνω από τριακόσιες χιλιάδες γύρους), και η σχολική μέθοδος της διαίρεσης είναι πολύ ταχύτερη· είναι όμως σωστός, και η απλότητά του τον κάνει ιδανικό για να μάθουμε να συλλογιζόμαστε πάνω στους αλγορίθμους. Ο κύκλος μαθημάτων θα επανέλθει στη διαφορά ανάμεσα σε έναν σωστό και έναν αποδοτικό αλγόριθμο στο μάθημα Το κόστος ενός αλγορίθμου.

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

Εκτέλεση ενός αλγορίθμου με το χέρι

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

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

ΠαράδειγμαΤο ίχνος της διαίρεσης του 17 διά 5

Εκτελούμε τη διαίρεση με διαδοχικές αφαιρέσεις με a=17a = 17 και b=5b = 5. Το βέλος του σχήματος δείχνει το βήμα που μόλις εκτελέστηκε· η διακεκομμένη γραμμή θυμίζει ότι το βήμα 4 επιστρέφει στο 2.

Απόδειξη

  1. (q,r)=(0,17)(q, r) = (0, 17)

    Βήμα 1: δίνονται οι αρχικές τιμές. Η είσοδος ικανοποιεί την προσυνθήκη, επειδή 17≥017 \geq 0 και 5>05 > 0.

  2. (q,r)=(1,12)(q, r) = (1, 12)

    Πρώτος γύρος. Στο βήμα 2 ελέγχεται ότι 17≥517 \geq 5, οπότε εκτελείται το σώμα: το βήμα 3 αφαιρεί μια ομάδα των πέντε και το βήμα 4 τη μετρά.

  3. (q,r)=(2,7)(q, r) = (2, 7)

    Δεύτερος γύρος: 12≥512 \geq 5, και το σώμα εκτελείται ξανά.

  4. (q,r)=(3,2)(q, r) = (3, 2)

    Τρίτος γύρος: 7≥57 \geq 5, και το σώμα εκτελείται ξανά.

  5. 17=5⋅3+2,0≤2<517 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5

    Στο βήμα 2 η συνθήκη αποτυγχάνει, επειδή 2<52 < 5: ο αλγόριθμος συνεχίζει στο βήμα 5 και δίνει q=3q = 3 και r=2r = 2. Η έξοδος ικανοποιεί τη μετασυνθήκη.

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

Δύο παρατηρήσεις για τον πίνακα. Η πρώτη: ο αριθμός των γύρων είναι ίσος με το πηλίκο, 33, και το βήμα 2 εκτελέστηκε μία φορά περισσότερο από το σώμα, 44 φορές· αυτό συμβαίνει πάντα σε μια επανάληψη αυτής της μορφής, επειδή ο τελευταίος έλεγχος είναι αυτός που αποτυγχάνει. Η δεύτερη: το ίχνος δείχνει κάτι που το κείμενο του αλγορίθμου δεν λέει με την πρώτη ματιά· αν a<ba < b, για παράδειγμα a=3a = 3 και b=5b = 5, η συνθήκη αποτυγχάνει την πρώτη φορά, το σώμα δεν εκτελείται καμία φορά, και η έξοδος είναι q=0q = 0, r=3r = 3, που είναι σωστή, επειδή 3=5⋅0+33 = 5 \cdot 0 + 3. Η παράλειψη της περίπτωσης όπου η επανάληψη δεν εκτελείται είναι ένα από τα συχνότερα σφάλματα στη σχεδίαση αλγορίθμων, και το ίχνος με μικρές εισόδους την αποκαλύπτει.

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

Ακολουθία, απόφαση και επανάληψη

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

  • Ακολουθία: μια εντολή μετά από την άλλη, με τη σειρά. Τα βήματα 3 και 4 της διαίρεσης είναι μια ακολουθία: πρώτα αφαιρούμε, έπειτα μετράμε.
  • Απόφαση: ανάλογα με το αν ισχύει ή όχι μια συνθήκη, εκτελείται ένα μέρος ή ένα άλλο (ή ένα μέρος ή τίποτα). Το «Αν y>my > m, η mm παίρνει την τιμή yy» είναι μια απόφαση.
  • Επανάληψη: όσο ισχύει μια συνθήκη, εκτελείται ένα μέρος ξανά και ξανά. Το βήμα 2 της διαίρεσης, με το σώμα του, είναι μια επανάληψη.

Κάθε μορφή έχει μία μόνο είσοδο και μία μόνο έξοδο, και το εσωτερικό της μπορεί να είναι με τη σειρά του οποιαδήποτε από τις τρεις: το σώμα μιας επανάληψης μπορεί να περιέχει αποφάσεις, ένας κλάδος μιας απόφασης μπορεί να περιέχει μια επανάληψη, και ούτω καθεξής. Αν αυτό ισχύει, με τις τρεις μορφές κατασκευάζονται αλγόριθμοι οποιασδήποτε πολυπλοκότητας, όπως με λίγα κομμάτια που ταιριάζουν μεταξύ τους κατασκευάζεται οποιοδήποτε οικοδόμημα. Ότι αρκούν για να εκφραστεί κάθε αλγόριθμος είναι ένα γνωστό αποτέλεσμα της θεωρίας του προγραμματισμού (το απέδειξαν οι Κοράντο Μπεμ και Τζουζέπε Τζακοπίνι το 1966)· εδώ δεν αποδεικνύεται, αλλά όλος ο κύκλος μαθημάτων το επιβεβαιώνει: τα προγράμματα που θα γραφτούν σε αυτόν, όσο μεγάλα κι αν είναι, δεν θα χρησιμοποιούν τίποτε άλλο από αυτές τις τρεις μορφές, γραμμένες σε C++ ως if για την απόφαση και while ή for για την επανάληψη, στα μαθήματα Αποφάσεις και Βρόχοι.

Ένας χρήσιμος συμβολισμός για να βλέπουμε τη μορφή ενός αλγορίθμου είναι το διάγραμμα ροής: κάθε εντολή είναι ένα ορθογώνιο, κάθε συνθήκη ένας ρόμβος με δύο εξόδους (ικανοποιείται, που το σχήμα σημειώνει με 11, και δεν ικανοποιείται, 00), και τα βέλη λένε ποιο είναι το επόμενο βήμα. Είναι συμβολισμός, όχι σκοπός: χρησιμεύει για να δούμε έναν μικρό αλγόριθμο με μια ματιά, αλλά δεν κλιμακώνεται, και κανείς δεν γράφει ένα μεγάλο πρόγραμμα σχεδιάζοντάς το.

ΠαράδειγμαΤρεις μορφές και η σύνθεσή τους

Το σχήμα σχεδιάζει τις τρεις μορφές με γενικές εντολές AA και BB και μια συνθήκη cc, και έπειτα τις συνθέτει στο διάγραμμα της διαίρεσης με διαδοχικές αφαιρέσεις.

Απόδειξη

  1. A;BA ; B

    Ακολουθία: εκτελείται η AA και έπειτα η BB· υπάρχει μία μόνο είσοδος και μία μόνο έξοδος.

  2. c=1⇒A,c=0⇒Bc = 1 \Rightarrow A, \quad c = 0 \Rightarrow B

    Απόφαση: αν η cc ικανοποιείται, εκτελείται η AA· αλλιώς, η BB. Οι δύο κλάδοι ενώνονται σε μία μόνο έξοδο.

  3. c,A,c,A,…,cc, A, c, A, \ldots, c

    Επανάληψη: αποτιμάται η cc· αν ικανοποιείται, εκτελείται η AA και αποτιμάται ξανά η cc· αλλιώς, βγαίνουμε. Η συνθήκη αποτιμάται μία φορά περισσότερο από το σώμα.

  4. a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

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

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

Τερματίζει;

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

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

ΠαράδειγμαΗ φθίνουσα ποσότητα της διαίρεσης με αφαιρέσεις

Στη διαίρεση με διαδοχικές αφαιρέσεις, η φθίνουσα ποσότητα είναι η rr. Όσο η επανάληψη συνεχίζεται, r≥b>0r \geq b > 0, οπότε η rr είναι φυσικός. Σε κάθε γύρο, η rr παίρνει την τιμή r−br - b, και επειδή b>0b > 0 (προσυνθήκη), η νέα τιμή είναι γνησίως μικρότερη. Επομένως η επανάληψη τερματίζει, και το κάνει το πολύ μετά από aa γύρους (στην πραγματικότητα, ακριβώς μετά από qq γύρους, όσο το πηλίκο).

Παρατηρήστε πού χρησιμοποιήθηκε η προσυνθήκη b>0b > 0. Αν ο αλγόριθμος εκτελεστεί με b=0b = 0, το βήμα 3 αφήνει την rr ίδια, η συνθήκη r≥0r \geq 0 ικανοποιείται πάντα και η επανάληψη δεν τερματίζει ποτέ: ο αλγόριθμος δεν είναι λάθος, αλλά του δόθηκε μια είσοδος που η σύμβαση απέκλειε. Και αν ο bb ήταν αρνητικός, η rr θα αυξανόταν σε κάθε γύρο. Η προσυνθήκη δεν είναι στολίδι: είναι ακριβώς αυτό που χρειάζεται για να λειτουργήσει ο συλλογισμός.

Οι δύο συνθήκες της φθίνουσας ποσότητας είναι αναγκαίες, και είναι εύκολο να κάνει κανείς λάθος με οποιαδήποτε από αυτές. Ας θεωρήσουμε αυτή τη διαδικασία, που επιδιώκει να αποφασίσει αν ένας φυσικός nn είναι άρτιος: «όσο n≠0n \neq 0, ο nn παίρνει την τιμή n−2n - 2· αν φτάσουμε στο μηδέν, ο nn ήταν άρτιος». Η ποσότητα nn μειώνεται σε κάθε γύρο, και παρ’ όλα αυτά η διαδικασία δεν τερματίζει αν ο nn είναι περιττός: με n=5n = 5 περνά από τα 33, 11, −1-1, −3-3, και η συνθήκη n≠0n \neq 0 δεν αποτυγχάνει ποτέ. Αυτό που δεν ικανοποιείται είναι η άλλη συνθήκη: ο nn παύει να είναι φυσικός, επειδή η συνθήκη της επανάληψης δεν τον εμποδίζει να κατέβει κάτω από το μηδέν. Η διόρθωση είναι να επαναλαμβάνουμε όσο n≥2n \geq 2 και να αποφασίζουμε στο τέλος ανάλογα με την τιμή που μένει, 00 ή 11· τώρα ο nn είναι φυσικός σε κάθε γύρο, επειδή αφαιρούμε μόνο όταν n≥2n \geq 2, και μειώνεται: η διαδικασία τερματίζει.

Το να αποφασίσει κανείς αν μια επανάληψη τερματίζει δεν είναι πάντα εύκολο. Ένα διάσημο παράδειγμα: ξεκινώντας από έναν φυσικό n≥1n \geq 1, όσο n≠1n \neq 1, αν ο nn είναι άρτιος διαιρείται διά δύο, και αν είναι περιττός αντικαθίσταται από τον 3n+13n + 1. Με n=6n = 6 η ακολουθία είναι 6,3,10,5,16,8,4,2,16, 3, 10, 5, 16, 8, 4, 2, 1, και τερματίζει. Κανείς δεν έχει βρει έναν nn για τον οποίο να μην τερματίζει, και έχει ελεγχθεί με υπολογιστές για τεράστιες ποσότητες τιμών· κανείς όμως δεν έχει καταφέρει να αποδείξει ότι τερματίζει πάντα: είναι η εικασία του Κόλατζ, ένα ανοιχτό πρόβλημα των μαθηματικών. Καμία γνωστή ποσότητα δεν μειώνεται σε κάθε γύρο. Το δίδαγμα για όποιον προγραμματίζει είναι μετριοπαθές και σταθερό: ένας αλγόριθμος του οποίου τον τερματισμό δεν ξέρουμε να αιτιολογήσουμε δεν έχει τελειώσει.

Συχνά σφάλματα

  • Ασαφή βήματα. «Επανάλαβε αρκετές φορές», «ώσπου να είναι εντάξει», «πάρε έναν κατάλληλο αριθμό». Κάθε βήμα πρέπει να μπορεί να εκτελεστεί χωρίς να γίνει κατανοητό το πρόβλημα· αλλιώς, είναι κακογραμμένο.
  • Παράλειψη της περίπτωσης όπου η επανάληψη δεν εκτελείται. Κάθε επανάληψη με τη συνθήκη στην αρχή μπορεί να εκτελέσει το σώμα της μηδέν φορές. Πρέπει πάντα να αναρωτιόμαστε τι δίνει ο αλγόριθμος σε αυτή την περίπτωση, και το ίχνος με μια ελάχιστη είσοδο το απαντά.
  • Προδιαγραφή με ένα παράδειγμα. Το «για 17 και 5 δίνει 3 και 2» δεν είναι προδιαγραφή· η σχέση γράφεται ως γενική συνθήκη, και το παράδειγμα τη φωτίζει.
  • Σύγχυση του αλγορίθμου με το πρόγραμμά του. Ένα πρόγραμμα που αποτυγχάνει μπορεί να έχει λάθος τον αλγόριθμο ή λάθος τη γραφή του. Όποιος δεν έγραψε πρώτα τον αλγόριθμο δεν ξέρει ποιο από τα δύο να αναζητήσει.
  • Ο τερματισμός θεωρείται δεδομένος. Δεν αρκεί να μειώνεται μια ποσότητα: πρέπει επιπλέον να είναι φυσικός αριθμός όσο συνεχίζεται η επανάληψη.

Λυμένα προβλήματα

Λυμένο πρόβλημα 1Ο μεγαλύτερος από τρεις αριθμούς, με ισοβαθμίες

Να γραφτεί ένας αλγόριθμος που ικανοποιεί την προδιαγραφή του μεγίστου τριών αριθμών της πρώτης παραγράφου, και να εκτελεστεί με το χέρι για τις εισόδους (7,2,5)(7, 2, 5) και (4,9,9)(4, 9, 9).

Λύση

  1. m=xm = x

    Ιδέα: διατρέχουμε την είσοδο κρατώντας τον μεγαλύτερο που έχουμε δει ως τώρα σε μια μεταβλητή mm. Πρώτο βήμα: η mm παίρνει την τιμή xx. Μετά από αυτό, η mm είναι το μέγιστο των δεδομένων που έχουμε δει, που είναι μόνο το xx.

  2. m=max⁡(x,y,z)m = \max(x, y, z)

    Δεύτερο βήμα: αν y>my > m, η mm παίρνει την τιμή yy. Τρίτο βήμα: αν z>mz > m, η mm παίρνει την τιμή zz. Τέταρτο βήμα: δώσε ως αποτέλεσμα την mm. Είναι τρεις εντολές σε ακολουθία, οι δύο από αυτές αποφάσεις χωρίς εναλλακτικό κλάδο.

  3. (x,y,z)=(7,2,5)⇒m=7(x, y, z) = (7, 2, 5) \Rightarrow m = 7

    Ίχνος για (7,2,5)(7, 2, 5): μετά το πρώτο βήμα m=7m = 7· στο δεύτερο, το 2>72 > 7 είναι ψευδές και η mm δεν αλλάζει· στο τρίτο, το 5>75 > 7 είναι ψευδές και η mm δεν αλλάζει. Δίνεται το 77.

  4. (x,y,z)=(4,9,9)⇒m=9(x, y, z) = (4, 9, 9) \Rightarrow m = 9

    Ίχνος για (4,9,9)(4, 9, 9): μετά το πρώτο βήμα m=4m = 4· στο δεύτερο, 9>49 > 4 και η mm παίρνει την τιμή 99· στο τρίτο, το 9>99 > 9 είναι ψευδές και η mm δεν αλλάζει. Δίνεται το 99, που είναι σωστό: η ισοβαθμία δεν χρειάζεται ιδιαίτερο χειρισμό.

  5. m≥x,m≥y,m≥zm \geq x, \quad m \geq y, \quad m \geq z

    Αιτιολόγηση: μετά από κάθε βήμα, η mm είναι ένα από τα δεδομένα που έχουμε δει και κανένα από αυτά δεν την ξεπερνά. Ισχύει μετά το πρώτο, και κάθε απόφαση το διατηρεί: αν το νέο δεδομένο είναι μεγαλύτερο, γίνεται η νέα mm· αλλιώς, δεν ξεπερνά την mm. Στο τέλος έχουμε δει και τα τρία, και η mm ικανοποιεί τη μετασυνθήκη.

  6. (x,y,z)=(4,9,9)⇒p∈{2,3}(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}

    Αν είχε γραφτεί y≥my \geq m αντί για y>my > m, το αποτέλεσμα θα ήταν το ίδιο, επειδή σε περίπτωση ισοβαθμίας εκχωρείται ίση τιμή. Η επιλογή ανάμεσα σε >> και ≥\geq θα είχε σημασία αν ζητούνταν επιπλέον η θέση του μεγίστου: με >> δίνεται η πρώτη από τις ισοβαθμούσες θέσεις, και με ≥\geq η τελευταία, που ο τύπος ονομάζει pp.

Λυμένο πρόβλημα 2Το δίσεκτο έτος, διορθωμένο με ένα αντιπαράδειγμα

Στο γρηγοριανό ημερολόγιο, ένα έτος είναι δίσεκτο αν διαιρείται με το 44, εκτός από όσα διαιρούνται με το 100100, που είναι δίσεκτα μόνο αν διαιρούνται επιπλέον με το 400400. Ένας φοιτητής προτείνει τον αλγόριθμο «αν το έτος διαιρείται με το 44, δώσε ναι· αλλιώς, δώσε όχι». Να βρεθεί ένα έτος στο οποίο αποτυγχάνει και να γραφτεί ένας σωστός αλγόριθμος, με την προδιαγραφή του.

Λύση

  1. (4∣n∧¬(100∣n))∨400∣n(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n

    Προδιαγραφή. Είσοδος: ένας ακέραιος n≥1583n \geq 1583 (το γρηγοριανό ημερολόγιο ισχύει από τον Οκτώβριο του 1582). Έξοδος: ναι ή όχι. Σχέση: η έξοδος είναι ναι ακριβώς όταν ο nn διαιρείται με το 44 και όχι με το 100100, ή διαιρείται με το 400400.

  2. 1900=4⋅475,1900=400⋅4+3001900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300

    Ο προτεινόμενος αλγόριθμος πετυχαίνει στα περισσότερα έτη, και γι’ αυτό φαίνεται σωστός. Για να ανασκευαστεί αρκεί ένα έτος που διαιρείται με το 100100 και όχι με το 400400: το 19001900 διαιρείται με το 44, και ο αλγόριθμος λέει ναι· το 19001900 όμως δεν ήταν δίσεκτο.

  3. 400∣n,100∣n,4∣n400 \mid n, \quad 100 \mid n, \quad 4 \mid n

    Διορθωμένος αλγόριθμος, σε τρεις αλυσιδωτές αποφάσεις. Βήμα 1: αν ο nn διαιρείται με το 400400, δώσε ναι και τερμάτισε. Βήμα 2: αν ο nn διαιρείται με το 100100, δώσε όχι και τερμάτισε. Βήμα 3: αν ο nn διαιρείται με το 44, δώσε ναι· αλλιώς, δώσε όχι.

  4. 2000,1900,2024,20232000, \quad 1900, \quad 2024, \quad 2023

    Η σειρά των ερωτήσεων είναι ουσιώδης: πηγαίνουν από τον πιο ειδικό κανόνα στον πιο γενικό. Αν ρωτούσαμε πρώτα για το 44, το έτος 19001900 θα έπαιρνε ναι πριν φτάσει στην εξαίρεση. Ίχνος για τέσσερα έτη, ένα από κάθε περίπτωση: 20002000 (βήμα 1: ναι), 19001900 (βήμα 2: όχι), 20242024 (βήμα 3: ναι), 20232023 (βήμα 3: όχι).

  5. 4∣1900∧¬(400∣1900)4 \mid 1900 \wedge \neg (400 \mid 1900)

    Το δίδαγμα δεν αφορά μόνο τα ημερολόγια: ένας αλγόριθμος ανασκευάζεται με ένα μόνο αντιπαράδειγμα, και τα αντιπαραδείγματα αναζητούνται στα όρια των κανόνων, όχι στις συνηθισμένες περιπτώσεις. Οι δοκιμές με 20242024, 20202020 και 20162016 δεν θα είχαν αποκαλύψει τίποτα.

Λυμένο πρόβλημα 3Πόσους γύρους κάνει η διαίρεση με αφαιρέσεις

Να εκτελεστεί με το χέρι η διαίρεση με διαδοχικές αφαιρέσεις με a=20a = 20 και b=5b = 5, και με a=0a = 0 και b=7b = 7. Έπειτα, να αιτιολογηθεί ότι για κάθε αποδεκτή είσοδο ο αλγόριθμος τερματίζει μετά από ακριβώς qq γύρους και ότι η έξοδός του ικανοποιεί τη μετασυνθήκη.

Λύση

  1. 20=5⋅4+020 = 5 \cdot 4 + 0

    Ίχνος με a=20a = 20, b=5b = 5: η rr περνά από τα 2020, 1515, 1010, 55, 00, και η qq από τα 00, 11, 22, 33, 44. Ο πέμπτος έλεγχος, 0≥50 \geq 5, αποτυγχάνει. Έξοδος: q=4q = 4, r=0r = 0. Εδώ η οριακή περίπτωση είναι η ακριβής διαίρεση: ο τέταρτος γύρος γίνεται επειδή 5≥55 \geq 5, και γι’ αυτό η συνθήκη πρέπει να είναι ≥\geq και όχι >>.

  2. 0=7⋅0+00 = 7 \cdot 0 + 0

    Ίχνος με a=0a = 0, b=7b = 7: ο πρώτος έλεγχος, 0≥70 \geq 7, αποτυγχάνει· το σώμα δεν εκτελείται καμία φορά. Έξοδος: q=0q = 0, r=0r = 0, που είναι σωστή.

  3. b⋅(q+1)+(r−b)=b⋅q+r=a\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}

    Μια σχέση που διατηρείται. Πριν από τον πρώτο γύρο, b⋅q+r=b⋅0+a=ab \cdot q + r = b \cdot 0 + a = a. Σε κάθε γύρο η rr μειώνεται κατά bb και η qq αυξάνεται κατά 11, οπότε η ποσότητα b⋅q+rb \cdot q + r δεν αλλάζει. Επομένως η ισότητα ισχύει μετά από κάθε γύρο.

  4. r0>r1>r2>⋯≥0r_0 > r_1 > r_2 > \cdots \geq 0

    Τερματισμός. Όσο συνεχίζεται η επανάληψη, r≥b>0r \geq b > 0, και η rr είναι φυσικός· σε κάθε γύρο μειώνεται κατά b≥1b \geq 1. Μια γνησίως φθίνουσα ακολουθία φυσικών είναι πεπερασμένη: η επανάληψη τερματίζει.

  5. a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

    Στο τέλος, η συνθήκη απέτυχε: r<br < b. Επιπλέον r≥0r \geq 0, επειδή αφαιρείται ο bb μόνο όταν r≥br \geq b. Μαζί με τη σχέση που διατηρείται, η έξοδος ικανοποιεί τη μετασυνθήκη· και επειδή η qq μετρά τους γύρους, ο αριθμός των γύρων είναι το πηλίκο.

Ασκήσεις στο διαδίκτυο

Άσκηση 1Μέτρηση των γύρων

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

  1. Ο nn παίρνει την τιμή 2929, και ο kk παίρνει την τιμή 00.
  2. Όσο ισχύει n>1n > 1, επανάλαβε τα βήματα 3 και 4· όταν πάψει να ισχύει, συνέχισε στο βήμα 5.
  3. Αν ο nn είναι άρτιος, ο nn παίρνει την τιμή n/2n / 2· αν είναι περιττός, ο nn παίρνει την τιμή n+1n + 1.
  4. Ο kk παίρνει την τιμή k+1k + 1· επίστρεψε στο βήμα 2.
  5. Δώσε ως αποτέλεσμα τον kk.

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

Υπόδειξη

Φτιάξε τον πίνακα: ο nn περνά από το 2929 στο 3030 στον πρώτο γύρο. Μέτρα έναν γύρο για κάθε αλλαγή του nn, ώσπου ο nn να γίνει 11.

Άσκηση 2Η συνθήκη που λείπει

Ο παρακάτω αλγόριθμος, γραμμένος στη σύντομη μορφή, πρέπει να υπολογίζει το πηλίκο και το υπόλοιπο της διαίρεσης με διαδοχικές αφαιρέσεις, αλλά του λείπει η συνθήκη της επανάληψης. Να αντικατασταθεί η γραμμή με τις κάτω παύλες από τη σωστή συνθήκη, χωρίς να αλλάξει τίποτε άλλο.

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

Υπόδειξη

Εκτέλεσε με το χέρι τον αλγόριθμο με a=10a = 10 και b=5b = 5: ο δεύτερος γύρος πρέπει να γίνει, παρότι το υπόλοιπο είναι ακριβώς 55.

Προτεινόμενα προβλήματα

Κάθε πρόβλημα έχει μια υπόδειξη, που καλό είναι να ανοίγεται μόνο αφού επιχειρηθεί η λύση, και μια απάντηση, που εμφανίζεται αφού ανοιχτεί η υπόδειξη.

Προτεινόμενο πρόβλημα 1Προδιαγραφή της διάταξης τριών αριθμών

Να γραφτεί η προδιαγραφή του προβλήματος «να διαταχθούν τρεις αριθμοί» (είσοδος, έξοδος και σχέση) και να επισημανθεί ποιες αποφάσεις υποχρεώνει να ληφθούν, που η διατύπωση δεν έπαιρνε. Έπειτα, να ελεγχθεί ότι η προδιαγραφή απορρίπτει αυτές τις δύο εξόδους για την είσοδο (5,2,5)(5, 2, 5): (2,5,6)(2, 5, 6) και (2,5,5,5)(2, 5, 5, 5), και ότι δέχεται την (2,5,5)(2, 5, 5).

Υπόδειξη

Μια «διατεταγμένη» έξοδος μπορεί να μην έχει καμία σχέση με την είσοδο. Ποια συνθήκη συνδέει τους αριθμούς της εξόδου με εκείνους της εισόδου, μαζί με τους επαναλαμβανόμενους; Αύξουσα ή φθίνουσα; Γνήσια ή όχι;

Απάντηση

Είσοδος: τρεις αριθμοί xx, yy, zz. Έξοδος: τρεις αριθμοί uu, vv, ww. Σχέση: u≤v≤wu \leq v \leq w, και η (u,v,w)(u, v, w) είναι αναδιάταξη της (x,y,z)(x, y, z), δηλαδή περιέχει τις ίδιες τιμές με τις ίδιες επαναλήψεις. Αποφάσεις που η διατύπωση δεν έπαιρνε: η φορά (εδώ, από τον μικρότερο στον μεγαλύτερο)· ότι η διάταξη δεν είναι γνήσια (≤\leq και όχι <<, επειδή με επαναλαμβανόμενες τιμές η γνήσια διάταξη είναι αδύνατη)· και ότι η έξοδος πρέπει να είναι αναδιάταξη. Η (2,5,6)(2, 5, 6) είναι διατεταγμένη αλλά περιέχει ένα 66 που δεν υπήρχε· η (2,5,5,5)(2, 5, 5, 5) έχει τέσσερις τιμές· η (2,5,5)(2, 5, 5) ικανοποιεί και τις δύο συνθήκες. Χωρίς τη συνθήκη της αναδιάταξης, η (0,0,0)(0, 0, 0) θα ήταν σωστή έξοδος για οποιαδήποτε είσοδο.

Προτεινόμενο πρόβλημα 2Τα ψηφία ενός αριθμού, από δεξιά προς τα αριστερά

Να γραφτεί ένας αλγόριθμος σε αριθμημένα βήματα που δέχεται έναν φυσικό nn και δίνει τα ψηφία του από το τελευταίο ως το πρώτο (για το 40724072, δίνει 22, 77, 00, 44), χρησιμοποιώντας μόνο το πηλίκο και το υπόλοιπο της διαίρεσης με το 1010. Να εκτελεστεί με το χέρι για το 40724072 και για το 00, και να αιτιολογηθεί ότι τερματίζει για κάθε nn.

Υπόδειξη

Το υπόλοιπο της διαίρεσης με το 1010 είναι το τελευταίο ψηφίο, και το πηλίκο είναι ο αριθμός χωρίς αυτό. Αποφάσισε αν η συνθήκη ελέγχεται πριν ή μετά από την απόδοση ενός ψηφίου, και δες τι συμβαίνει με n=0n = 0, που έχει ένα ψηφίο.

Απάντηση

Ένας σωστός αλγόριθμος: (1) δώσε το υπόλοιπο της διαίρεσης του nn με το 1010· (2) ο nn παίρνει την τιμή του πηλίκου της διαίρεσης του nn με το 1010· (3) αν n>0n > 0, επίστρεψε στο βήμα 1· αλλιώς, τερμάτισε. Η ερώτηση μπαίνει μετά από το σώμα, οπότε το σώμα εκτελείται τουλάχιστον μία φορά: για n=0n = 0 δίνει 00, που είναι το μοναδικό του ψηφίο. Αν η ερώτηση γινόταν στην αρχή («όσο n>0n > 0»), για n=0n = 0 δεν θα δινόταν τίποτα· είναι το σφάλμα της παράλειψης της περίπτωσης όπου η επανάληψη δεν εκτελείται. Ίχνος για το 40724072: δίνονται τα 22, 77, 00, 44, και ο nn περνά από τα 407407, 4040, 44, 00. Τερματισμός: η φθίνουσα ποσότητα είναι ο nn, ένας φυσικός· αν επιστρέφουμε στο βήμα 1 είναι επειδή n>0n > 0, και για n≥1n \geq 1 το πηλίκο διά 1010 είναι γνησίως μικρότερο από τον nn, οπότε ο nn μειώνεται γνησίως σε κάθε γύρο.

Προτεινόμενο πρόβλημα 3Τα ρέστα σε κέρματα

Διαθέτουμε κέρματα των 5050, 1010 και 11 μονάδων, σε απεριόριστη ποσότητα. Προδιαγραφή: είσοδος, ένας φυσικός mm· έξοδος, τρεις φυσικοί c50c_{50}, c10c_{10}, c1c_1 με 50c50+10c10+c1=m50 c_{50} + 10 c_{10} + c_1 = m και τον μικρότερο δυνατό αριθμό κερμάτων, c50+c10+c1c_{50} + c_{10} + c_1. Κάποιος προτείνει τον παρακάτω αλγόριθμο. Να βρεθεί μια είσοδος στην οποία αποτυγχάνει, να εξηγηθεί κάθε ελάττωμα και να διορθωθεί.

  1. Οι c50c_{50}, c10c_{10} και c1c_1 παίρνουν την τιμή 00.
  2. Αν m≥50m \geq 50, ο c50c_{50} παίρνει την τιμή c50+1c_{50} + 1 και ο mm παίρνει την τιμή m−50m - 50.
  3. Όσο m>10m > 10: ο c10c_{10} παίρνει την τιμή c10+1c_{10} + 1 και ο mm παίρνει την τιμή m−10m - 10.
  4. Όσο m>0m > 0: ο c1c_1 παίρνει την τιμή c1+1c_1 + 1 και ο mm παίρνει την τιμή m−1m - 1.
  5. Δώσε ως αποτέλεσμα τους c50c_{50}, c10c_{10} και c1c_1.
Υπόδειξη

Το άθροισμα των κερμάτων είναι πάντα mm· αυτό που μπορεί να αποτύχει είναι το πλήθος τους. Δοκίμασε ένα ακριβές πολλαπλάσιο του 1010 και ένα ποσό μεγαλύτερο από 100100, και αναρωτήσου ποιον τρόπο συνδυασμού βημάτων χρησιμοποιεί το βήμα 2 και ποιον θα έπρεπε να χρησιμοποιεί.

Απάντηση

Υπάρχουν δύο ελαττώματα. Πρώτον, το βήμα 3 χρησιμοποιεί m>10m > 10: με m=10m = 10 δεν δίνει κανένα κέρμα των 1010 και δίνει δέκα των 11, αντί για ένα. Δεύτερον, το βήμα 2 είναι απόφαση εκεί όπου χρειάζεται επανάληψη: με m=120m = 120, ο αλγόριθμος όπως είναι γραμμένος δίνει ένα κέρμα των 5050, έξι των 1010 και δέκα των 11 (δεκαεπτά κέρματα), και ακόμη και με το βήμα 3 διορθωμένο θα έδινε ένα των 5050 και επτά των 1010 (οκτώ), αντί για δύο των 5050 και δύο των 1010 (τέσσερα). Η είσοδος m=100m = 100 δείχνει και τα δύο ελαττώματα: ο αλγόριθμος δίνει ένα των 5050, τέσσερα των 1010 και δέκα των 11, δεκαπέντε κέρματα, αντί για δύο. Διόρθωση: βήμα 2, «όσο m≥50m \geq 50, …»· βήμα 3, «όσο m≥10m \geq 10, …». Έτσι διορθωμένος, ο αλγόριθμος παίρνει πάντα το μεγαλύτερο κέρμα που χωρά, και με αυτά τα τρία κέρματα αυτό δίνει το μικρότερο πλήθος: το ψηφίο των μονάδων του mm μπορεί να πληρωθεί μόνο με κέρματα του 11, και από ό,τι μένει συμφέρει να πληρωθεί με κέρματα των 5050 όσο το δυνατόν περισσότερο, επειδή πέντε των 1010 αξίζουν όσο ένα των 5050. Με άλλα κέρματα, για παράδειγμα των 11, 33 και 44 για m=6m = 6, η επιλογή πάντα του μεγαλύτερου δεν δίνει πια το ελάχιστο (4+1+14 + 1 + 1 έναντι 3+33 + 3).