Αποστολέας Θέμα: Άσκηση Ουρές  (Αναγνώστηκε 4435 φορές)

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 253
Άσκηση Ουρές
« στις: 13 Φεβ 2020, 04:08:03 πμ »
1. Να γραφεί πρόγραμμα σε Γλώσσα, το οποίο θα δέχεται ως είσοδο μία ακολουθία χαρακτήρων από το χρήστη, ένα γράμμα κάθε φορά. Το πρόγραμμα θα χειρίζεται μια ουρά 10 θέσεων. Για κάθε χαρακτήρα ‘*’ που διαβάζεται, θα πραγματοποιείται μία εξαγωγή, ενώ για κάθε άλλο χαρακτήρα, θα πραγματοποιείται η εισαγωγή του. Το πρόγραμμα θα σταματάει μόλις δοθεί ο χαρακτήρας του κενού από το χρήστη, οπότε και θα τυπώνει τα περιεχόμενα της ουράς, αδειάζοντάς την.
2. Έστω η ακολουθία χαρακτήρων:
FIRS*T*IN***FI*RS***T*OUT***** .
i) Ποια έξοδο θα πάρουμε, στο τέλος του προγράμματος, χωρίς ολίσθηση;
ii) Ομοίως, αν η ουρά υλοποιεί ολίσθηση;


Σαν πιο εξεζητημένο ερώτημα, εκτός λογικής διδακτικού πακέτου, μπορεί να μπει το:
iii) Ομοίως, αν η ουρά υλοποιεί αναδίπλωση στο τέλος του πίνακα (ή "χρησιμοποιεί κυκλική ουρά");


(Εμπνεύστηκα την άσκηση από την συνημμένη εικόνα, στο βιβλίο "Αλγόριθμοι σε C", R. Sedgewick.)
(υγ> φανταστικοί moderators... ένα υποφόρουμ για στοίβες/ουρές;)
« Τελευταία τροποποίηση: 15 Φεβ 2020, 04:48:08 μμ από akalest0s »
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 253
Απ: Άσκηση Ουρές
« Απάντηση #1 στις: 13 Φεβ 2020, 04:11:10 πμ »
και μια λύση..

