Γενικό Λύκειο > Δομές δεδομένων

Άσκηση Ουρές

(1/6) > >>

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

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


(Εμπνεύστηκα την άσκηση από την συνημμένη εικόνα, στο βιβλίο "Αλγόριθμοι σε C", R. Sedgewick.)
(υγ> φανταστικοί moderators... ένα υποφόρουμ για στοίβες/ουρές;)

akalest0s:
και μια λύση..


--- Κώδικας: Javascript ---ΠΡΟΓΡΑΜΜΑ μο_ουρά_ακολουθία_χαρακτήρωνΣΤΑΘΕΡΕΣ  Ν = 10ΜΕΤΑΒΛΗΤΕΣ  ΧΑΡΑΚΤΗΡΕΣ: Q[Ν], input  ΑΚΕΡΑΙΕΣ: f, r, iΑΡΧΗ  f <- 0  r <- 0  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ    ΔΙΑΒΑΣΕ input    ΑΝ input = '*' ΤΟΤΕ      ΚΑΛΕΣΕ deq(Q, f, r)     ΑΛΛΙΩΣ_ΑΝ input <> ' ' ΤΟΤΕ !μην καλείς την enq για " "      ΚΑΛΕΣΕ enq(Q, f, r, input)     ΤΕΛΟΣ_ΑΝ  ΜΕΧΡΙΣ_ΟΤΟΥ input = " "   ΑΝ f = 0 ΤΟΤΕ    ΓΡΑΨΕ 'ουρά ήδη άδεια, δεν υπάρχουν στοιχεία να εξαχθούν'  ΑΛΛΙΩΣ    i <- f    ΟΣΟ i <= r ΕΠΑΝΑΛΑΒΕ      ΓΡΑΨΕ Q[i]       ΚΑΛΕΣΕ deq(Q, f, r)       i <- i + 1    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ    ΓΡΑΨΕ 'η ουρά άδειασε από όλα τα στοιχεία'  ΤΕΛΟΣ_ΑΝΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ  !=================ΔΙΑΔΙΚΑΣΙΑ enq(Π, f, r, input) ΣΤΑΘΕΡΕΣ  Ν = 10ΜΕΤΑΒΛΗΤΕΣ  ΧΑΡΑΚΤΗΡΕΣ: Π[Ν], input  ΑΚΕΡΑΙΕΣ: f, r, k, i  ΛΟΓΙΚΕΣ: doneΑΡΧΗ  ΑΝ r = Ν ΤΟΤΕ    ΑΝ f > 1 ΤΟΤΕ ! ΟΛΙΣΘΗΣΗ (μόνο για ερώτημα 2ιι)      k <- 1      ΓΙΑ i ΑΠΟ f ΜΕΧΡΙ r        Π[k] <- Π[i]         k <- k + 1      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ      f <- 1      r <- k      ΚΑΛΕΣΕ enq(Π, f, r, input)  !  αναδρομή, ή αλλιώς: !   61.  r <- r + 1 !   62.  Π[r] <- input      done <- ΑΛΗΘΗΣ    ΑΛΛΙΩΣ      ΓΡΑΨΕ 'Ουρά γεμάτη' ! μ2θητή      done <- ΨΕΥΔΗΣ    ΤΕΛΟΣ_ΑΝ  ΑΛΛΙΩΣ    ΑΝ f = 0 ΤΟΤΕ      f <- 1    ΤΕΛΟΣ_ΑΝ    r <- r + 1    Π[r] <- input    done <- ΑΛΗΘΗΣ  ΤΕΛΟΣ_ΑΝ  ΓΡΑΨΕ 'έγινε εισαγωγή: ', doneΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ!=================ΔΙΑΔΙΚΑΣΙΑ deq(Π, f, r) ΣΤΑΘΕΡΕΣ  Ν = 10ΜΕΤΑΒΛΗΤΕΣ  ΧΑΡΑΚΤΗΡΕΣ: Π[Ν]   ΑΚΕΡΑΙΕΣ: f, r  ΛΟΓΙΚΕΣ: doneΑΡΧΗ  ΑΝ f < r ΤΟΤΕ    f <- f + 1    done <- ΑΛΗΘΗΣ  ΑΛΛΙΩΣ_ΑΝ f = r ΤΟΤΕ    ΑΝ r = 0 ΤΟΤΕ      ΓΡΑΨΕ 'ουρά ήδη άδεια'      done <- ΨΕΥΔΗΣ    ΑΛΛΙΩΣ      f <- 0      r <- 0      done <- ΑΛΗΘΗΣ    ΤΕΛΟΣ_ΑΝ  ΤΕΛΟΣ_ΑΝ  ΓΡΑΨΕ 'έγινε εξαγωγή: ', doneΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

gthal:
Καλημέρα,
κάτι δεν κατάλαβα... η έξοδος που θα πάρουμε εξαρτάται από την υλοποίηση;

Λαμπράκης Μανώλης:
Καλημέρα σε όλους

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

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






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

--- Παράθεση από: Λαμπράκης Μανώλης στις 13 Φεβ 2020, 09:27:27 πμ ---Καλημέρα σε όλους

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

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

--- Τέλος παράθεσης ---

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


Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση