Μετάβαση στο περιεχόμενο

Αλγόριθμοι και διαγράμματα ροής

Ένα πρόβλημα λυμένο βήμα βήμα, και σχεδιασμένο σε σχήμα.

35 λεπτά

Θα μάθεις να

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

Μια συνταγή για τον υπολογιστή

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

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

Τι είναι αλγόριθμος

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

Για να είναι μια σειρά οδηγιών αλγόριθμος, πρέπει:

ΙδιότηταΤι σημαίνειΠαράδειγμα που αποτυγχάνει
Είσοδοςπαίρνει δεδομένα για να δουλέψει (μπορεί και κανένα)—
Έξοδοςδίνει τουλάχιστον ένα αποτέλεσμα«Υπολόγισε το άθροισμα» χωρίς να το εμφανίσει πουθενά
Σαφήνεια (καθοριστικότητα)κάθε βήμα έχει μία ερμηνεία«Ρίξε λίγο αλάτι»
Περατότητατελειώνει μετά από πεπερασμένο πλήθος βημάτων«Μέτρα 1, 2, 3, … και μη σταματήσεις»
Εκτελεσιμότητα (αποτελεσματικότητα)κάθε βήμα μπορεί πράγματι να γίνει«Διαίρεσε με το μηδέν»

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

Δύο σελίδες ενός παλιού αραβικού χειρογράφου γεμάτες γραφή με μαύρο μελάνι· στο κάτω μέρος κάθε σελίδας ένα γεωμετρικό σχήμα από τετράγωνα και ορθογώνια με κόκκινες γραμμές.
Δύο σελίδες από την «Άλγεβρα» του αλ-Χουαρίζμι, σε αντίγραφο που φυλάγεται σήμερα στην Οξφόρδη. Δεν υπάρχουν σύμβολα όπως το x ή το =: οι κανόνες του είναι γραμμένοι ολόκληροι με λέξεις, ένα βήμα μετά το άλλο, όπως γράφεις κι εσύ έναν αλγόριθμο σε φυσική γλώσσα.Φωτογραφία: Bodleian Library, Oxford · κοινό κτήμα · Wikimedia Commons

Πώς γράφεται ένας αλγόριθμος

Ο ίδιος αλγόριθμος μπορεί να γραφτεί με διάφορους τρόπους:

  1. Με φυσική γλώσσα, σε αριθμημένα βήματα. Εύκολο, αλλά οι λέξεις μπορεί να είναι ασαφείς.
  2. Με διάγραμμα ροής: σχήματα συνδεδεμένα με βέλη. Φαίνεται με μια ματιά πού πάει η εκτέλεση.
  3. Με ψευδοκώδικα: σύντομες εντολές που μοιάζουν με γλώσσα προγραμματισμού.
  4. Και τελικά, σε γλώσσα προγραμματισμού (όπως το Scratch ή η Python), ώστε να τον εκτελέσει ο υπολογιστής.

Τα σχήματα του διαγράμματος ροής

Κάθε σχήμα έχει συγκεκριμένη σημασία:

ΣχήμαΧρήσηΤι γράφουμε μέσα
Έλλειψη (οβάλ)αρχή και τέλος«Αρχή», «Τέλος»
Πλάγιο παραλληλόγραμμοείσοδος και έξοδος δεδομένων«Διάβασε α», «Εμφάνισε άθροισμα»
Ορθογώνιοεπεξεργασία: πράξη ή ανάθεση τιμής«άθροισμα ← α + β»
Ρόμβοςαπόφαση: ερώτηση με απάντηση ΝΑΙ ή ΟΧΙ«α > β ;»
Βέλοςη σειρά εκτέλεσης—

Από τον ρόμβο βγαίνουν δύο βέλη, ένα για το ΝΑΙ κι ένα για το ΟΧΙ. Από όλα τα άλλα σχήματα (εκτός από το «Τέλος») βγαίνει ένα.

Το βελάκι ← σημαίνει ανάθεση: «υπολόγισε ό,τι είναι δεξιά και βάλ' το στη μεταβλητή αριστερά». Το άθροισμα ← α + β διαβάζεται «το άθροισμα γίνεται α συν β».