Κώδικας: Javascript
  1. ΠΡΟΓΡΑΜΜΑ μο_ουρά_ακολουθία_χαρακτήρων
  2. ΣΤΑΘΕΡΕΣ
  3.   Ν = 10
  4. ΜΕΤΑΒΛΗΤΕΣ
  5.   ΧΑΡΑΚΤΗΡΕΣ: Q[Ν], input
  6.   ΑΚΕΡΑΙΕΣ: f, r, i
  7. ΑΡΧΗ
  8.   f <- 0
  9.   r <- 0
  10.   ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
  11.     ΔΙΑΒΑΣΕ input
  12.     ΑΝ input = '*' ΤΟΤΕ
  13.       ΚΑΛΕΣΕ deq(Q, f, r)
  14.     ΑΛΛΙΩΣ_ΑΝ input <> ' ' ΤΟΤΕ !μην καλείς την enq για " "
  15.       ΚΑΛΕΣΕ enq(Q, f, r, input)
  16.     ΤΕΛΟΣ_ΑΝ
  17.   ΜΕΧΡΙΣ_ΟΤΟΥ input = " "
  18.  
  19.   ΑΝ f = 0 ΤΟΤΕ
  20.     ΓΡΑΨΕ 'ουρά ήδη άδεια, δεν υπάρχουν στοιχεία να εξαχθούν'
  21.   ΑΛΛΙΩΣ
  22.     i <- f
  23.     ΟΣΟ i <= r ΕΠΑΝΑΛΑΒΕ
  24.       ΓΡΑΨΕ Q[i]
  25.       ΚΑΛΕΣΕ deq(Q, f, r)
  26.       i <- i + 1
  27.     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  28.     ΓΡΑΨΕ 'η ουρά άδειασε από όλα τα στοιχεία'
  29.   ΤΕΛΟΣ_ΑΝ
  30. ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
  31.  
  32.  
  33. !=================
  34. ΔΙΑΔΙΚΑΣΙΑ enq(Π, f, r, input)
  35. ΣΤΑΘΕΡΕΣ
  36.   Ν = 10
  37. ΜΕΤΑΒΛΗΤΕΣ
  38.   ΧΑΡΑΚΤΗΡΕΣ: Π[Ν], input
  39.   ΑΚΕΡΑΙΕΣ: f, r, k, i
  40.   ΛΟΓΙΚΕΣ: done
  41. ΑΡΧΗ
  42.   ΑΝ r = Ν ΤΟΤΕ
  43.     ΑΝ f > 1 ΤΟΤΕ ! ΟΛΙΣΘΗΣΗ (μόνο για ερώτημα 2ιι)
  44.       k <- 1
  45.       ΓΙΑ i ΑΠΟ f ΜΕΧΡΙ r
  46.         Π[k] <- Π[i]
  47.         k <- k + 1
  48.       ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  49.       f <- 1
  50.       r <- k
  51.       ΚΑΛΕΣΕ enq(Π, f, r, input)
  52.  !  αναδρομή, ή αλλιώς:
  53.  !   61.  r <- r + 1
  54.  !   62.  Π[r] <- input
  55.       done <- ΑΛΗΘΗΣ
  56.     ΑΛΛΙΩΣ
  57.       ΓΡΑΨΕ 'Ουρά γεμάτη' ! μ2θητή
  58.       done <- ΨΕΥΔΗΣ
  59.     ΤΕΛΟΣ_ΑΝ
  60.   ΑΛΛΙΩΣ
  61.     ΑΝ f = 0 ΤΟΤΕ
  62.       f <- 1
  63.     ΤΕΛΟΣ_ΑΝ
  64.     r <- r + 1
  65.     Π[r] <- input
  66.     done <- ΑΛΗΘΗΣ
  67.   ΤΕΛΟΣ_ΑΝ
  68.   ΓΡΑΨΕ 'έγινε εισαγωγή: ', done
  69. ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
  70. !=================
  71. ΔΙΑΔΙΚΑΣΙΑ deq(Π, f, r)
  72. ΣΤΑΘΕΡΕΣ
  73.   Ν = 10
  74. ΜΕΤΑΒΛΗΤΕΣ
  75.   ΧΑΡΑΚΤΗΡΕΣ: Π[Ν]
  76.   ΑΚΕΡΑΙΕΣ: f, r
  77.   ΛΟΓΙΚΕΣ: done
  78. ΑΡΧΗ
  79.   ΑΝ f < r ΤΟΤΕ
  80.     f <- f + 1
  81.     done <- ΑΛΗΘΗΣ
  82.   ΑΛΛΙΩΣ_ΑΝ f = r ΤΟΤΕ
  83.     ΑΝ r = 0 ΤΟΤΕ
  84.       ΓΡΑΨΕ 'ουρά ήδη άδεια'
  85.       done <- ΨΕΥΔΗΣ
  86.     ΑΛΛΙΩΣ
  87.       f <- 0
  88.       r <- 0
  89.       done <- ΑΛΗΘΗΣ
  90.     ΤΕΛΟΣ_ΑΝ
  91.   ΤΕΛΟΣ_ΑΝ
  92.   ΓΡΑΨΕ 'έγινε εξαγωγή: ', done
  93. ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 948
Απ: Άσκηση Ουρές
« Απάντηση #2 στις: 13 Φεβ 2020, 09:11:40 πμ »
Καλημέρα,
κάτι δεν κατάλαβα... η έξοδος που θα πάρουμε εξαρτάται από την υλοποίηση;
Φιλικά,
Γιώργος Θαλασσινός

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 884
Απ: Άσκηση Ουρές
« Απάντηση #3 στις: 13 Φεβ 2020, 09:27:27 πμ »
Καλημέρα σε όλους

να ρωτήσω και εγώ κάτι γενικά, "ολίσθηση ουράς", από αυτά που έχουν οι λύσεις του βιβλίου, εκτελούμε μόνο όταν ισχύει πίσω=μέγαθος ουράς αλλά υπάρχουν κενές θέσεις στο μπροστά τμήμα ?? δεν θα μπορούσε  κάποιος υλοποιήσει ολίσθηση κάθε φορά που βγαίνει κάποιος από την ουρά (όπως πχ στην τράπεζα, όταν βγαίνει κάποιος μεταφέρονται όλοι ένα βήμα μπροστά) ??? υποθέτω δεν είναι κάτι λάθος έτσι ?? δηλαδή κάτι του στυλ

Αν επιλογή = 'εξαγωγή' τότε
   αν πίσω=0 και εμπρός = 0  τότε
        γράψε 'άδεια'
   αλλιώς_αν εμπρός=πίσω τότε ! εδώ και το σχολικό μεταφέρει μπροστά τους δείκτες μιας που έχουμε ένα στοιχείο και θα αδειάσει η ουρά
         εμπρός<--0
         πίσω<--0
  Αλλιώς
        Για κ από εμπρός+1 μέχρι πίσω
           ουρά[κ-1]<--ουρά[κ]
        τέλος_επανάληψης
        εμπρός<--1
        πίσω<--πίσω-1
   Τέλος_αν
Τέλος_αν







Γιάννης Αναγνωστάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 846
Απ: Άσκηση Ουρές
« Απάντηση #4 στις: 13 Φεβ 2020, 11:48:19 πμ »
Καλημέρα σε όλους

να ρωτήσω και εγώ κάτι γενικά, "ολίσθηση ουράς", από αυτά που έχουν οι λύσεις του βιβλίου, εκτελούμε μόνο όταν ισχύει πίσω=μέγαθος ουράς αλλά υπάρχουν κενές θέσεις στο μπροστά τμήμα ?? δεν θα μπορούσε  κάποιος υλοποιήσει ολίσθηση κάθε φορά που βγαίνει κάποιος από την ουρά (όπως πχ στην τράπεζα, όταν βγαίνει κάποιος μεταφέρονται όλοι ένα βήμα μπροστά) ??? υποθέτω δεν είναι κάτι λάθος έτσι ?? δηλαδή κάτι του στυλ

Αν επιλογή = 'εξαγωγή' τότε
   αν πίσω=0 και εμπρός = 0  τότε
        γράψε 'άδεια'
   αλλιώς_αν εμπρός=πίσω τότε ! εδώ και το σχολικό μεταφέρει μπροστά τους δείκτες μιας που έχουμε ένα στοιχείο και θα αδειάσει η ουρά
         εμπρός<--0
         πίσω<--0
  Αλλιώς
        Για κ από εμπρός+1 μέχρι πίσω
           ουρά[κ-1]<--ουρά[κ]
        τέλος_επανάληψης
        εμπρός<--1
        πίσω<--πίσω-1
   Τέλος_αν
Τέλος_αν

Για μένα φίλε, πρέπει,να το ζητάει ακριβώς η εκφώνηση  ξεκάθαρα.



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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 884
Απ: Άσκηση Ουρές
« Απάντηση #5 στις: 13 Φεβ 2020, 12:01:10 μμ »
Γιάννη ας ελπίσουμε ... γιατί αλλιώς θα δημιουργηθούν προβληματα .. πάντως πιστεύω πως σε όλες αυτές τι υλοποιήσεις δεν τίθεται θέμα "λάθους", τώρα δε βάζω και το χέρι μου στη φωτιά  >:D :police:

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 253
Απ: Άσκηση Ουρές
« Απάντηση #6 στις: 13 Φεβ 2020, 06:32:09 μμ »
Καλημέρα,
κάτι δεν κατάλαβα... η έξοδος που θα πάρουμε εξαρτάται από την υλοποίηση;
Αν η ουρά φτάσει στο τέλος του πίνακα, και δεν προβλέπεται ολίσθηση (ή άλλη ενέργεια), αυτό σημαίνει ότι όλες οι επόμενες εισαγωγές δεν θα γίνουν.
Αν η ουρά φτάσει στο τέλος του πίνακα, και προβλέπεται ολίσθηση, τότε, αν υπάρχει χώρος στο μπροστά μέρος, θα μπορέσουν τελικά να υπάρξουν εισαγωγές, που δεν μπορούσαν στην προηγούμενη περίπτωση.
Υπό αυτή την έννοια, ναι, μπορεί να υπάρξει διαφορετική έξοδος, εφόσον έχουμε διαφορετική υλοποίηση.

@Λαμπράκης Μανώλης και Γιάννης Αναγνωστάκης
Όπως ξέρετε καλά, οι χειρισμοί της κατάστασης, από πλευράς υπουργείου, είναι λανθασμένοι. Απλά λανθασμένοι. Λάθος χειρισμοί, δημιουργούν νέα λάθη με τη σειρά τους.
Φερειπείν, πολλοί λέμε να μπει η Python. Ξαναλέω, αν μπει με τον ίδιο τρόπο που μπήκε η Γλώσσα, δηλαδή κακώς ορισμένα, τότε μια τρύπα στο νερό θα πετύχουμε. Μόνο το ψώνιο ότι κάνουμε python θα μας μείνει. Και αυτό θα γίνει 20 χρόνια μετά την εισαγωγή του μαθήματος... τα σχόλια περιττεύουν.

