καλύτερη υλοποίηση ουράς

Ξεκίνησε από Αναστάσης Κολιόπουλος, 23 Ιουν 2022, 05:47:27 ΜΜ

« προηγούμενο - επόμενο »

Αναστάσης Κολιόπουλος

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

ΕΙΣΑΓΩΓΗ:

Αν rear = n τότε 
  Γράψε "Γεμάτη ουρά"
αλλιώς 
  rear <- rear + 1 
  Διάβασε ουρά[rear]
τέλος_αν 

ΕΞΑΓΩΓΗ:

Αν rear = 0 τότε 
  Γράψε "Άδεια ουρά"
αλλιώς 
  Γράψε "Εξάγεται το ",ουρά[1]
  Για i από 1 μέχρι rear - 1 ! Ολίσθηση στοιχείων της ουράς στις πρώτες θέσεις, όπως σε μία πραγματική κατάσταση ουράς
    ουρά <- ουρά
  τέλος_επανάληψης 
  rear <- rear - 1
τέλος_αν 

Παρατηρήσεις: 
i. Ο δείκτης rear αρχικοποιείται με τιμή μηδέν ( rear <- 0 ).
ii. Ο δείκτης front είναι περιττός.
iii. Γνωρίζω ότι η ολίσθηση υπάρχει στην άσκηση με το ταχυδρομείο αλλά ο κώδικας εκεί είναι αχρείαστα πολύπλοκος, γιαυτό και προτείνω έναν πιο απλό κώδικα.

Foto

Ένας αποδοτικός αλγόριθμος για ουρά χωρίς ολίσθηση θα χρησιμοποιούσε μια δομή με τιμή και δείκτη επόμενης θέσης. Αυτή η δομή λέγεται κόμβος. Όταν ο δείκτης επόμενης θέσης είναι 0 τότε σημαίνει Null, άρα ο κόμβος είναι τερματικός. Τα νούμερα για τους δείκτες θα έρχονται από μια στοίβα που θα χρησιμοποιεί τους κόμβους χωρίς να ενδιαφέρεται για την τιμή στο κόμβο.
Για να δουλέψει όλο αυτό χρειαζόμαστε δύο πίνακες μονοδιάστατους. Ο ένας θα έχει τις τιμές και ο άλλος τους δείκτες  Έστω ότι οι πίνακες έχουν 50 στοιχεία, από 1 μέχρι 50. Η αρχική κατάσταση του πίνακα ΔΕΙΚΤΗΣ[] θα είναι: ΔΕΙΚΤΗΣ[1]<-2 δηλαδή η θέση 1 δείχνει στη θέση 2. Στη θέση 50 θα έχουμε το 0, δεν υπάρχει άλλο! Η στοίβα θα δουλέψει με μια μεταβλητή έστω Σ που θα δείχνει στο 1. Όταν θα θέλουμε κόμβο θα κοιτάμε αν το Σ είναι 0 και αν δεν είναι τότε θα παίρνουμε αυτόν τον κόμβο για χρήση στην ουρά και θα βάζουμε στο Σ την τιμή του ΔΕΊΚΤΗΣ[Σ]. Κάθε φορά που θέλουμε να επιστρέψουμε έναν κόμβο έστω ήταν αυτός στη θέση 10, τότε θα βάζουμε στο ΔΕΙΚΤΗΣ[Σ] την τιμή του Σ και στο Σ το 10. Έτσι δουλεύει η στοίβα για τους κενούς κόμβους.
Για την ουρά χρειαζόμαστε δύο μεταβλητές. Την ΕΙΣ για να βάλουμε το κόμβο που θα εισάγουμε και την ΕΞ για να βάλουμε τον κόμβο που θα εξάγουμε Όταν τα ΕΙΣ και ΕΞ είναι 0 τότε η ουρά είναι άδεια. Αν είναι άδεια η ουρά και θέλουμε να βάλουμε ένα κόμβο έστω τον 10, τότε τα ΕΙΣ και ΕΞ θα πάρουν την τιμή 10, ενώ ο ΔΕΊΚΤΗΣ[10] θα πάρει την τιμή ΕΙΣ που είναι 0. Αν βάλουμε έστω τον κόμβο 15 (ότι μας δώσει η στοίβα) τότε το ΔΕΙΚΤΗΣ[10] θα δείχνει το 15,  όπου το ΕΙΣ είναι το 10, και το ΕΙΣ θα πάρει το 15. Έτσι γεμίζουμε την ουρά. Τι γίνεται όμως στο διάβασμα. Επειδή κατά την εγγραφή της ουράς οι δείκτες δείχνουν προς το τελευταίο που μπήκε στο ΕΞ που είναι το 10 θα μας δώσει ο ΔΕΊΚΤΗΣ[ΕΞ] το 15, και θα το βάλουμε ως νέο ΕΞ. Την επόμενη φορά θα πάρουμε το 0 οπότε μηδενίζουμε και το ΕΙΣ (δηλαδή σε κάθε απόσυρση από την ουρά ελέγχουμε για null τιμή). Μας ενδιαφέρει στο άδειασμα των κόμβων τα ΕΙΣ και ΕΞ να γίνουν 0, γιατί σε επόμενη εισαγωγή πρέπει εκτός από τον ΕΙΣ να φτιάξουμε και τον ΕΞ.
Δεν έχω βάλει την χρήση του άλλου πίνακα, που θα μπουν οι τιμές. Αλλά για τη λογική της ουράς με κόμβους δεν χρειάζεται.
Η ουρά με κόμβους δεν έχει μετακινήσεις. Η χρήση της στοίβας για τους κενούς κύβους απαιτεί μια μεταβλητή και κατάλληλη αρχικοποίηση όλων των δεικτών. Η χρήση της ουράς απαιτεί μόνο δύο μεταβλητές και όλα είναι τυποποιημένα. Στην εισαγωγή ελέγχουμε αν το ΕΙΣ είναι μμηδεν και βάζουμε ίδιο δείκτη κόμβου στα ΕΙΣ και ΕΞ. Στην εξαγωγή του τελευταίου όταν το ΕΞ γίνει μηδέν κάνουμε και το ΕΙΣ μηδέν. Στην εισαγωγή ενός κόμβου εκτός του πρώτου απλά γράφουμε στο ΔΕΙΚΤΗΣ[ΕΙΣ] το το νούμερο του νέου κόμβου, βάζουμε στο ΕΙΣ το νούμερο του νέου κόμβου και στο ΔΕΙΚΤΗΣ[ΕΙΣ] τιμή μηδέν. Στην εξαγωγή αν έχουμε ΕΞ διάφορο του μηδέν τότε βγάζουμε αυτόν τον κόμβο με απλή αντικατάσταση τιμής στο ΕΞ την τιμή του ΔΕΙΚΤΗΣ[ΕΞ], κοιτάμε αν είναι μηδέν και αν ναι τότε αλλάζουμε σε μηδέν και την ΕΙΣ. Επειδή θέλουμε να επιστρέψουμε το κόμβο στη στοίβα πριν αλλάξουμε την ΕΞ κραταμε την τιμή σε μια Επ (επιστρεφόμενο) και κάνουμε το Επ εισαγωγή στη στοίβα.
Δεν υπάρχουν προσθέσεις, αφαιρέσεις, συγκρίσεις μικρό ή και μεγάλο. Γίνονται μόνο μεταθέσεις τιμών και έλεγχος για το μηδέν. Η μόνη πρόσθεση γίνεται στην αρχικοποίηση της στοίβας όπου εκεί ξερά βάζουμε τους δείκτες στην θέση 1 να δείχνει το 2, μέχρι τη θέση 49 να δείχνει την 50 και στην 50 να δείχνει το 0.
Νομίζω ότι με τις οδηγίες αυτές όλοι μπορούν να φτιάξουν μια πετυχημένη ουρά με κόμβους.

