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

Yποδείξεις για τη σύνταξη και εκτέλεση προγραμμάτων στο Unix.

1. Προγραμματιστικές Ενότητες (modules) - Αναδρομικές Συναρτήσεις

α. Για το υπολογισμό της συνάρτησης "παραγοντικό" σχεδιάστε δύο υλοποιήσεις, σε δύο διαφορετικά αρχεία υλοποιήσεων: "fact1.c" και "fact2.c". Στο πρώτο αρχείο θα περιέχεται η συνάρτηση υπολογισμού με επαναλήψεις και στο δεύτερο η αναδρομική συνάρτηση υπολογισμού. Το αρχείο "main.c" (αρχείο χρήσης) θα χρησιμοποιεί μία υλοποίηση κάθε φορά, προκειμένου να διαβάσει έναν αριθμό που θα δώσει ο χρήστης και αφού υπολογίσει το παραγοντικό του θα τυπώσει το αποτέλεσμα. Π.χ. Αν ο χρήστης δώσει 4, θα πρέπει να τυπώνεται: (4)! = 24. Το πρόγραμμμά σας πρέπει να τυπώνει κατάλληλα μηνύματα ενημέρωσης προς τον χρήστη και παράλληλα να "αμύνεται" ελέγχοντας τα δεδομένα εισόδου, ώστε κατά την εκτέλεση να μη σταματήσει ανώμαλα (abnormal stop).

/* αρχείο "fact1.c"
    με επαναλήψεις  */
int fact(int n)
{
   ...
}

/* αρχείο "fact2.c" με
    αναδρομική συνάρτηση */
int fact(int n)
{
   ...
}

/* αρχείο χρήσης "main.c" */
#include <stdio.h>
#include "fact1.c"
int main ()
{
   ...
   /* διαβάζουμε δεδομένα,
      καλούμε τη
         συνάρτηση "fact",
      τυπώνουμε τα
         αποτελέσματα  */
   return 0;
}

β. Εργαστείτε με τον ίδιο τρόπο για τον υπολογισμό τυχαίου αριθμού της ακολουθίας Fibonacci:

f(0) = 0, f(1) = 1, f(i+1) = f(i) + f(i-1) για i-1,2,...

Δηλαδή, για τον υπολογισμό σχεδιάστε δύο υλοποιήσεις: μία με επαναλήψεις και μία με αναδρομική συνάρτηση. Σχολιάστε την απόδοση των αλγορίθμων των δύο υλοποιήσεων.

2. Μονοδιάστατος Πίνακας - Ταξινόμηση

Μας δίνουν έναν πίνακα list[length], length > 0, ο οποίος περιέχει μια ακολουθία ακεραίων, ταξινομημένη σε αύξουσα ή φθίνουσα σειρά.

α. Γράψτε μια συνάρτηση η οποία διαβάζει ένα νέο ακέραιο (element) και τον εισάγει στον πίνακα έτσι ώστε η ακολουθία των αριθμών του πίνακα, να παραμένει ταξινομημένη.

 void insert(int list[], int length, int element)

β. Γράψτε μια συνάρτηση η οποία αναζητά έναν ακέραιο (element), μέσα στον πίνακα, και αν τον βρει τον αφαιρεί (delete) από τον πίνακα. Η συνάρτηση αφαιρεί την πρώτη εμφάνιση του στοιχείου που ψάχνει και επιστρέφει 0 (false) αν δεν βρεθεί ή 1 (true) αν βρεθεί.

 int remove(int list[], int length, int element)

γ. Γράψτε μια συνάρτηση η οποία αναζητά έναν ακέραιο (μέσα στον πίνακα) και αν δεν τον βρει τον εισάγει (insert). Η συνάρτηση επιστρέφει 0 (false) αν ο αριθμός υπάρχει ή 1 (true) αν εισαχθεί ο αριθμός.

 int insert(int list[], int length, int element)

δ. Υλοποιήστε τον αλγόριθμο δυαδικής αναζήτησης (binary search).

int bin_search(int list[], int length, int element)

Για να ελέγξετε τις συναρτήσεις αυτές γράψτε ένα μικρό πρόγραμμα χρήσης για κάθε μία ή εναλλακτικά ένα για όλες. Ειδικότερα, για την συνάρτηση δυαδικής αναζήτησης χρησιμοποιήστε τη συνάρτηση 'β' (πιο πάνω) για να διαβάσετε (την δίνει ο χρήστης) μια ταξινομημένη ακολουθία ακεραίων.

Θα σας χρειαστεί και μία συνάρτηση (διαδικασία) εκτύπωσης του πίνακα.

 void print_list(int list[], int length)

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

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

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

Σχεδιάστε:

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

(Προαιρετικά:) Μπορεί κάπως να αποτυπωθεί η επιτυχής διαδρομή αναζήτησης και να παρουσιαστεί;

Υπόδειξη:

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

Επιπρόσθετες υποδείξεις:

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

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Μ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Τ

Το κίτρινο τετράγωνο είναι η αρχική θέση του Θησέα στο λαβύρινθο και δεν πρέπει να καταλαμβάνεται από τοίχο.

Ο λόγος ύπαρξης του μίτου (χαρακτήρας 'Κ') είναι για να ξέρει ο Θησέας ότι έχει ήδη επισκεφθεί μια θέση του λαβύρινθου και να αποφύγει να ξαναπεράσει από αυτή.

Για την επίλυση του προβλήματος ενδείκνυται η χρήση αναδρομής.

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

Τελευταία αλλαγή: 16/03/2002 1:16.

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

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

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