Προφανώς, μια επίσημη εκφώνηση, θα έπρεπε να περιγράφει τι ακριβώς θέλει. Ωστόσο, όπως έχω ήδη θίξει, το διδακτικό πακέτο, out of nowhere, σε μια ξεκάρφωτη άσκηση (Ε6/34), παραθέτει μια υλοποίηση ολίσθησης, και μάλιστα ούτε καν στο αρχικό "συμπληρωματικό" βιβλίο, αλλά στις προτεινόμενες λύσεις, που "κάποια στιγμή" εστάλησαν. Είναι στον ορισμό/θεωρία των ουρών; όχι. Περιλαμβάνεται στο διδακτικό πακέτο; Ναι. Είναι αυτό αρκετό, για να το πάρουμε ως δεδομένο για μια εκφώνηση άσκησης; Take your chances...

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

Ακόμη και η κωδικοποίηση εισαγωγής και εξαγωγής, από τη στιγμή που περιγράφονται σε "Παραδείγματα" και όχι ορισμούς στο βιβλίο, (θα έπρεπε να) θεωρούνται υλοποιήσιμοι με πολλούς και διαφορετικούς τρόπους. Πολυπλοκότητα/απόδοση; εκτός. Άρα τι θα σου απαγορεύσει να τα λύσεις αλλιώς;
Μπορείς να είσαι σίγουρος, ωστόσο; Νομίζω τα δικά μου μάτια αρκετά έχουν δει ως τώρα, για να φυλάω τα ρούχα μου.. Εσείς, ως εμπειρότεροι, τι λέτε στους μαθητές σας;
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

tsak

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 189
Απ: Άσκηση Ουρές
« Απάντηση #7 στις: 14 Φεβ 2020, 11:21:06 μμ »
Δεν καταλαβαίνω (διορθώσετε με αν κάνω λάθος) γιατί τόση κουβέντα περί ολίσθησης στην ουρά κλπ. Αφού και στην προτεινόμενη κωδικοποίηση και στο λυμένο παράδειγμα του συμπληρωματικού βιβλίου δεν δίνεται κάτι τέτοιο. Όντως η υλοποίηση που προτείνεται δεν είναι η ιδανική, αλλά νομίζω σπέρνουμε λίγο πανικό στην ήδη αινιγματική ας πούμε φετινή ατμόσφαιρα με την αυξημένη ύλη.

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 884
Απ: Άσκηση Ουρές
« Απάντηση #8 στις: 14 Φεβ 2020, 11:32:34 μμ »
Ολίσθηση πραγματοποιεί στην προτεινόμενη λύση της άσκηση Ε.6 του συμπληρωματικού υλικού, δίχως να το αναφέρει κάπου στην εκφώνηση, κάτι που γενικά δημιουργεί ερωτηματικά ..

tsak

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 189
Απ: Άσκηση Ουρές
« Απάντηση #9 στις: 15 Φεβ 2020, 12:03:36 πμ »
Δεν έχω δει την Ε6, αλλά αφού και στις οδηγίες που δίνουν και μάλιστα με την άσκηση της τράπεζας αναφέρουν την λύση χωρίς την κυκλική υλοποίηση, εγώ θα πάρω το "ρίσκο" να μην αναφερθώ καν σ αυτήν. Θεωρώ ότι ένα τέτοιο ζητούμενο θα εγείρει μέχρι και ακύρωση ερωτήματος αν τεθεί. Καλό είναι βέβαια να βγει επιτέλους ένα ενιαίο σύγγραμμα με ακριβέστερες και σαφέστερες υλοποιήσεις.

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 253
Απ: Άσκηση Ουρές
« Απάντηση #10 στις: 15 Φεβ 2020, 02:24:47 πμ »
Δεν έχω δει την Ε6
Όταν την δεις, θα καταλάβεις ότι το πρόβλημα εκεί βρίσκεται: ενώ παντού αποσιωπάται η λογική ολίσθησης, ξαφνικά στην Ε6 λύνει με αυτό το τρόπο, λες και είναι το πιο αναμενόμενο πράγμα. Και μάλιστα χωρίς να το ζητά στην εκφώνηση. Άρα, οι οδηγίες που παραθέτεις, είναι ικανές ή θα μας εκθέσουν στο τέλος;

