2.4.5 Δομή Επανάληψης

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

Παράδειγμα 7. Εκτύπωση διαδοχικών αριθμών με επαναληπτική εντολή: όσο…επανάλαβε Να γραφεί αλγόριθμος που να εμφανίζει τους αριθμούς από 1 έως

Στον αλγόριθμο αυτό επιζητείται η παρουσίαση μίας σειράς αριθμών. Αν οι αριθμοί αυτοί ήσαν λίγοι, τότε αυτό θα μπορούσε να γίνει με την παράθεση αντίστοιχων εντολών εμφάνισης. Το ίδιο θα συμβεί και στην περίπτωση που οι αριθμοί είναι περισσότεροι, αλλά δεν έχουν καμία σχέση μεταξύ τους π.χ. 5, 207, -32 κοκ. Όμως στο ζητούμενο αλγόριθμο παρατηρούμε ότι κάθε αριθμός παράγεται από τον προηγούμενό του με απλό τρόπο δηλαδή προσθέτοντας κάθε φορά το 1. Μπορεί λοιπόν να χρησιμοποιηθεί μια μεταβλητή, έστω i, η οποία αρχίζει από το 1 και καταλήγει στο 100 αυξανόμενη κατά 1. Η εκάστοτε αύξηση της μεταβλητής αυτής μπορεί να γίνει με τη χρήση της εντολής εκχώρησης i

i

Η αρχική τιμή της μεταβλητής i ορίζεται εύκολα με την εντολή i Το ζητούμενο είναι να εκτελεστεί 100 φορές η εντολή i Αυτό επιτυγχάνεται με τη χρήση της εντολής Όσο …επανάλαβε. Η σύνταξη της εντολής αυτής είναι: Όσο συνθήκη επανάλαβε εντολές Τέλος_επανάληψης

Η λειτουργία της εντολής είναι η εξής: Επαναλαμβάνεται η εκτέλεση των εντολών, όσο η συνθήκη είναι αληθής. Όταν η συνθήκη γίνει ψευδής, τότε ο αλγόριθμος συνεχίζεται με την εντολή που ακολουθεί το 'Τέλος_επανάληψης'. Με την εισαγωγή της εντολής αυτής η σχεδίαση του ζητούμενου αλγορίθμου είναι: Αλγόριθμος Παράδειγμα_7 i Όσο i 100 επανάλαβε Εμφάνισε i i Τέλος_επανάληψης Τέλος Παράδειγμα_7

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

Παράδειγμα 8: Επαναληπτική είσοδος στοιχείων Να γραφεί αλγόριθμος που να διαβάζει ένα άγνωστο πλήθος αριθμών και να εμφανίζει τον κάθε αριθμό.

Το πρόβλημα αυτό παρουσιάζει την εξής ιδιομορφία: ενώ φαίνεται ότι θα χρησιμοποιηθεί για τη λύση του κάποια επαναληπτική διαδικασία, δεν προσδιορίζεται ο τρόπος τερματισμού της. Κατ' αρχήν, λοιπόν, ας εξετάσουμε τον αλγόριθμο που εκτελεί ένας άνθρωπος, όταν αντιγράφει κάποιους αριθμούς, όπως για παράδειγμα όταν συγκεντρώνονται τα έξοδα από διάφορους λογαριασμούς. Ο αλγόριθμος αυτός είναι: Βήμα 1. Διάβασε έναν αριθμό Βήμα 2. Γράψε τον αριθμό Βήμα 3. Επανάλαβε τη διαδικασία από το βήμα 1.

Ο αλγόριθμος αυτός έχει μια ατέλεια, δεν διαθέτει τρόπο τερματισμού (ατέρμων βρόχος). Η έλλειψη αυτή είναι φυσική, εφ' όσον ο αλγόριθμος εκτελείται από έναν άνθρωπο. Αυτός θα σταματήσει να γράφει, όταν δεν υπάρχουν πλέον άλλοι αριθμοί. Ωστόσο είναι δυνατόν να διορθωθεί αυτή η ατέλεια, αν το βήμα 3 λάβει την εξής μορφή: Βήμα 3. Αν υπάρχουν άλλοι αριθμοί, επανάλαβε τη διαδικασία από το βήμα 1, αλλιώς σταμάτησε.

Ο αλγόριθμος τώρα είναι σωστός και μπορεί να εκτελεστεί και από μία μηχανή. Όμως έχει ένα άλλο μειονέκτημα: ο τερματισμός γίνεται μέσα από την εντολή Αν … τότε … αλλιώς …, πράγμα που δεν συνιστάται και πρέπει να αποφεύγεται, γιατί εύκολα μπορεί να χάσει ο προγραμματιστής τον έλεγχο της ροής του προγράμματος και να οδηγηθεί σε λάθος. Για την άρση του μειονεκτήματος αυτού πρέπει να χρησιμοποιηθεί μία εντολή επαναληπτικής διαδικασίας, όπως η εντολή Όσο…επανάλαβε. Ο τελικός αλγόριθμος είναι ο εξής: Αλγόριθμος Παράδειγμα_8 Διάβασε x. Όσο x > 0 επανάλαβε Εμφάνισε x Διάβασε x Τέλος_επανάληψης Τέλος Παράδειγμα_8

