ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ
Τμήμα Ηλεκτρολόγων Μηχ. και Μηχ. Υπολογιστών

Προγραμματιστικές Τεχνικές
http://www.softlab.ntua.gr/~nickie/Courses/progtech/

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, με το οποίο:

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

Ερώτημα Β

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

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

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

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

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

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

Υπόδειξη: Χρησιμοποιείστε την συνάρτηση 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:

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

   typedef enum {false, true} boolean;


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