Ιδού το κείμενο που συνοδεύει τη λύση της Ε6:
Παράθεση
Σημειώνεται ότι, κατά την επίλυση της άσκησης και δεδομένου ότι:
(α) εισέρχονται στην ουρά πολλοί πελάτες προς εξυπηρέτηση και
(β) εξέρχονται από την ουρά πολλοί πελάτες που εξυπηρετήθηκαν,
για να μην υπάρξουν κενές, μη αξιοποιήσιμες, θέσεις στην αρχή της ουράς, υλοποιείται ολίσθηση (shift) των περιεχομένων της ουράς (του πίνακα), ώστε οι κενές θέσεις προς εισαγωγή νέων πελατών να βρίσκονται στο πίσω μέρος της ουράς. Για την περίπτωση αυτή, ελέγχεται αν η τελευταία θέση της ουράς είναι γεμάτη και ταυτόχρονα υπάρχει διαθέσιμη (από προηγούμενη εξαγωγή στοιχείων) τουλάχιστον μία κενή θέση στην αρχή της ουράς. Τότε πραγματοποιείται ολίσθηση.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

tsak

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 189
Απ: Άσκηση Ουρές
« Απάντηση #11 στις: 15 Φεβ 2020, 05:03:24 πμ »
Θα μπορούσε κάλλιστα να γίνει ένα ερώτημα στο Υπουργείο για το αν απαιτείται η γνώση της κυκλικής υλοποίησης τώρα που είναι νωρίς. Αν κάποιος έχει προσβάσεις ή ξέρει πού να αποταθεί, ας βοηθήσει.
Θεωρώ πάντως φέτος που για πρώτη φορά εξετάζονται τόσα νέα πράγματα, ότι το συγκεκριμένο δεν μπορεί και δεν πρέπει να ζητηθεί έτσι όπως δίνουν τον προτεινόμενο κώδικα στη θεωρία.

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 884
Απ: Άσκηση Ουρές
« Απάντηση #12 στις: 15 Φεβ 2020, 07:44:29 πμ »
Όταν την δεις, θα καταλάβεις ότι το πρόβλημα εκεί βρίσκεται: ενώ παντού αποσιωπάται η λογική ολίσθησης, ξαφνικά στην Ε6 λύνει με αυτό το τρόπο, λες και είναι το πιο αναμενόμενο πράγμα. Και μάλιστα χωρίς να το ζητά στην εκφώνηση. Άρα, οι οδηγίες που παραθέτεις, είναι ικανές ή θα μας εκθέσουν στο τέλος;

Καλημέρα σε όλους

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1463
  • There are always possibilities...
Απ: Άσκηση Ουρές
« Απάντηση #13 στις: 15 Φεβ 2020, 09:58:45 πμ »
Δεν καταλαβαίνω (διορθώσετε με αν κάνω λάθος) γιατί τόση κουβέντα περί ολίσθησης στην ουρά κλπ. Αφού και στην προτεινόμενη κωδικοποίηση και στο λυμένο παράδειγμα του συμπληρωματικού βιβλίου δεν δίνεται κάτι τέτοιο. Όντως η υλοποίηση που προτείνεται δεν είναι η ιδανική, αλλά νομίζω σπέρνουμε λίγο πανικό στην ήδη αινιγματική ας πούμε φετινή ατμόσφαιρα με την αυξημένη ύλη.

Θα συμφωνήσω. Προσωπικά θεωρώ την ολίσθηση στην επίλυση της περιβόητης άσκησης, ως τροφή για σκέψη, αφορμή για κάτι παραπάνω, ειδικά επειδή δεν ζητείται στην εκφώνηση, και επειδή δεν γίνεται κάθε φορά αλλά μόνο όταν η ουρά γεμίσει.
Και μάλιστα με αυτό το σκεπτικό δεν το θεωρώ άσχημη ιδέα που μπήκε. Για μένα χειρότεροι είναι οι τόσοι έλεγχοι εγκυρότητας που απομακρύνουν από τον στόχο μιας άσκησης, παρά μία διαφορετική προσέγγιση.
Ας μην είμαστε με το όπλο στο χέρι κάθε φορά που βλέπουμε κάτι διαφορετικό και ας μην θεωρούμε τα διδακτικά πακέτα (και τις λύσεις τους) ως ευαγγέλια...
Η 'επίσημη' υλοποίηση της ουράς παραμενει αυτή του βιβλίου Πληροφορικής (με όλα τα προβλήματα που έχει).
Ο κάθε ένας μας μπορεί να κάνει όποιες παραλλαγές θέλει για να προετοιμάσει καλύτερα, κατά τη γνωμη του, τους μαθητές του (ολίσθηση, κυκλική ουρά), αλλά αν οι θεματοδότες θέλουν κάτι διαφορετικό από την επίσημη υλοποίηση θα πρέπει να το περιγράψουν ρητά, μετατρέποντας έτσι το συγκεκριμένο ερώτημα σε μετατροπή αλγορίθμου από φυσική γλώσσα σε κωδικοποίηση.
« Τελευταία τροποποίηση: 15 Φεβ 2020, 10:12:55 πμ από pgrontas »
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3325
    • P.Tsiotakis
