ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ Τμήμα Ηλεκτρολόγων Μηχ. και Μηχ. Υπολογιστών Προγραμματιστικές Τεχνικές http://www.softlab.ntua.gr/~nickie/Courses/progtech/

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

8. Δυαδικό Δένδρο - Λεξικό

Σχεδιάστε ένα πρόγραμμα C με το οποίο:

• Διαβάζεται ένας πίνακας words, του οποίου κάθε γραμμή περιέχει μία λέξη μήκους το πολύ Μ γραμμάτων.
• Δημιουργείται ένα δυαδικό δένδρο (lexicon) με στοιχεία το περιεχόμενο του πίνακα των λέξεων (words), που διαβάστηκαν. Κάθε κόμβος πρέπει να περιέχει μία λέξη, το αριστερό παιδί του να έχει αλφαβητικά μικρότερη λέξη και το δεξιό παιδί του αλφαβητικά μεγαλύτερη.
• Καλείται μια συνάρτηση με την οποία εισάγεται μια λέξη, που δίνεται από τον χρήστη, στη σωστή θέση του δένδρου από πλευράς ταξινόμησης (ψάχνουμε για το κατάλληλο υποδένδρο μέχρις ότου συναντηθεί NULL). Η λέξη που δίνει ο χρήστης αν δεν υπάρχει στο δένδρο θα πρέπει εισάγεται σ' αυτό ενώ αν προϋπάρχει τυπώνεται κατάλληλο μήνυμα.
• Tυπώνεται ο αρχικός πίνακας των λέξεων (words).
• Καλείται μια συνάρτηση η οποία επισκέπτεται το δένδρο (lexicon) και τυπώνει τις λέξεις που περιέχει με τη σωστή σειρά ώστε στην εκτύπωση να είναι αλφαβητικά ταξινομημένες.

Υπόδειξη: Αποφασίστε ρεαλιστική τιμή για το Μ. Το Ν να μην είναι μικρότερο του 10.

9. Παιχνίδι με τον Υπολογιστή: "Πέτρα - Ψαλίδι - Χαρτί"

Σχεδιάστε ένα πρόγραμμα C με το οποίο υλοποιείται το παιχνίδι "Πέτρα - Ψαλίδι - Χαρτί". Ο ένας παίκτης είναι ο χρήστης του προγράμματος και ο άλλος ο υπολογιστής (το πρόγραμμά σας).

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

Υποδείξεις:

• Μπορείτε να εξομοιώσετε τις καταστάσεις "Πέτρα", "Ψαλίδι" και "Χαρτί" με τους ακεραίους 0, 1 και 2 αντιστοίχως. Μην ξεχάσετε το ενδεχόμενο χρήστης και υπολογιστής να "παίξουν" το ίδιο (π.χ. Πέτρα ο ένας, Πέτρα και ο άλλος).
• Το πρόγραμμά σας θα πρέπει να παίζει όσο τίμια γίνεται με την κλήση της συνάρτησης παραγωγής ψευδοτυχαίων αριθμών srand(time(NULL)) .Αυτή παράγει διαφορετική σειρά ψευδοτυχαίων αριθμών κάθε φορά που εκτελείται το πρόγραμμα. (Οι συναρτήσεις srand και time περιέχονται στις βιβλιοθήκες <stdlib.h> και <time.h> αντιστοίχως.)

10. Λαβύρινθος - Θησέας - Μινώταυρος

Ο Θησέας θέλει να μπει στον Λαβύρινθο και να σκοτώσει τον Μινώταυρο χρησιμοποιώντας τον μίτο που του έδωσε η Αριάδνη για να μη χάσει την είσοδο/έξοδο. Ο Λαβύρινθος εξομοιώνεται από έναν πίνακα Λ[10, 10]. Κάθε στοιχείο (θέση) του πίνακα αυτού μπορεί να είναι 'κενό', ή να περιέχει έναν από τους χαρακτήρες: 'Κ' (κλωστή=μίτος), 'Τ' (τοίχος), 'Μ' (Μινώταυρος). Θεωρούμε ότι ο Θησέας μπαίνει στον Λαβύρινθο από τη θέση Λ[1,1] και ψάχνει συστηματικά όλες τις θέσεις του Λ να βρει τον Μινώταυρο, ξετυλίγοντας τον μίτο (απ' όπου περνά βάζει 'Κ' στο αντίστοιχο στοιχείο του Λ). Στα όρια του Λ υπάρχει τοίχος ('Τ'), ενώ 'Μ' (ο Μινώταυρος) υπάρχει μόνο σε ένα στοιχείο του Λ (στόχος που πρέπει να επιτευχθεί).

Σχεδιάστε ένα πρόγραμμα C με το οποίο διαβάζεται από ένα αρχείο ο Λαβίρυνθος Λ[10,10], και υλοποιείται το ψάξιμο του Μινώταυρου μέσα στον Λαβύρινθο με αναδρομική συνάρτηση. Η συνάρτηση αυτή θα καλείται μία φορά με την πληροφορία της αρχικής θέσης Λ[1,1] του Θησέα.

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

Υποδείξεις:

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

Τ	Τ	Τ	Τ	Τ	Τ	Τ	Τ	Τ	Τ
Τ		Τ							Τ
Τ		Τ		Τ	Τ	Τ	Τ		Τ
Τ		Τ			Μ	Τ	Τ		Τ
Τ		Τ	Τ	Τ	Τ	Τ			Τ
Τ						Τ		Τ	Τ
Τ		Τ	Τ	Τ					Τ
Τ				Τ		Τ	Τ		Τ
Τ				Τ					Τ
Τ	Τ	Τ	Τ	Τ	Τ	Τ	Τ	Τ	Τ

• Το κίτρινο τετράγωνο είναι η αρχική θέση του Θησέα στο λαβύρινθο και δεν πρέπει να καταλαμβάνεται από τοίχο.
• Ο λόγος ύπαρξης του μίτου (χαρακτήρας 'Κ') είναι για να ξέρει ο Θησέας ότι έχει ήδη επισκεφθεί μια θέση του λαβύρινθου και να αποφύγει να ξαναπεράσει από αυτή.
• Για την επίλυση του προβλήματος ενδείκνυται η χρήση αναδρομής.
• Σε κάθε θέση, ο Θησέας έχει διαθέσιμες το πολύ τέσσερις διαφορετικές κατευθύνσεις για να κινηθεί: πάνω, κάτω, αριστερά και δεξιά. Από αυτές πρέπει να αποκλείει όσες καταλαμβάνονται από 'Τ' ή 'Κ'. Αν απομένουν περισσότερες από μια δυνατές κατευθύνσεις, τότε μπορεί να επιλέγει τυχαία. Αν δεν απομένει καμια δυνατή κατεύθυνση (αδιέξοδο) τότε με χρήση αναδρομής ο Θησέας μπορεί να επιστρέφει σε προηγούμενες θέσεις όπου και να επιλέγει εναλλακτικές διαδρομές που είχε απορρίψει.

11. Προγραμματισμός φλοιού Unix

Σχεδιάστε ένα πρόγραμμα για τον φλοιό (shell) του Unix με το οποίο:

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

Σχεδιάστε πρόγραμμα C το οποίο εκτελεί το προηγούμενο πρόγραμμα φλοιού.