2η Σειρά Ασκήσεων

3. Κατανομή διακριτών αντικειμένων

Θέλουμε να μοιράσουμε τέσσερα ίδια παιχνίδια σε τρία παιδιά (Π1, Π2, Π3). Το παιδί Π1 μπορεί να πάρει οσαδήποτε παιχνίδια από 0 μέχρι 4. Τα υπόλοιπα παιχνίδια θα μοιραστούν στα (υπόλοιπα) παιδιά Π2 και Π3. Πόσοι και ποιοι τρόποι υπάρχουν να μοιραστούν τα παιχνίδια στα παιδιά;

ΠΑΡΑΔΕΙΓΜΑ: Οι κατανομές που ζητάμε είναι (εξαντλητικά):

{0,0,4}	{0,1,3}	{0,2,2}	{0,3,1}	{0,4,0}
{1,0,3}	{1,1,2}	{1,2,1}	{1,3,0}
{2,0,2}	{2,1,1}	{2,2,0}
{3,0,1}	{3,1,0}
{4,0,0}

Σχεδιάστε ένα πρόγραμμα το οποίο να παρουσιάζει (να οπτικοποιεί με όποιο τρόπο επιθυμείτε) τις κατανομές των παιχνιδιών στα παιδιά (είναι δεκτά και τρικ) και να υπολογίζει το πλήθος τους.

Το πρόγραμμα θα πρέπει να είναι παραμετρικό ώστε να αντιμετωπίζει το γενικό πρόβλημα: κατανομή Ν παιχνιδιών σε Μ παιδιά. Δηλαδή ο χρήστης θα πρέπει να δίνει τα Ν και Μ.

4. Πεπερασμένο αυτόματο σε C

Θεωρούμε το αυτόματο του σχήματος το οποίο δέχεται ως είσοδο μια ακολουθία λατινικών χαρακτήρων και ελέγχει την ύπαρξη της διαδοχής "A E O I" μέσα σ' αυτήν. Το αυτόματο αποτελείται από τις καταστάσεις 0, 1, 2, 3 και 4. Η λειτουργία του ξεκινά από την (αρχική) κατάσταση 0 και ανάλογα με τον εισαγόμενο (πρώτο) χαρακτήρα θα ακολουθήσει είτε τη διαδρομή S-A (αν ο χαρακτήρας δεν είναι Α), οπότε παραμένει στην κατάσταση 0, είτε τη διαδρομή A, οπότε μεταβαίνει στην κατάσταση 1 (αν ο χαρακτήρας είναι το Α). Στη συνέχεια διαβάζεται ο δεύτερος χαρακτήρας και το αυτόματο προχωρά ή όχι στην επομένη κατάσταση 2 κ.ο.κ.. Τα βέλη υποδεικνύουν τις μεταβάσεις (απο κατάσταση σε κατάσταση). Το αυτόματο τελειώνει επιτυχώς τον έλεγχο όταν φτάσει στην κατάσταση 4 (τελική) με το τέλος της ακολουθίας εισόδου. Αλιώς, η ακολουθία εισόδου απορρίπτεται (ως μη νόμιμη).

Σημείωση: S-Α ονομάζεται η διαδρομή που ακολουθεί στο σύνολο των κεφαλαίων γραμμάτων πλην του Α, S-Β η διαδρομή που αντιστοιχεί στο σύνολο των γραμμάτων πλην του Β, κ.ο.κ. Τέλος, S είναι το σύνολο των κεφαλαίων γραμμάτων.

Σχεδιάστε ένα πρόγραμμα (σε C) το οποίο να υλοποιεί το αυτόματο αυτό για τον έλεγχο ακολουθιών χαρακτήρων (Ελληνικών λέξεων). Ελέγξτε με το πρόγραμμά σας ακολουθίες (Ελληνικών χαρακτήρων). Π.χ.: AEROPORIA, ANEMEVLOGIA, PANTELONI, KASETOPEIRATEIA κ.λπ. (που νομιμοποιούνται από το αυτόματο) και AEROPOROUS, PARAMYTHI κ.λπ. (που απορρίπτονται).

5. Γραμματική και συχνότητα λέξεων σε Unix

Ερώτημα Α

Σχεδιάστε ένα πρόγραμμα - αρχείο εντολών φλοιού (shell command file) σε Unix, με το οποίο:

Διαβάζεται ένα αρχείο με Αγγλικές λέξεις
Μετατρέπονται τα γράμματα σε κεφαλαία (με χρήση της εντολής tr)
Υλοποιείται το αυτόματο της άσκησης 3 (με χρήση της εντολής egrep)

Σχόλιο: Θα μπορούσε το αυτόματο (Γραμματική) που υλοποιήσατε να "παραγάγει" όλες τις νόμιμες ακολουθίες χαρακτήρων (Λεξιλόγιο) που δέχεται ως νόμιμες; Γιατί;

Ερώτημα Β

Σχεδιάστε ένα πρόγραμμα - αρχείο εντολών φλοιού (shell command file) σε Unix, με το οποίο:

Διαβάζεται ένα αρχείο αγγλικού κειμένου (λατινικοί χαρακτήρες)
Μετατρέπεται αυτό σε ένα αρχείο λέξεων (μία λέξη ανά γραμμή) (με την εντολή tr)
Ταξινομείται αλφαβητικά (με την εντολή sort)
Διαγράφονται οι πολλαπλές εμφανίσεις της ίδιας λέξης (με την εντολή uniq ή στο προηγούμενο βήμα) ενώ, παράλληλα, υπολογίζονται και αποθηκεύονται σε ενδιάμεσο αρχείο (εξόδου) οι συχνότητες εμφάνισης των λέξεων (θα σας χρειαστεί η εντολή tee)
Ελέγχεται η ορθότητα των λέξεων (με την εντολή grep) και οι μη ορθές αποθηκεύονται σε ένα αρχείο εξόδου.

Σχόλιο: Θα εκτιμηθεί θετικά η δυνατότητα του προγράμματος να εμφανίζει μηνύματα προς τον χρήστη στο πρότυπο αρχείο λαθών (/dev/stderr).

6. Πρόγραμμα εξομοίωσης εκδοτηρίου

Σ ένα εκδοτήριο σταθμού του Μητροπολιτικού Σιδηροδρόμου (metro) φτάνουν επιβάτες και μπαίνουν στην ουρά για έκδοση εισιτηρίου κάθε t_αφ (τυχαία τιμή: 0 < t_αφ < 1 min), ενώ κάθε εξυπηρέτηση διαρκεί t_εξ (τυχαία τιμή: 0 < t_εξ < 2 min).

Σχεδιάστε πρόγραμμα εξομοίωσης ενός εκδοτηρίου με τα ακόλουθα επιπλέον δεδομένα και υποδείξεις:

Δημιουργείται μία ουρά: Q (ουρά αναμονής για έκδοση εισιτηρίου)
Μετά από κάθε άφιξη η ουρά μεγαλώνει (Q = Q + 1)
Μετά από κάθε εξυπηρέτηση (έκδοση εισιτηρίου) η ουρά μειώνεται (Q = Q - 1)
Το σύστημα ξεκινά με Q = 5 επιβάτες, t = 0 (τρέχων χρόνος, που "βιώνει" το σύστημά μας)
Η εξυπηρέτηση των γεγονότων εξομοιώνεται ως εξής: η έκδοση εισιτηρίου (ολοκλήρωση του γεγονότος) πραγματοποιείται ("βιώνεται") με t = t + t_εξ (τυχαία τιμή: 0 < t_εξ < 2 min), ενώ η άφιξη με t = t + t_αφ (τυχαία τιμή: 0 < t_αφ < 1 min).
Το πρόγραμμα "δουλεύει" επί 10 ώρες (= 10 x 60 mins = 600 mins)

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

Υπόδειξη: Χρησιμοποιείστε την συνάρτηση rand() για τη δημιουργία τυχαίων αφίξεων και εξυπηρετήσεων. Προκειμένου το σύστημά μας να "βιώσει" ένα γεγονός (εξυπηρέτηση ή άφιξη) ελέγχει το "επόμενο χρονικά γεγονός". Το ποιο γεγονός θα συμβεί κάθε στιγμή καθορίζεται από τη σχέση μεταξύ τους των τιμών t_εξ και t_αφ. Π.χ. : αν το "επόμενο γεγονός" είναι εξυπηρέτηση το σύστημα την "βιώνει" με t = t + t_εξ (όπου t ο τρέχων χρόνος) και Q = Q - 1.

7. Στοίβα (stack) - Αναστροφή Συμβολοακολουθίας (string)

Σχεδιάστε ένα πρόγραμμα C το οποίο εισάγει μια συμβολοακολουθία (μονοδιάστατος πίνακας) σε μια στοίβα (stack) και στη συνέχεια την αναστρέφει (reverse). Το πρόγραμμα θα πρέπει να τυπώνει σε ένα αρχείο εξόδου (out) την αρχική συμβολοακολουθία και την ανάστροφή της, σε δύο διαδοχικές σειρές (γραμμές του αρχείου).

Το πρόγραμμά σας θα πρέπει να ορίζει μια δομή στοίβας, όπως για παράδειγμα:

   typedef struct stack {
      char s[MAX_LEN];
      int top;
   } stack;

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

void reset (stack *stk)
/* αρχικοποίηση της στοίβας : "EMPTY" στην κορυφή */
void push (char c, stack *stk)
/* εισαγωγή χαρακτήρα στην κορυφή της στοίβας */
char pop (stack *stk)
/* αφαίρεση χαρακτήρα από την κορυφή της στοίβας */
char top (const stack *stk)
/* αρχικοποίηση της στοίβας */
boolean empty (const stack *stk)
/* έλεγχος αν η στοίβα είναι άδεια (EMPTY = -1) */
boolean full (const stack *stk)
/* έλεγχος αν η στοίβα είναι γεμάτη (FULL = 1000) */

όπου boolean μπορεί να οριστεί ως νέος τύπος:

   typedef enum {false, true} boolean;

Τελευταία αλλαγή: 01/04/2001 14:57.