Απ: Άσκηση Ουρές
« Απάντηση #14 στις: 15 Φεβ 2020, 12:24:21 μμ »
Θα μπορούσε κάλλιστα να γίνει ένα ερώτημα στο Υπουργείο για το αν απαιτείται η γνώση της κυκλικής υλοποίησης τώρα που είναι νωρίς. Αν κάποιος έχει προσβάσεις ή ξέρει πού να αποταθεί, ας βοηθήσει.
δεν χρειάζεται να ερωτηθεί το υπουργείο, η υλοποίηση της κυκλικής ουράς δεν είναι γνώση που απαιτείται να γνωρίζουν οι μαθητές.

από την άλλη, πάντοτε μία συμπλήρωση κενού σε κώδικα που περιγράφεται με ελεύθερο κείμενο είναι ένα πιθανό (και όμορφο) θέμα εξέτασης

akalest0s

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 253
Απ: Άσκηση Ουρές
« Απάντηση #15 στις: 15 Φεβ 2020, 12:25:01 μμ »
Το λιγότερο που μπορώ να δεχθώ, είναι ότι έπρεπε η εκφώνηση της Ε6 να το λέει, ή έστω να υπήρχε άλλη εξήγηση στην λύση, από αυτήν που παρέθεσα παραπάνω.
Όπως και να έχει, συμφωνώ και εγώ, το έγραψα και παραπάνω: αν περιγράφεται ρητά η υλοποίηση της ολίσθησης, μπορεί να συμπεριληφθεί στις εξετάσεις. Με την ίδια λογική που μπορεί να ζητήσουν insertionsort αλγόριθμο, ενώ δεν υπάρχει στο βιβλίο.
Από κει και πέρα, εγώ κατ' αρχάς κατέθεσα μια άσκηση/λύση σε ολίσθηση. Το πρόβλημα της Ε6 είχε ήδη θιχτεί από άλλους εδώ μέσα, και δεν είχα σκοπό να κάνω ντόρο, αλλά βγήκε από μόνο του.. ίσως για καλό, ειδικά αν κρίνω την ιδέα του Άλκη στο άλλο θέμα.

υγ> Το ενίοτε υπερβάλλον θυμικό μου, συμπαθάτε το.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

epsilonXi

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 169
Απ: Άσκηση Ουρές
« Απάντηση #16 στις: 15 Φεβ 2020, 08:03:29 μμ »
Καλημέρα σε όλους

να ρωτήσω και εγώ κάτι γενικά, "ολίσθηση ουράς", από αυτά που έχουν οι λύσεις του βιβλίου, εκτελούμε μόνο όταν ισχύει πίσω=μέγαθος ουράς αλλά υπάρχουν κενές θέσεις στο μπροστά τμήμα ?? δεν θα μπορούσε  κάποιος υλοποιήσει ολίσθηση κάθε φορά που βγαίνει κάποιος από την ουρά (όπως πχ στην τράπεζα, όταν βγαίνει κάποιος μεταφέρονται όλοι ένα βήμα μπροστά) ??? υποθέτω δεν είναι κάτι λάθος έτσι ?? δηλαδή κάτι του στυλ


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

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

συνήθως έτσι καταλαβαίνουν ότι δεν είναι ό,τι καλύτερο

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 884
Απ: Άσκηση Ουρές
« Απάντηση #17 στις: 15 Φεβ 2020, 08:29:10 μμ »
τα περισσότερα παιδιά αυτό μού λένε ότι τους φαίνεται «φυσικό», να μετακινούνται όλοι μία θέση μπροστά όταν φύγει ο μπροστινός, όπως συμβαίνει στην πραγματικότητα...

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

συνήθως έτσι καταλαβαίνουν ότι δεν είναι ό,τι καλύτερο

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6150
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Άσκηση Ουρές
« Απάντηση #18 στις: 15 Φεβ 2020, 08:47:08 μμ »
Οι άνθρωποι που προχωρούν μπροστά από μόνοι τους σε μια ουρά τραπέζης, αντιστοιχούν σε Ν επεξεργαστές που ο καθένας κάνει μόνο μια κίνηση. Υπερ-παράλληλος προγραμματισμός.
Εμείς προγραμματίζουμε με έναν επεξεργαστή.
Ας προτείνουμε λοιπόν στον ίδιο τον μαθητή (=1 επεξεργαστής) σε κάθε ολίσθηση να τους κουβαλάει αυτός σαν να είναι κούκλες! Και θα καταλάβει γιατί η υλοποίηση ουράς με ολίσθηση είναι μη αποδοτική! :)
Μάλιστα σε αυτό το παράδειγμα δεν χρειάζεται καν δείκτης front αφού είναι πάντα ίσος με 1.

Ένα πιο δόκιμο παράδειγμα θα ήταν, "αν στην τράπεζα αντί για όρθια ουρά είχαμε 10 καρέκλες, πώς θα οργανώναμε την καθιστή ουρά, ώστε να μην χρειάζεται να αλλάζουν καρέκλα;"
Οι καρέκλες αντιστοιχούν καλύτερα σε υλοποίηση ουρών με πίνακα και χρειάζονται δείκτη front.

Και το το παράδειγμα με τους αριθμούς προτεραιότητας καλούτσικο είναι, αποφεύγει την ολίσθηση. Δυστυχώς όμως προϋποθέτει "πίνακα" με άπειρα στοιχεία, αν θέλουμε να αποφύγουμε να αναφερθούμε στον "κύκλο" του να ξαναμηδενίζονται κάποτε τα νούμερα, όπου τότε γίνεται ισοδύναμο με τις καρέκλες.

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2384
Απ: Άσκηση Ουρές
« Απάντηση #19 στις: 16 Φεβ 2020, 08:33:48 μμ »
...
« Τελευταία τροποποίηση: 16 Φεβ 2020, 11:30:02 μμ από petrosp13 »
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6150
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Άσκηση Ουρές
« Απάντηση #20 στις: 17 Φεβ 2020, 09:00:59 πμ »
Συνάδελφοι όπως ζητήσατε μετέφερα τα μηνύματα που αφορούσαν επικοινωνία με το Υπουργείο κλπ στο Συγκρούσεις-Αντιφάσεις στη Νέα Ύλη 2019.
Αν κατάλαβα ή έκανα κάτι λάθος φωνάξτε. :)

pvs

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 136
Απ: Άσκηση Ουρές
« Απάντηση #21 στις: 02 Δεκ 2020, 10:43:26 πμ »
Θα ήθελα τη βοήθεια σας στο παρακάτω κομμάτι κώδικα. Προσπάθησα να υλοποιήσω την ουρά με ολίσθηση με βάση τον κώδικα του βιβλίου έτσι ώστε στους μαθητές να τους έρθει πιο εύκολο καθώς θα χρειάζεται να μάθουν απλά μία μικρή παραλλαγή. Η ερώτηση μου είναι απλή είναι σωστή η συγκεκριμένη υλοποίηση ή βλέπετε κάπου λάθος? Ευχαριστώ πολύ για το χρόνο σας.
!ΕΣΤΩ ΟΤΙ ΥΠΑΡΧΟΥΝ ΔΕΚΑ ΣΤΟΙΧΕΙΑ ΣΤΗΝ ΟΥΡΑ
FRONT ← 1
REAR ← 10

Αρχή_επανάληψης
  Αν FRONT = 0 και REAR = 0 τότε
    Γράψε 'ΟΥΡΑ ΑΔΕΙΑ'
  αλλιώς_αν FRONT = REAR τότε
    Γράψε 'ΕΞΕΡΧΕΤΑΙ ΤΟ ΣΤΟΙΧΕΙΟ ', Α[FRONT]
    FRONT ← 0
    REAR ← 0
  αλλιώς
    Γράψε 'ΕΞΕΡΧΕΤΑΙ ΤΟ ΣΤΟΙΧΕΙΟ ', Α[FRONT]
    Για Ι από 2 μέχρι REAR !ΜΕΤΑΚΙΝΗΣΗ ΤΩΝ ΣΤΟΙΧΕΙΩΝ ΜΙΑ ΘΕΣΗ ΜΠΡΟΣΤΑ
      Α[Ι - 1] ← Α[Ι]
    Τέλος_επανάληψης
    REAR ← REAR - 1
  Τέλος_αν