Οι τρεις δομές

Ακολουθία: τα βήματα γίνονται το ένα μετά το άλλο, με τη σειρά. Στο διάγραμμα, σχήματα στη σειρά με ένα βέλος ανάμεσα.

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

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

Ένα διάγραμμα με επανάληψη: η αντίστροφη μέτρηση

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

Αρ.ΣχήμαΠεριεχόμενοΜετά πηγαίνει
1ΈλλειψηΑρχή→ 2
2Ορθογώνιομετρητής ← 3→ 3
3Ρόμβοςμετρητής > 0 ;ΝΑΙ → 4, ΟΧΙ → 6
4Πλάγιο παραλληλόγραμμοΕμφάνισε μετρητής→ 5
5Ορθογώνιομετρητής ← μετρητής − 1→ 3 (πίσω)
6Πλάγιο παραλληλόγραμμοΕμφάνισε «Εκκίνηση»→ 7
7ΈλλειψηΤέλος—

Το βέλος από το 5 πίσω στο 3 είναι η επανάληψη. Κάθε φορά που περνά από τον ρόμβο, ο μετρητής είναι κατά ένα μικρότερος, οπότε κάποια στιγμή η απάντηση θα γίνει ΟΧΙ και ο αλγόριθμος θα τελειώσει.

Ας εκτελέσουμε το διάγραμμα με το μολύβι. Πριν πατήσεις, πες ποια θα είναι η επόμενη γραμμή.

Αντίστροφη μέτρηση, σχήμα προς σχήμα

Κάθε γραμμή είναι ένα σχήμα που εκτελείται. Η απάντηση του ρόμβου και ό,τι εμφανίζεται έρχονται πρώτα ως «?»: πες τα εσύ και μετά πάτα ξανά. Πρόσεξε πόσες φορές περνάμε από τον ρόμβο 3.

ΒήμαΣχήμαμετρητήςμετρητής > 0 ;Εμφανίζεται
Ζωντανή ενημέρωση

Ο ίδιος αλγόριθμος σε ψευδοκώδικα

Το διάγραμμα της αντίστροφης μέτρησης, γραμμένο σε ψευδοκώδικα, είναι:

Αντίστροφη μέτρηση

Ο μετρητής ξεκινά από το 3. Πριν από κάθε βήμα πες τι θα γίνει: αν η συνθήκη της γραμμής 2 είναι Αληθής, τι θα εμφανιστεί και ποια τιμή θα πάρει ο μετρητής.

  1. τρέχουσα γραμμή: μετρητής ← 3
  2. ΟΣΟ μετρητής > 0 ΕΠΑΝΑΛΑΒΕ
  3. ΓΡΑΨΕ μετρητής
  4. μετρητής ← μετρητής - 1
  5. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  6. ΓΡΑΨΕ 'Εκκίνηση'

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.Γραμμή 1: τι τιμή θα πάρει το μετρητής;

Μεταβλητές

—

Έξοδος

Οι γραμμές 3 και 4 είναι μετατοπισμένες προς τα δεξιά: έτσι φαίνεται ότι βρίσκονται μέσα στην επανάληψη. Στο Scratch, αυτό θα είναι ένα τουβλάκι που «αγκαλιάζει» άλλα τουβλάκια.

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

Παράδειγμα 1

Γράψε διάγραμμα ροής που διαβάζει δύο αριθμούς α και β και εμφανίζει τον μεγαλύτερο.

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 2

Γράψε αλγόριθμο που διαβάζει 3 βαθμούς, βρίσκει τον μέσο όρο τους, και εμφανίζει «Προάγεται» αν ο μέσος όρος είναι τουλάχιστον 10, αλλιώς «Χρειάζεται στήριξη».

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Τι είναι αλγόριθμος;

Ασκήσεις

ΒασικήΆσκηση 1 από 4

Σε ποιο σχήμα διαγράμματος ροής γράφεται η εντολή εμβαδόν ← πλάτος × μήκος;

Τα κατάφερες;

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

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;