Αποστολέας Θέμα: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ  (Αναγνώστηκε 2165 φορές)

vav

  • Βετεράνος
  • ****
  • Μηνύματα: 54
ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« στις: 21 Μάρ 2011, 08:58:00 μμ »
Έστω μία ουρά που υλοποιείται με έναν μονοδιάστατο πίνακα 10 θέσεων με δύο δείκτες τον εμπρός (front) και πίσω (rear). Θεωρήστε ότι η ουρα είναι κενή.

Ποιες είναι οι αρχικές τιμές των δύο δεικτών ?
θα είναι :
εμπρός=1      πίσω =0
ή δεν προκύπτει πουθενά από το σχολικό βιβλίο??

Λάμπρος Μπουκουβάλας

  • Η παιδεία είναι: στους φτωχούς, ΠΛΟΥΤΟΣ. Στους πλούσιους, ΣΤΟΛΙΔΙ. Στους νέους, ΚΑΙ ΤΑ ΔΥΟ (Διογένης) !
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 1242
    • Το μπλογκάκι μου
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #1 στις: 21 Μάρ 2011, 11:04:38 μμ »
σύμφωνα με το βιβλίο, ο front πρέπει να βρίσκεται 1 θέση πριν τον rear.
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται…

Σπύρος Δουκάκης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 831
  • Έτερος εξ ετέρου σοφός, το τε πάλαι το τε νυν
    • http://sdoukakis.wordpress.com/
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #2 στις: 21 Μάρ 2011, 11:10:47 μμ »
Δες και αυτό

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

Έστω μία ουρά που υλοποιείται με έναν μονοδιάστατο πίνακα 10 θέσεων με δύο δείκτες τον εμπρός (front) και πίσω (rear). Θεωρήστε ότι η ουρα είναι κενή.

Ποιες είναι οι αρχικές τιμές των δύο δεικτών ?
θα είναι :
εμπρός=1      πίσω =0
ή δεν προκύπτει πουθενά από το σχολικό βιβλίο??

vav

  • Βετεράνος
  • ****
  • Μηνύματα: 54
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #3 στις: 22 Μάρ 2011, 08:40:09 πμ »
σύμφωνα με το βιβλίο, ο front πρέπει να βρίσκεται 1 θέση πριν τον rear, όπως λέει και ο
κ. Μπουκουβάλας και συμφωνώ και 'γω, ώστε να μπορέσει να ελεγχθεί αν μία ουρά είναι άδεια.
δεν είναι λογικό σε μία κενή ουρά και οι δύο δείκτες να είναι μηδέν.

Λάμπρος Μπουκουβάλας

  • Η παιδεία είναι: στους φτωχούς, ΠΛΟΥΤΟΣ. Στους πλούσιους, ΣΤΟΛΙΔΙ. Στους νέους, ΚΑΙ ΤΑ ΔΥΟ (Διογένης) !
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 1242
    • Το μπλογκάκι μου
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #4 στις: 22 Μάρ 2011, 09:28:18 πμ »
παρόλα αυτά, μπορείς να δώσεις σαφή απάντηση για τα εξής;;;;

front=1, rear=2
front=10, rear=11

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

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται…

Σπύρος Δουκάκης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 831
  • Έτερος εξ ετέρου σοφός, το τε πάλαι το τε νυν
    • http://sdoukakis.wordpress.com/
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #5 στις: 22 Μάρ 2011, 10:36:51 πμ »
Οι παράγραφοι ουράς-στοίβας είναι τμήματα κειμένων από το βιβλίο του Μανωλόπουλου "Δομές Δεδομένων" όπου λέει:

Παράθεση
... αρχικά ισχύει front = rear = lowerminus1 = 0.
Ο πίσω δείκτης δείχνει πάντα στο τελευταίο στοιχείο της ουράς.
Αν μία ουρά έχει μόνο ένα στοιχείο, τότε και οι δύο δείκτες δείχνουν στο στοιχείο αυτό.
Επειδή βολεύει η ισότητα των δεικτών να αποδεικνύει ότι η ουρά είναι άδεια, ο εμπρός δείκτης είναι κατά μία μονάδα μικρότερος από την πραγματική αρχή της ουράς.

Προσεγγίζω παιδαγωγικά την ουρά με την ουρά σε ένα supermarket όπου οι πελάτες θέλουν να αγοράσουν τυρί  και χρειάζεται να έχουν ένα χαρτάκι.