Μέχρις_ότου FRONT = 0 και REAR = 0
 

johnk

  • Νέος
  • *
  • Μηνύματα: 7
Απ: Άσκηση Ουρές
« Απάντηση #22 στις: 02 Δεκ 2020, 11:48:15 πμ »
Εγώ έτσι ακριβώς το έκανα και πέρυσι. Θεωρώ πως είναι μια χαρά. Οι λύσεις του βιβλίου είναι πολύ κακογραμμένες.
Απλά μετά τη ΓΙΑ στο Α[rear] εκχωρώ το κενό (αν είναι πίνακας χαρακτήρων) ή το 0 (αν έχει αριθμούς) για να φαίνεται και εντάξει ο πίνακας

pvs

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 136
Απ: Άσκηση Ουρές
« Απάντηση #23 στις: 02 Δεκ 2020, 12:24:06 μμ »
Εγώ έτσι ακριβώς το έκανα και πέρυσι. Θεωρώ πως είναι μια χαρά. Οι λύσεις του βιβλίου είναι πολύ κακογραμμένες.
Απλά μετά τη ΓΙΑ στο Α[rear] εκχωρώ το κενό (αν είναι πίνακας χαρακτήρων) ή το 0 (αν έχει αριθμούς) για να φαίνεται και εντάξει ο πίνακας
Δεν έβαλα " " ή το 0 στη λογική ότι "παίζουμε" με τον rear αλλά θα το χρησιμοποιώ από εδώ και στο εξής

bugman

  • Επισκέπτης
Απ: Άσκηση Ουρές
« Απάντηση #24 στις: 02 Δεκ 2020, 03:30:23 μμ »
Φυσική ερμηνεία της ουράς με ολίσθηση είναι:
1. Ο σωρός της τράπουλας στο καζίνο, που τραβάμε φύλλο από κάτω, και προσθέτουμε από πάνω (πάνω είναι το rear, κάτω το front που έχει "κολλήσει" στο ίδιο νούμερο)
2. Το πατατοθέσιο, στα πολεμικά καράβια, όπου οι πατάτες μπαίνουν σε ένα είδος ντουλάπας, στο πλάι του καταστρώματος, και υπάρχει από πάνω ένα άνοιγμα για να προσθέτεις τις φρέσκιες, και από κάτω ένα άνοιγμα να πάρεις τις παλιές.
3. Σιλό καλαμποκιού και άλλον τροφών για ζώα. Και εδώ η νέα τροφή μπαίνει από πάνω, και η παλιά βγαίνει πρώτη!
Σε κάθε περίπτωση η ολίσθηση γίνεται με την βαρύτητα!
Υπάρχει και η περίπτωση με σπρώξιμο:
4. Γκισέ παραλαβής δίσκου φαγητού σε φοιτητική λέσχη. Αυτό το έχω δει! Σπρώχνουν τους δίσκους και δεν κοιτάνε καν αν τον έπιασε κανείς, γιατί είναι τόσος ο κόσμος που κάποιος θα τον πάρει!
 :D
« Τελευταία τροποποίηση: 02 Δεκ 2020, 11:13:40 μμ από bugman »

George Eco

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 504
Απ: Άσκηση Ουρές
« Απάντηση #25 στις: 04 Δεκ 2020, 12:26:08 πμ »
(υγ> φανταστικοί moderators... ένα υποφόρουμ για στοίβες/ουρές;)


alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6150
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Άσκηση Ουρές
« Απάντηση #26 στις: 04 Δεκ 2020, 06:48:50 πμ »
Εεε..., το φτιάξαμε, το ονομάσαμε "Δομές δεδομένων" αντί για "ουρές/στοίβες", και μετάφεραμε το παρόν μήνυμα σε αυτό. He's right, and we've fixed it half a year ago...

George Eco

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 504
Απ: Άσκηση Ουρές
« Απάντηση #27 στις: 05 Δεκ 2020, 03:03:49 πμ »
Εεε..., το φτιάξαμε, το ονομάσαμε "Δομές δεδομένων" αντί για "ουρές/στοίβες", και μετάφεραμε το παρόν μήνυμα σε αυτό. He's right, and we've fixed it half a year ago...
Θα το επισκευτώ ASAP!