Ο βρόχος επανάληψης μπορεί να μην εκτελεσθεί καμία φορά, αν η πρώτη τιμή που διαβάζεται είναι αρνητική

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

Παράδειγμα 9. Εκτύπωση θετικών αριθμών με εντολή: αρχή_επανάληψης…μέχρις_ότου Να διαβάζονται και να εκτυπώνονται όσοι θετικοί αριθμοί δίνονται από το πληκτρολόγιο. Ο αλγόριθμος τελειώνει, όταν δοθεί ένας αρνητικός αριθμός. Αλγόριθμος Παράδειγμα_9 Αρχή_επανάληψης Διάβασε x

Eμφάνισε x Μέχρις_ότου x < 0 Τέλος Παράδειγμα_9

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

Η εντολή Αρχή_επανάληψης…Μέχρις_ότου εκτελείται οπωσδήποτε μια φορά

Παράδειγμα 10. Υπολογισμός αθροίσματος αριθμών με επαναληπτική εντολή: για…από…μέχρι Να βρεθεί και να εκτυπωθεί το άθροισμα των 100 ακεραίων από το 1 μέχρι το 100.

Όταν ο αριθμός των φορών που θα εκτελεστεί μια επαναληπτική διαδικασία είναι γνωστός εκ των προτέρων, τότε είναι προτιμότερο να χρησιμοποιείται η εντολή Για…από…μέχρι. Έτσι ο ζητούμενος αλγόριθμος είναι.

Αλγόριθμος Παράδειγμα_10 Sum 0 Για i από 1 μέχρι 100 Sum Τέλος_επανάληψης Eκτύπωσε Sum Τέλος Παράδειγμα_10

Όπως γίνεται φανερό, η εντολή Για…από…μέχρι περιλαμβάνει όλα τα απαιτούμενα στοιχεία για την επανάληψη, δηλαδή αρχική τιμή της μεταβλητής i (=1) και τελική τιμή (=100). Το βήμα μεταβολής της μεταβλητής i είναι 1, το οποίο υπονοείται και δεν σημειώνεται, όταν είναι 1. Η μεταβλητή Sum που υποδέχεται το άθροισμα των διαδοχικών αριθμών, πρέπει να εκκινήσει με τιμή 0, ενώ το εκάστοτε μερικό άθροισμα υπολογίζεται με την εντολή εκχώρησης εντός του βρόχου. Στο τέλος η μεταβλητή Sum θα περιέχει το τελικό άθροισμα.

Sum

Σχ. 2.6. Ο αλγόριθμος του παραδείγματος 10 με διάγραμμα ροής

Παράδειγμα 11. Υπολογισμός αθροίσματος με επαναληπτική εντολή: για…από…μέχρι…βήμα Να βρεθεί και να εκτυπωθεί το άθροισμα των άρτιων αριθμών από το 1 μέχρι το 100.

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

Αλγόριθμος Παράδειγμα_11 άθροισμα 0 Για i από 2 μέχρι 100 με_βήμα 2 άθροισμα άθροισμα + i Τέλος_επανάληψης Eκτύπωσε άθροισμα Τέλος Παράδειγμα_11

Από τα προηγούμενα δύο παραδείγματα γίνεται φανερός ο τρόπος χρήσης της εντολής Για…από…μέχρι. Ας σημειωθεί ωστόσο, ότι υπάρχουν κάποιες δεσμεύσεις μεταξύ των τιμών από, μέχρι και βήμα. Έτσι το βήμα δεν μπορεί να είναι μηδέν, γιατί τότε ο βρόχος εκτελείται έπ’ άπειρον. Είναι δυνατόν όμως το βήμα να έχει αρνητική τιμή, αρκεί η τιμή από να είναι μεγαλύτερη από την τιμή μέχρι, όπως για παράδειγμα στην επόμενη εντολή: Για k από 100 μέχρι 0 με_βήμα -1

Ο βρόχος Για k από 5 μέχρι 5 εκτελείται ακριβώς μία φορά Ο βρόχος Για k από 5 μέχρι 1 δεν εκτελείται καμία φορά

Επίσης οι τιμές από, μέχρι και βήμα δεν είναι απαραίτητο να είναι ακραίες. Μπορούν λάβουν οποιαδήποτε πραγματική τιμή. Για παράδειγμα, όταν ζητείται να βρεθούν διαδοχικές τιμές μιας συνάρτησης f(x) για x από 0 έως 1, τότε μπορεί να γραφεί η επόμενη εντολή Για x από 0 μέχρι 1 με_βήμα 0,01

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