Όταν ανοίξει το supermarket το πρώτο χαρτάκι είναι το 1, αλλά κανένας πελάτης δεν έχει πάρει ακόμα χαρτάκι και άρα 0 πελάτες είναι στην ουρά. Ο δείκτης εμπρός και πίσω είναι 0. Μόλις πάρει ο πρώτος πελάτης το χαρτάκι 1, το μηχανηματάκι είναι έτοιμο να δώσει 2ο χαρτάκι, αλλά δεν το έχει πάρει ακόμα κάποιος και άρα ο εμπρός και ο πίσω δείκτης έχουν την ίδια τιμή που είναι 1. Η διαδικασία συνεχίζεται και το χαρτάκι περιμένει τον πελάτη στην επόμενη θέση.

Εξίσου χρήσιμη είναι η ουρά στο supermarket για να κατανοήσουν οι μαθητές ότι ποτέ δεν θα πάρει άλλος πελάτης το χαρτάκι 1, παρότι κάποια στιγμή θα είναι πρώτος στην ουρά και θα εξυπηρετηθεί πρώτος.

Όταν τώρα γεμίσει η ουρά και λάβει κάποιος το τελευταίο χαρτάκι (ας πούμε 200), τότε οι υπάλληλοι βάζουν νέα ταινία στο μηχανηματάκι  που ξεκινά από το 1 ξανά και άρα όταν τελειώσουν όλα τα χαρτάκια και έρχεται ο 201 πελάτης δεν μπορεί να εξυπηρετηθεί και η ουρά ξαναγυρνά στην αρχική της μορφή (το κλασικό ερώτημα των παιδιών... και άρα ο νέος 1 είναι πριν τον πελάτη 195 που δεν έχει εξυπηρετηθεί ακόμα....; )

Άρα αν η ουρά έχει δέκα θέσεις τότε
Πριν μπουν στοιχεία στην ουρά f = r = 0
Αν μπει ένα στοιχείο f = r = 1
Aν μπει δεύτερο στοιχείο και δεν έχει βγει το πρώτο f = 1 r = 2
Αν μπει δεύτερο στοιχείο και έχει βγει το πρώτο f = 2 r = 2

Αν μπει στην ουρά στοιχείο στη θέση 10 και δεν έχουν βγει κάποια προηγούμενα f < 10 και r = 10
Αν προσπαθήσει να μπει και άλλο στοιχείο τότε δεν επιτρέπει η διαδικασία την εισαγωγή αφού r δεν είναι πλέον μικρότερο του 10.
Αν εξυπηρετηθούν όλα τότε f = 11 και ΤΕΛΟΣ.

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

vav

  • Βετεράνος
  • ****
  • Μηνύματα: 54
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #6 στις: 22 Μάρ 2011, 11:02:06 πμ »
Με την λογική αυτή δηλ  r=10 f=11 (f>r) σε περίπτωση που έχουν εξαχθεί όλα τα στοιχεία και η ουρά είναι άδεια θα μπορούσαμε να επικαλεστούμε και ότι r=0 και f=1  (f>r) όταν εξαρχής είναι άδεια.

Καρκαμάνης Γεώργιος

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1133
Απ: ΑΠΟΡΙΑ ΣΤΟΙΒΑ-ΟΥΡΑ
« Απάντηση #7 στις: 22 Μάρ 2011, 12:19:44 μμ »

Άρα αν η ουρά έχει δέκα θέσεις τότε
Πριν μπουν στοιχεία στην ουρά f = r = 0
Αν μπει ένα στοιχείο f = r = 1
Aν μπει δεύτερο στοιχείο και δεν έχει βγει το πρώτο f = 1 r = 2
Αν μπει δεύτερο στοιχείο και έχει βγει το πρώτο f = 2 r = 2

Αν μπει στην ουρά στοιχείο στη θέση 10 και δεν έχουν βγει κάποια προηγούμενα f < 10 και r = 10
Αν προσπαθήσει να μπει και άλλο στοιχείο τότε δεν επιτρέπει η διαδικασία την εισαγωγή αφού r δεν είναι πλέον μικρότερο του 10.
Αν εξυπηρετηθούν όλα τότε f = 11 και ΤΕΛΟΣ.

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