ΒΙΒΛΙΟ ΚΑΘΗΓΗΤΗ: ΑΛΓΟΡΙΘΜΟI ΟΥΡΑΣ-ΣΤΟΙΒΑΣ

Ξεκίνησε από tsak, 07 Ιουλ 2015, 11:46:57 ΜΜ

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

tsak

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

Αλγόριθμος Εξαγωγή_από_Ουρά
Δεδομένα // rear, item //
Αν rear <= front τότε
front ← front+1
item ← queue[front]
done ← Αληθής
αλλιώς
done ← Ψευδής
Τέλος_αν
Αποτελέσματα // item, rear, done //
Τέλος Εξαγωγή_από_Ουρά


ενώ θα έπρεπε,

Αλγόριθμος Εξαγωγή_από_Ουρά
Δεδομένα // rear, item //
Αν rear <> front τότε
front ← front+1
item ← queue[front]
done ← Αληθής
αλλιώς
done ← Ψευδής
Τέλος_αν
Αποτελέσματα // item, rear, done //
Τέλος Εξαγωγή_από_Ουρά


Το αναφέρω μιας και θα μας απασχολήσει φέτος και στην υλοποίηση ασκήσεων.

tsak

Λάθος υπάρχει επίσης και στον αλγόριθμο απώθησης από στοίβα, που γράφει:

Αλγόριθμος Απώθηση
Δεδομένα // top //
Αν top<=1 τότε
item ← stack[top]
top ← top-1
done ← Αληθής
αλλιώς
done ← Ψευδής
Τέλος_αν
Αποτελέσματα // item, top, done //
Τέλος Απώθηση


ενώ θα έπρεπε,

Αλγόριθμος Απώθηση
Δεδομένα // top //
Αν top>=1 τότε
item ← stack[top]
top ← top-1
done ← Αληθής
αλλιώς
done ← Ψευδής
Τέλος_αν
Αποτελέσματα // item, top, done //
Τέλος Απώθηση


Δεν ξέρω αν έχω κάποια παλιά έκδοση του βιβλίου και αν έχουν διορθωθεί αυτά σε καινούρια version

Λαμπράκης Μανώλης

Παράθεση από: tsak στις 07 Ιουλ 2015, 11:46:57 ΜΜ
Γεια σας. Δεν ξέρω αν έχει συζητηθεί παλαιότερα, αλλά στο βιβλίο του καθηγητή υπάρχει νομίζω λάθος στην υλοποίηση του αλγορίθμου εξαγωγής από ουρά και συγκεκριμένα λέει:

Αλγόριθμος Εξαγωγή_από_Ουρά
Δεδομένα // rear, item //
Αν rear <= front τότε
front ← front+1
item ← queue[front]
done ← Αληθής
αλλιώς
done ← Ψευδής
Τέλος_αν
Αποτελέσματα // item, rear, done //
Τέλος Εξαγωγή_από_Ουρά


ενώ θα έπρεπε,

Αλγόριθμος Εξαγωγή_από_Ουρά
Δεδομένα // rear, item //
Αν rear <> front τότε
front ← front+1
item ← queue[front]
done ← Αληθής
αλλιώς
done ← Ψευδής
Τέλος_αν
Αποτελέσματα // item, rear, done //
Τέλος Εξαγωγή_από_Ουρά


Το αναφέρω μιας και θα μας απασχολήσει φέτος και στην υλοποίηση ασκήσεων.

καλησπέρα

έχω την εντύπωση πως στην απώθηση η συνθήκη είναι  "" Αν  rear >= front  τότε "" ... μπορούμε να εκτελέσουμε εξωγωγή αν ο δείκτης πίσω είναι μεγαλύτερος ή και ίσως όμως από τον δείκτη εμπρός ...  αν έχουν ίδια τιμή υπάρχει ένα στοιχείο στην ουρά ... σωστά ?? επίσης μία ερώτηση, στον ίδιο κώδικα, πρώτα αυξάνει την τιμή του front και στην συνέχεια εκτελεί 
item ← queue[front]  ... η μεταβλητή item με τον τρόπο που εκτελείται ο κώδικας έχει τιμή το στοιχείο που δείχνει ο δείκτης front ???  γιατί αν η λογική είναι το item να εκφράζει το στοιχείο που βγήκε, πρώτα πρέπει να γίνει η εκχώρηση αυτή και στη συνέχεια να αυξηθεί το front κατά ένα ... συμφωνείτε ??