45 x 19 405 + 45 855 Σχ. 2.7 Χειρωνακτικός τρόπος πολλαπλασιασμού.

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

Έστω, λοιπόν, ότι δίνονται δύο θετικοί ακέραιοι αριθμοί, οι αριθμοί 45 και 19. Οι αριθμοί γράφονται δίπλα-δίπλα και ο πρώτος διπλασιάζεται αγνοώντας το δεκαδικό μέρος, ενώ ο δεύτερος υποδιπλασιάζεται. Στο σχήμα 2. 8 παρουσιάζεται η επαναλαμβανόμενη διαδικασία, που συνεχίζεται μέχρις ότου στη δεύτερη στήλη να προκύψει μονάδα. Τελικώς, το γινόμενο ισούται με το άθροισμα των στοιχείων της πρώτης στήλης, όπου αντίστοιχα στη δεύτερη στήλη υπάρχει περιττός αριθμός. Για το παράδειγμά μας, τα στοιχεία αυτά παρουσιάζονται στην τρίτη στήλη.

45 19 45 90 9 90 180 4 360 2 720 1 720 Άθροισμα = 855 Σχ. 2.8. Πολλαπλασιασμός αλά ρωσικά.

Ολίσθηση (shift) Στα κυκλώματα του υπολογιστή τα δεδομένα αποθηκεύονται με δυαδική μορφή, δηλαδή 0 και 1, ανεξάρτητα από το πως τα ορίζει ο προγραμματιστής, όπως ακεραίους ή πραγματικούς σε δεκαδικό σύστημα, ή ακόμη χαρακτήρες κ.λπ. Έτσι ο αριθμός 17 του δεκαδικού συστήματος ισοδυναμεί με τον αριθμό 00010001 του δυαδικού συστήματος, ο οποίος μπορεί να αποθηκευθεί σε ένα byte. Αν μετακινήσουμε τα ψηφία αυτά κατά μία θέση προς τα αριστερά, δηλαδή αν προσθέσουμε ένα 0 στο τέλος του αριθμού και αγνοήσουμε το αρχικό 0, τότε προκύπτει ο αριθμός 00100010 του δυαδικού συστήματος, που ισοδυναμεί με το αριθμό 34 του δεκαδικού συστήματος. Επίσης, με παρόμοιο τρόπο, αν μετακινήσουμε τα ψηφία κατά μία θέση δεξιά, δηλαδή αποκόψουμε το τελευταίο ψηφίο 1 και θεωρήσουμε ένα ακόμη αρχικό 0, τότε προκύπτει ο αριθμός 00001000 του δυαδικού συστήματος, που ισοδυναμεί με τον αριθμό 8 του δεκαδικού συστήματος. Άρα η ολίσθηση προς τα αριστερά ισοδυναμεί με πολλαπλασιασμό επί δύο, ενώ η ολίσθηση προς τα δεξιά ισοδυναμεί με την ακέραια διαίρεση διά δύο.

Στοιχεία ψευδογλώσσας 1. Σταθερές Αριθμητικές: χρησιμοποιούνται οι αριθμητικοί χαρακτήρες, το +, το ­ και το κόμμα ως δεκαδικό σημείο, Αλφαριθμητικές: σχηματίζονται από οποιουσδήποτε χαρακτήρες εντός διπλών εισαγωγικών, Λογικές: υπάρχουν δύο, οι Αληθής και Ψευδής. 2. Μεταβλητές Για τη σύνθεση του ονόματος μιας μεταβλητής χρησιμοποιούνται οι αριθμητικοί χαρακτήρες, οι αλφαβητικοί χαρακτήρες πεζοί και κεφαλαίοι, καθώς και ο χαρακτήρας _ (underscore). Οι μεταβλητές μπορούν επίσης να είναι αριθμητικές, αλφαριθμητικές και λογικές. 3. Τελεστές Αριθμητικοί +, -, *, /, ^ Συγκριτικοί: ?, , ?, Λογικοί: και (σύζευξη), ή (διάζευξη), όχι (άρνηση). 4. Εκφράσεις Σχηματίζονται από σταθερές, μεταβλητές, συναρτήσεις, τελεστές και παρενθέσεις. 5. Εντολή εκχώρησης Μεταβλητή έκφραση 6. Σχήματα λογικών υποθέσεων Αν τότε Αν τότε Αν τότε αλλιώς αλλιώς_αν τότε Τέλος_αν …… Επίλεξε έκφραση αλλιώς_αν τότε Περίπτωση 1 Διαδικασία_1 αλλιώς ………… Περίπτωση ν Τέλος_αν Διαδικασία _ν Περίπτωση αλλιώς Διαδικασία _αλλιώς Τέλος_επιλογών

