2.2.1 Ορισμός αλγορίθμου
Αλγόριθμος είναι μια πεπερασμένη (= όχι άπειρη) σειρά ενεργειών (βημάτων), αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύουν στην επίλυση ενός προβλήματος.
Η έννοια του αλγορίθμου δεν συνδέεται αποκλειστικά και μόνο με προβλήματα της Πληροφορικής. Για παράδειγμα, το δέσιμο ή το πέρασμα των κορδονιών στα παπούτσια αποτελεί ένα πρόβλημα, για την επίλυση του οποίου χρειάζεται να εκτελεστεί μια πεπερασμένη σειρά ενεργειών. Η αλληλουχία των ενεργειών οδηγεί στο επιθυμητό αποτέλεσμα. Η αλληλουχία δεν είναι απαραίτητα μοναδική για την επίτευξη αυτού του, αφού, υπάρχουν και άλλοι τρόποι για το δέσιμο ή το πέρασμα των κορδονιών.
Κάθε αλγόριθμος χρειάζεται να δέχεται ένα σύνολο μεταβλητών εισόδου (που μπορεί να είναι και το κενό σύνολο), οι οποίες αποτελούν τα δεδομένα του αλγορίθμου. Η είσοδος των μεταβλητών μπορεί να επιτευχθεί με κατάλληλες εντολές, οι οποίες θα παρουσιαστούν σε επόμενες παραγράφους.
Κάθε αλγόριθμος χρειάζεται να δημιουργεί κάποιο αποτέλεσμα. Το αποτέλεσμα του αλγορίθμου, η έξοδός του, είναι μία ή περισσότερες μεταβλητές ή/και σταθερές τιμές. Η έξοδος μπορεί να επιτευχθεί με κατάλληλες εντολές, οι οποίες θα παρουσιαστούν σε επόμενες παραγράφους.
Η αναπαράσταση των αλγορίθμων μπορεί να πραγματοποιηθεί με:
- Φυσική γλώσσα όπου η αναπαράσταση γίνεται με την ομιλούμενη γλώσσα, μέσω της οποίας περιγράφονται τα βήματα επίλυσης του προβλήματος. Ωστόσο, με τη φυσική γλώσσα μπορούν να παρατηρηθούν ασάφειες στις οδηγίες.
- Ψευδοκώδικα ή ψευδογλώσσα η οποία είναι μια υποθετική γλώσσα για την αναπαράσταση αλγορίθμων με στοιχεία από κάποιες γλώσσες προγραμματισμού, παραλείποντας λεπτομέρειες που δεν είναι ουσιαστικές για την ανθρώπινη κατανόηση του αλγορίθμου.
- Διάγραμμα Ροής όπου αναπαρίσταται εποπτικά με κατάλληλα σχήματα και βέλη ο αλγόριθμος.
- Γλώσσα προγραμματισμού η οποία είναι μια τεχνητή γλώσσα, που έχει αναπτυχθεί για να δημιουργεί ή να εκφράζει προγράμματα για τον υπολογιστή. Η αναπαράσταση των αλγορίθμων με γλώσσα προγραμματισμού μπορεί να γίνει είτε με οπτικές είτε με κειμενικές γλώσσες προγραμματισμού. Στην εικόνα κάτω: υλοποίηση του αλγόριθμου της πρόσθεσης δύο ακεραίων που εισάγονται από το πληκτρολόγιο σε γλώσσα προγραμματισμού BASIC και σε γλώσσα προγραμματισμού PYTHON
Άσκηση 1(2.2.1). Διατύπωση αλγορίθμου σε φυσική γλώσσα
Να διατυπωθεί αλγόριθμος σε φυσική γλώσσα, ο οποίος να περιγράφει τα βήματα για να βράσει ένα αυγό.
2.2.7 Εντολές και δομές αλγορίθμου
Στην ενότητα αυτή δίδονται διάφορα παραδείγματα αλγορίθμων, όπου εξετάζονται τα συστατικά μέρη ενός αλγορίθμου και οι τρεις συνιστώσες του (δομή ακολουθίας, δομή επιλογής και δομή επανάληψης)
Η μελέτη τους θα γίνει κυρίως με την χρήση Ψευδοκώδικα ή ψευδογλώσσας που είναι μια υποθετική γλώσσα για την αναπαράσταση αλγορίθμων με στοιχεία από κάποιες γλώσσες προγραμματισμού, παραλείποντας λεπτομέρειες που δεν είναι ουσιαστικές για την ανθρώπινη κατανόηση του αλγορίθμου.
Κάθε αλγόριθμος διατυπωμένος σε ψευδογλώσσα ξεκινά με τη γραμμή:
Αλγόριθμος όνομα_αλγορίθμου
και τελειώνει με τη γραμμή:
Τέλος όνομα_αλγορίθμου
Μεταξύ αυτών των δύο γραμμών γράφονται οι εντολές του αλγορίθμου. Οι εντολές είναι λέξεις (συνήθως ρήματα σε προστακτική) ή συμβολισμοί που προσδιορίζουν μία σαφή ενέργεια. Οι λέξεις που έχουν αυστηρά καθορισμένο νόημα στην ψευδογλώσσα καλούνται δεσμευμένες λέξεις Οι εντολές γράφονται σε ξεχωριστές γραμμές. Επεξηγηματικά σχόλια μπορούν να γράφονται οπουδήποτε στο σώμα του αλγορίθμου. Ένα σχόλιο αρχίζει με το χαρακτήρα θαυμαστικό (!).
2.2.7.1 Εκχώρηση, Είσοδος και Έξοδος τιμών
Οι μεταβλητές δημιουργούνται σε έναν αλγόριθμο για να καταχωρούνται (να αποθηκεύονται) σε αυτές τιμές οι οποίες μπορεί και να μεταβάλλονται κατά την διάρκεια της εκτέλεσης του αλγορίθμου. Για το σχηματισμό του ονόματος μιας μεταβλητής χρησιμοποιείται οποιοσδήποτε αριθμός αλφαβητικών ή αριθμητικών χαρακτήρων και ο χαρακτήρας κάτω παύλα. Ο πρώτος χαρακτήρας της μεταβλητής πρέπει να είναι αλφαβητικός και δεν μπορεί να χρησιμοποιηθεί δεσμευμένη λέξη ως όνομα μεταβλητής.
Μια έκφραση μπορεί να είναι μια σταθερά, μια μεταβλητή, μια συνάρτηση ή ένας συνδυασμός σταθερών, μεταβλητών, συναρτήσεων, τελεστών και παρενθέσεων.
Η γενική μορφή της εντολής εκχώρησης είναι:
Μεταβλητή ← Έκφραση
και η λειτουργία της είναι «εκτελούνται οι πράξεις στην έκφραση και η τιμή της εκχωρείται (αποδίδεται, μεταβιβάζεται) στη μεταβλητή». Στην εντολή χρησιμοποιείται το αριστερό βέλος προκειμένου να δείχνει τη φορά της εκχώρησης.
Πχ. όγκος ← ύψος * πλάτος * βάθος
Η εκχώρηση τιμών επιτυγχάνεται και με τις εντολές εισόδου. Η εντολή:
Διάβασε λίστα_μεταβλητών
επιτρέπει την είσοδο τιμών και την εκχώρηση αυτών στις μεταβλητές που αναφέρονται στη λίστα_μεταβλητών.
Η εντολή Διάβασε διαφέρει από την εντολή εκχώρησης, γιατί στη δεύτερη οι τιμές των μεταβλητών προσδιορίζονται κατά τη συγγραφή του αλγορίθμου, ενώ στην πρώτη κατά την εκτέλεση του αλγορίθμου.
Πχ. Διάβασε ύψος, πλάτος, βάθος
Για την έξοδο τιμών (αποτελεσμάτων) μπορούν να χρησιμοποιηθούν οι εντολές Γράψε, Εμφάνισε ή Εκτύπωσε με ίδια σύνταξη. Κάθε μία από αυτές τις εντολές συνοδεύεται από μια λίστα μεταβλητών ή σταθερών. Π.χ. Γράψε "Τιμή:", αξία.
Η μελέτη των αλγόριθμων στο εργαστήριο με ψευδογλώσσα μπορεί να γίνει με την βοήθεια της εφαρμογής ΓΛΩΣΣΑ που μπορεί να εκτελείται σε Windows. Το περιβάλλον της εφαρμογής φαίνεται στην παρακάτω εικόνα:
Το σύνολο των χαρακτήρων που χρησιμοποιούνται στην ψευδογλώσσα περιλαμβάνει:
- όλα τα γράμματα της ελληνικής ή αγγλικής αλφαβήτου πεζά και κεφαλαία
- τους αριθμητικούς χαρακτήρες 0-9
- τους επόμενους ειδικούς χαρακτήρες
- " " εισαγωγικά (διπλά)
- ( ) παρενθέσεις
- [ ] αγκύλες
- * αστερίσκος
- + συν
- , κόμμα
- - μείον
- . τελεία
- / κάθετος
- ! θαυμαστικό
- < μικρότερο από
- = ίσον
- > μεγαλύτερο από
- ≤ μικρότερο ή ίσο
- ≥ μεγαλύτερο ή ίσο
- ≠ διάφορο
- ^ άνω βέλος
- _ κάτω παύλα
- κενό
- ← (αριστερό βέλος)
2.2.7.2 Δομή ακολουθίας
Η δομή ακολουθίας χρησιμοποιείται για την αντιμετώπιση προβλημάτων στα οποία οι εντολές εκτελούνται η μία μετά την άλλη από πάνω προς τα κάτω.
Παράδειγμα 2.8α. Είσοδος και έξοδος αριθμών
Να διαβαστούν δύο αριθμοί και να υπολογιστεί και να εμφανιστεί το άθροισμά τους.
Αλγόριθμος Άθροισμα
Διάβασε α, β
Σ ← α + β
Εμφάνισε Σ
Τέλος Άθροισμα
Η πρώτη ενέργεια που γίνεται είναι η εισαγωγή δεδομένων. Αυτό επιτυγχάνεται με τη χρήση της εντολής Διάβασε. Μετά την εκτέλεση της εντολής αυτής στις μεταβλητές α και β έχουν εκχωρηθεί τιμές, οπότε υπάρχει η δυνατότητα επεξεργασίας των τιμών. Εδώ απαιτείται η πρόσθεση των δύο αριθμών και η απόδοση του αθροίσματος σε μια άλλη μεταβλητή, τη Σ, που επιτυγχάνεται με την επόμενη εντολή εκχώρησης. Τελευταία ενέργεια αποτελεί η εμφάνιση (ή εκτύπωση) του αποτελέσματος.
Το διάγραμμα ροής που περιγράφει τον παραπάνω αλγόριθμο είναι:
Άσκηση 1(2.8α). Υπολογισμός αθροίσματος, διαφοράς, γινομένου και πηλίκου δύο αριθμών
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει δύο αριθμούς και να υπολογίζει και να εκτυπώνει το άθροισμα, την διαφορά, το γινόμενο και το πηλίκο τους.
Άσκηση 2(2.8α). Εκτύπωση ονοματεπώνυμου
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει το όνομα και το επώνυμό σας και να εκτυπώνει το ονοματεπώνυμο.
Υπόδειξη: Οι μεταβλητές που θα χρησιμοποιηθούν είναι αλφαριθμητικές και θα πρέπει να χρησιμοποιηθούν τα διπλά εισαγωγικά. Έτσι θα πρέπει να γράψουμε πχ. όνομα ← "Μαρία"
Παράδειγμα 2.8β. Είσοδος και έξοδος αριθμών
Να διαβαστούν δύο αριθμοί και να υπολογιστεί και να εμφανιστεί το άθροισμά τους.
Αλγόριθμος Άθροισμα_2
Δεδομένα // α, β //
Σ ← α + β
Αποτελέσματα // Σ //
Τέλος Άθροισμα_2
7 8
Εναλλακτική είσοδος και έξοδος τιμών παρέχεται με τη χρήση των εντολών Δεδομένα και Αποτελέσματα. Η εντολή Δεδομένα γράφεται δεύτερη (μετά την εντολή Αλγόριθμος) και περιγράφει εντός των συμβόλων // .... // τα δεδομένα του αλγορίθμου, δηλαδή τις μεταβλητές που έχουν ήδη κάποια τιμή. Αντίστοιχα η εντολή Αποτελέσματα γράφεται προτελευταία και περιέχει τις μεταβλητές εξόδου.
Η χρήση των εντολών Δεδομένα και Αποτελέσματα γενικά προτιμάται προκειμένου ο αλγόριθμος να απαλλαγεί από τις λεπτομέρειες εισόδου/εξόδου και να επικεντρωθεί στο πρόβλημα που επιλύει (εκτός βέβαια αν το πρόβλημα είναι η εισαγωγή δεδομένων). Επίσης η χρήση τους συνιστάται στην περίπτωση που τα δεδομένα εισόδου ή/και εξόδου είναι πολυπληθή, όπως για παράδειγμα σε προβλήματα επεξεργασίας πινάκων. Τέλος η χρήση τους επιβάλλεται, στην περίπτωση που ένας αλγόριθμος καλείται από άλλον.
Παράδειγμα 2.9. Υπολογισμός τελικής αξίας είδους
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει την καθαρή αξία ενός είδους και το ποσοστό ΦΠΑ και να υπολογίζει και να εκτυπώνει την τελική αξία.
(Ο ΦΠΑ = "Φόρος Προστιθέμενης Αξίας" είναι ένας φόρος που επιβάλλεται σε κάθε προϊόν που πωλείται ή σε κάθε παρεχόμενη υπηρεσία και επιβαρύνει την τελική τιμή πώλησης.)
ΚΑ: Καθαρή Αξία, ΤΑ: Τελική Αξία, ΦΠΑ: Ποσοστό Φόρου Προστιθέμενης Αξίας
Αλγόριθμος Υπολογισμός_ΦΠΑ
Εμφάνισε "Δώστε τιμές για την Καθαρή Αξία και το Ποσοστό ΦΠΑ:"
Διάβασε ΚΑ, ΦΠΑ
ΤΑ ← ΚΑ + ΚΑ * ΦΠΑ / 100
Εκτύπωσε "Τελική Αξία:", ΤΑ
Τέλος Υπολογισμός_ΦΠΑ
Η τελική αξία (ΤΑ) ενός είδους βρίσκεται, αν στην καθαρή αξία (ΚΑ) προστεθεί η αξία ΦΠΑ. Αυτό επιτυγχάνεται με την εντολή εκχώρησης.
Οι εντολές εισόδου/εξόδου μπορούν να συνδυάζονται προκειμένου να είναι πιο κατανοητή η ενέργεια που απαιτείται από το χρήστη του προγράμματος που θα υλοποιεί έναν αλγόριθμο.
Άσκηση 1(2.9). Υπολογισμός εμβαδού τριγώνου
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει την βάση β και το ύψος υ τριγώνου και να υπολογίζει και να εκτυπώνει το εμβαδό του Ε.
Άσκηση 2(2.9). Υπολογισμός εμβαδού τραπεζίου
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει την μικρή βάση β, την μεγάλη βάση Β και το ύψος υ τραπεζίου και να υπολογίζει και να εκτυπώνει το εμβαδό του Ε.
Άσκηση 3(2.9). Υπολογισμός υποτείνουσας με Πυθαγόρειο Θεώρημα
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει τις δύο κάθετες πλευρές ορθογωνίου τριγώνου και να υπολογίζει και να εκτυπώνει την τιμή της υποτείνουσας. Σημείωση: Θα χρειαστεί η συνάρτηση που υπολογίζει τετραγωνική ρίζα Τ_Ρ().
Άσκηση 4(2.9). Υπολογισμός τελικής τιμής με έκπτωση
Να γραφεί αλγόριθμος, ο οποίος να διαβάζει την αρχική τιμή ενός προϊόντος και το ποσοστό της έκπτωσης και να υπολογίζει και να εκτυπώνει την τελική τιμή.
Άσκηση 20(Β). Υπολογισμός βαρυτικής ελκτικής δύναμης
Ο νόμος του Νεύτωνα για τη βαρύτητα λέει ότι κάθε σώμα στο σύμπαν έλκει κάθε άλλο σώμα με δύναμη που δίνεται από τον τύπο
όπου m1 και m2 είναι οι μάζες των δύο σωμάτων (σε κιλά), r η απόσταση μεταξύ τους (σε μέτρα) και G είναι η παγκόσμια βαρυτική σταθερά. Να αναπτύξετε αλγόριθμο ο οποίος θα διαβάζει τις δύο μάζες, την απόσταση μεταξύ τους και θα υπολογίζει και θα εκτυπώνει τη δύναμη. Δίνεται ότι G = 6,67 x 10-11 N*m2*kg-2.
Εφαρμογή: μάζα Γης: 5.97*1024kg μάζα Σελήνης: 7.4*1022kg απόσταση Γης-Σελήνης: 384.400.000m
Άσκηση 21(Β). Υπολογισμός αρχικής τιμής πριν την έκπτωση
Στην περίοδο των εκπτώσεων αγοράσατε ένα ποδήλατο με έκπτωση 25%. Το ποσό που δώσατε για το ποδήλατο ήταν 100 ευρώ. Να αναπτύξετε αλγόριθμο ο οποίος θα υπολογίζει την αρχική τιμή του ποδηλάτου. Να γενικεύσετε τον αλγόριθμο.
Υπόδειξη:
Αν η τελική τιμή είναι τ, η αρχική τιμή είναι α και η έκπτωση είναι ε η μαθηματική σχέση που τα συνδέει θα είναι:
Άσκηση 5(2.9). Υπολογισμός ακέραιου πηλίκου και υπόλοιπου διαίρεσης
Να αναπτύξετε αλγόριθμο ο οποίος θα υπολογίζει και θα εμφανίζει το ακέραιο πηλίκο και το υπόλοιπο της διαίρεσης ενός αριθμού με έναν άλλο αριθμό που θα εισάγονται από τον χρήστη.
Υπόδειξη: Αν οι δύο αριθμοί είναι αποθηκευμένοι στις μεταβλητές α και β το ακέραιο πηλίκο θα δίνεται από την έκφραση π ← α Div β και το υπόλοιπο θα δίνεται από την έκφραση υ ← α Mod β.
Άσκηση 6(2.9). Υπολογισμός μετατροπής από κλίμακα Κελσίου σε Φαρενάιτ
Να αναπτύξετε αλγόριθμο ο οποίος θα δέχεται μια θερμοκρασία σε βαθμούς Φαρενάιτ και θα υπολογίζει και θα εμφανίζει την αντίστοιχη θερμοκρασία σε βαθμούς Κελσίου.
Υπόδειξη: Ο τύπος μετατροπής είναι: F = 1.8*C + 32