Λαμπράκης Μανώλης

διόρθωση ,όχι στην απώθηση, στην εξαγωγή από την ουρά εννοώ   >:D :police: :laugh: :angel:

tsak

Παράθεση από: Λαμπράκης Μανώλης στις 08 Ιουλ 2015, 03:42:05 ΜΜ
καλησπέρα

έχω την εντύπωση πως στην απώθηση η συνθήκη είναι  "" Αν  rear >= front  τότε "" ... μπορούμε να εκτελέσουμε εξωγωγή αν ο δείκτης πίσω είναι μεγαλύτερος ή και ίσως όμως από τον δείκτη εμπρός ...  αν έχουν ίδια τιμή υπάρχει ένα στοιχείο στην ουρά ... σωστά ?? επίσης μία ερώτηση, στον ίδιο κώδικα, πρώτα αυξάνει την τιμή του front και στην συνέχεια εκτελεί 
item ← queue[front]  ... η μεταβλητή item με τον τρόπο που εκτελείται ο κώδικας έχει τιμή το στοιχείο που δείχνει ο δείκτης front ???  γιατί αν η λογική είναι το item να εκφράζει το στοιχείο που βγήκε, πρώτα πρέπει να γίνει η εκχώρηση αυτή και στη συνέχεια να αυξηθεί το front κατά ένα ... συμφωνείτε ??

Θα διαφωνήσω γιατί π.χ. εξέτασε την περίπτωση που δεν έχει γίνει τίποτα ακόμη με την ουρά (καμία εισαγωγή ή εξαγωγή). Οι δείκτες front και rear ξεκινάνε από το 0. Η διόρθωση που προτείνω (rear<>front) θα λειτουργήσει σωστά αν πάει να γίνει εξαγωγή (δεν θα το επιτρέψει ο κώδικας), ενώ αν βάλεις στη συνθήκη "rear>=front" θα προσπαθήσει να κάνει εξαγωγή για ένα στοιχείο που δεν υπάρχει.
Επίσης, αν δοκιμάσεις κάποιες εισαγωγές και εξαγωγές θα δεις ότι δουλεύει σωστά.

Λαμπράκης Μανώλης

Παράθεση από: tsak στις 08 Ιουλ 2015, 10:01:02 ΜΜ
Θα διαφωνήσω γιατί π.χ. εξέτασε την περίπτωση που δεν έχει γίνει τίποτα ακόμη με την ουρά (καμία εισαγωγή ή εξαγωγή). Οι δείκτες front και rear ξεκινάνε από το 0. Η διόρθωση που προτείνω (rear<>front) θα λειτουργήσει σωστά αν πάει να γίνει εξαγωγή (δεν θα το επιτρέψει ο κώδικας), ενώ αν βάλεις στη συνθήκη "rear>=front" θα προσπαθήσει να κάνει εξαγωγή για ένα στοιχείο που δεν υπάρχει.
Επίσης, αν δοκιμάσεις κάποιες εισαγωγές και εξαγωγές θα δεις ότι δουλεύει σωστά.

καλησπέρα ξανά

συμφωνώ ότι χρειάζεται κάποιος έλεγχος για τις αρχικές τους τιμές ... όμως έστω ότι έχομε μία ουρά πχ 10 θέσεων που μετά από εισαγωγές - εξαγωγές υπάρχει ένα στοιχείο πχ στην θέση 5 ... τότε και οι δύο δείκτες έχουν τιμή 5 ... στην συνθήκη σου θα εξετάσει αν front <> rear, κάτι που είναι ψευδής και δεν θα κάνει εξαγωγή .. το συγκεκριμένα κομμάτια κώδικα θεωρώ είναι "περιορισμένα" με την έννοια πως εξετάζουν συγκεκριμένες περιπτώσεις και δεν είναι γενικά ...  περιέχουν αρκετές υποθέσεις και θέλουν θα πρεσθέσουμε κομμάτια για να ισχύουν στην γενική περίπτωση