όπου ως διαδικασία λαμβάνεται ένα σύνολο εντολών 7. Επαναληπτικές διαδικασίες - Επαναληπτικό σχήμα με έλεγχο επανάληψης στην αρχή Όσο επανάλαβε Διαδικασία Τέλος_επανάληψης - Επαναληπτικό σχήμα με έλεγχο επανάληψης στο τέλος Αρχή_επανάληψης Διαδικασία Μέχρις_ότου

- Επαναληπτικό σχήμα ορισμένων φορών επανάληψης Για μεταβλητή από τ1 μέχρι τ2 με_βήμα β Διαδικασία Τέλος_επανάληψης 8. Ρήματα σε προστακτική Για παράδειγμα, "Διάβασε", "Γράψε", "Εκτέλεσε" κ.λπ. 9. Ουσιαστικά Σε ορισμένες περιπτώσεις όταν οι ζητούμενες ενέργειες είναι πολλές ή προφανείς, καθορίζονται με τη χρήση ουσιαστικών αντί ρημάτων, ό πως "εισαγωγή δεδομένων", "εμφάνιση πεδίων στην οθόνη" κ.λπ. 10. Σχόλια Προκειμένου να διαχωρίζονται οι επεξηγηματικές φράσεις από τις λέξεις-κλειδιά του αλγορίθμου, στις πρώτες προτάσσεται το σύμβολο !, για παράδειγμα ! Σχόλια. 11. Πρώτη και τελευταία γραμμή ενός αλγορίθμου είναι αντίστοιχα Αλγόριθμος και Τέλος 12. Δεδομένα και αποτελέσματα Τα δεδομένα εισόδου (αν υπάρχουν) περιγράφονται στη δεύτερη γραμμή του αλγορίθμου εντός των συμβόλων // … //. Αντίστοιχα τα αποτελέσματα εξόδου δίνονται στην προτελευταία γραμμή του αλγορίθμου εντός των συμβόλων // … //.

Η μέθοδος αυτή χρησιμοποιείται πρακτικά στους υπολογιστές, γιατί υλοποιείται πολύ πιο απλά απ' ότι ο γνωστός μας χειρωνακτικός τρόπος πολλαπλασιασμού. Πιο συγκεκριμένα, απαιτεί πολλαπλασιασμό επί δύο, διαίρεση διά δύο και πρόσθεση. Σε αντίθεση η γνωστή μας διαδικασία πολλαπλασιασμού απαιτεί πολλαπλασιασμό με οποιοδήποτε ακέραιο και πρόσθεση. Σε επίπεδο, λοιπόν, κυκλωμάτων υπολογιστή ο πολλαπλασιασμός επί δύο και η διαίρεση διά δύο μπορούν να υλοποιηθούν ταχύτατα με μία απλή εντολή ολίσθησης (shift), σε αντίθεση με τον πολλαπλασιασμό με οποιοδήποτε ακέραιο που θεωρείται πιο χρονοβόρα διαδικασία. Το τελευταίο γεγονός είναι ο λόγος που ο πολλαπλασιασμός αλά ρωσικά είναι προτιμότερος απ' ότι ο χειρωνακτικός τρόπος πολλαπλασιασμού δύο ακεραίων.

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

Αλγόριθμος: Πολλαπλασιασμός δύο θετικών ακεραίων (αλά ρωσικά) Είσοδος: Δύο ακέραιοι M1 και M2, όπου M1, M2 1 Έξοδος: Το γινόμενο P=M1*M2 Βήμα 1 Θέσε P=0 Βήμα 2 Αν M2>0, τότε πήγαινε στο Βήμα 3, αλλιώς πήγαινε στο Βήμα 7 Βήμα 3 Αν ο Μ2 είναι περιττός, τότε θέσε P=P+M1 Βήμα 4 Θέσε Μ1=Μ1*2 Βήμα 5 Θέσε Μ2=Μ2/2 (θεώρησε μόνο το ακέραιο μέρος) Βήμα 6 Πήγαινε στο Βήμα 2 Βήμα 7 Τύπωσε τον P.

Ακολουθεί ο αλγόριθμος σε ψευδοκώδικα για το ίδιο πρόβλημα του πολλαπλασιασμού αλά ρωσικά.

Αλγόριθμος Πολλαπλασιασμός_αλά_ρωσικά Δεδομένα // Μ1,Μ2 ακέραιοι // P Όσο M2 > 0 επανάλαβε Αν M2 mod 2 = 1 τότε P M1 M2 Τέλος_επανάληψης Αποτελέσματα // P, το γινόμενο των ακεραίων Μ1,Μ2 // Τέλος Πολλαπλασιασμός_αλά_ρωσικά