Foto

#2
Μια απλή οπτικοποίηση του παραπάνω αλγορίθμου γίνεται με βελάκια.
Έστω έχουμε 5 μόνο κενούς κόμβους:
ΕΙΣ = 0
ΕΞ = 0
Σ = 1
1->2 2->3- 3>4 4->5 5->0. (ο 5 δείχνει 0)
Παίρνουμε το κόμβο στο Σ
Σ = 2
2->3 3->4 4->5 5->0
Βάζουμε το κόμβο 1 στην ουρά
ΕΙΣ = 1
ΕΞ = 1
0<-1 (ο 1 δείχνει το 0)
Βάζουμε το κόμβο 2 (δεν δείχνω τώρα τη στοίβα, είναι εύκολο να την κατανόηση κανείς)
ΕΙΣ =  2
ΕΞ =  1
0<-2 2<-1
Εδώ βλέπουμε ότι τον δείκτη στο προηγούμενο ΕΙΣ που δεν είναι 0 (ΕΙΣ διάφορο του μηδέν) είχαμε τιμή μηδέν και μετά την εισαγωγή έγινε τιμή 2.
Στην εξαγωγή από την ουρά ξέρουμε ότι θα πάρουμε τον κόμβο ΕΞ αν δεν είναι μηδέν, και νέα τιμή στο ΕΞ θα δώσουμε το 2 επειδή ο κόμβος 1 έδειχνε το 2
Για να βάλουμε τον κόμβο 1 πίσω στη στοίβα αρκεί να γράψουμε σαν νέο δείκτη την τιμή Σ και να δώσουμε στο Σ το 1.
Σ = 1
1->3 3->4 4->5 5->0
Βλέπουμε ότι στην στοίβα αρχίζουν οι κόμβοι να αλλάζουν την αρχική σειρά. Μας είναι όμως αδιάφορο το πώς θα γίνει.

Αναστάσης Κολιόπουλος

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


Foto

Παράθεση από: Αναστάσης Κολιόπουλος στις 23 Ιουν 2022, 09:16:54 ΜΜΝαι αλλά πως ακριβώς θα το καταλάβει όλο αυτό ο μέσος μαθητής που δυσκολεύεται να καταλάβει τι κάνει η ταξινόμηση φυσαλίδας; Η λύση με την ολίσθηση είναι πολύ πιο απλοϊκή και σχετίζεται άμεσα με την πραγματικότητα, επομένως είναι και πιο εύκολη στην κατανόηση.
Ο τρόπος που έδειξα είναι πολύ καλύτερος και πιο απλός. Μαθαίνει ο μαθητής ότι ο προγραμματισμός δεν είναι μαθηματικά. Ότι πράγματα (τιμές) μπορούν να διευθετηθούν χωρίς να μετακινηθούν. Η υλοποίηση τέτοιου παραδείγματος μαθαίνει την ουσία στο μαθητή. Όταν ξέρεις την ουσία τότε η ολίσθηση ή οαπλος πίνακας για ουρά είναι παιχνίδι.
Αν μείνει το μάθημα σε καρικατούρες τύπου ουρά με ολίσθηση, τότε δεν χρειάζεται καν να υπάρχει προγραμματισμός, μπορεί άνετα να διδαχθεί με κύβους όπως στο νηπιαγωγείο.

Αναστάσης Κολιόπουλος

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

Foto

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