tsak

#6
Αυτό προσπαθώ να εξηγήσω, ότι αφού ξεκινάνε οι δείκτες από το μηδέν, δεν πρόκειται πότε να δείξουν ταυτόχρονα σε κελί που έχει περιεχόμενο προς εξαγωγή. Στο παράδειγμα σου και σύμφωνα με τον αλγόριθμο του βιβλίου καθηγητή (με τη συνθήκη rear<>front όμως), ο front θα δειχνει στο 4 και ο  rear στο 5.Κανε 5 εισαγωγές και μετά 5 εξαγωγές να δεις.
Βέβαια για να είμαστε ακριβείς, ο παραπάνω αλγόριθμος εξαγωγής δεν συμφωνεί ακριβώς με τα γραφόμενα στο βιβλίο του μαθητή, το οποίο λέει για την περίπτωση της εξαγωγής ότι πρώτα εξέρχεται το στοιχείο που δείχνει ο front και μετά αυξάνεται κατά ένα. Στην υλοποίηση του βιβλίου του καθηγητή, πρώτα αυξάνει τον δείκτη και μετά δείχνει ποιο στοιχείο εξέρχεται.

Λαμπράκης Μανώλης

καλημέρα

https://alkisg.mysch.gr/steki/index.php?topic=3760.msg38724#msg38724

https://alkisg.mysch.gr/steki/index.php?topic=3760.msg38724#msg38724

https://alkisg.mysch.gr/steki/index.php?topic=954.0

κάποιες συζητήσεις που είχαν γίνει και στο παρελθόν,  μάλλον καταλήγουν στο συμπρέρασμα ότι το θέμα αυτό σίγουρα χρειάζεται παραπάνω ανάλυση και χρειάζονται διευκρινίσεις για το πως πρέπει να υλοποιούμε μία ουρά .... όμως - επιτρέψτε μου την "απαγορευμένη έκφραση"  :police: :angel: -  """ στα πλαίσια του μαθήματος """", γιατί καλώς ή κακώς με βάση αυτό εγώ προσωπικά διδάσκω, η ουρά είναι στατική δομή και μάλλον δεν θα ζητηθεί η "κυκλική υλοποίησή της", δηλαδή αν σε ουρά 5 θέσεων ο δείκτης πίσω φτάσει στην θέση 5, τότε ""μάλλον"" η ουρά θεωρείται γεμάτη ... επαναλαμβάνω στα πλαίσια του μαθηματος ... εγώ αυτό που έχω καταλάβει στο βιβλίο είναι ότι ο δείκτης εμπρός δείχνει στο στοιχείο που θα εξαχθεί σε πρώτη ευκαιρία και στα παραδείγματα  ο δείκτης εμπρός δείχνει στο " πιο αριστερά στοιχείο που υπάρχει στην ουρά" - ας μου επιτραπεί η έκφραση ... οπότε στην ουρά 10 θέσεων αν υπάρχει άν στοιχείο στην θέση 5, ο δείκτης εμπρός θα δείχνει στην 5 και ο πίσω στην 5 ... αν δείχνει στην θέση 4 δεν υπάρχει στοιχείο να βγει ... έτσι το αντιλαμβάνομαι εγώ τουλάχιστον ..και στις παραπάνω συζητήσεις φαίνεται πως μελετάμε μάλλον ένα κομμάτι της πραγματικότητας

tsak

Σιγουρα υπαρχει ασυμφωνια μεταξυ τησ αναλυσης στο βιβλιο μαθητη  και του αλγοριθμου του βιβλιου καθηγητη.Προκυπτει και εδω λοιπον θεμα ως προς το ποια λογικη πρεπει να δειξόυμε.Εγω απλως σχολιασα και διορθωσα αυτα που εχει στο βιβλιο καθηγητη.Παντως οι αλγοριθμοι αυτοι ειναι ουσιστικα απο το βιβλιο ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ των Μανωλοπουλου και Βακαλη που ειναι και οι συγγραφεις των βιβλιων της ΑΕΠΠ.Ηταν και καθηγητες μου στο ΑΠΘ.

Λαμπράκης Μανώλης

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