irodis: Προγράμματα σε C

Προγράμματα σε C

1o Πρόγραμμα σε C: Διαχείριση συμβολοσειρών

Υλοποιήστε μια συνάρτηση int position(string1, string2) που επιστρέφει την πρώτη θέση του αλφαριθμητικού string1 στην οποία βρίσκεται οποιοσδήποτε από τους χαρακτήρες του string2, ή -1 αν το αλφαριθμητικό string1 δεν περιέχει κανένα από τους χαρακτήρες του αλφαριθμητικού string2. Για παράδειγμα:

Εάν η συνάρτηση κληθεί με ορίσματα «Πέτρος» και «Πέτρα» θα πρέπει να επιστρέψει τον αριθμό 0.
Εάν η συνάρτηση κληθεί με ορίσματα «Γραπτή» και «Εργασία» θα πρέπει να επιστρέφει τον αριθμό 1.
Εάν η συνάρτηση κληθεί με ορίσματα «Ελληνικό» και «Πάτρα» θα πρέπει να επιστρέψει τον αριθμό -1.

Σημείωση: Στον κώδικα που θα υλοποιήσετε να μη χρησιμοποιήσετε καμία από τις έτοιμες συναρτήσεις της βιβλιοθήκης string.h

Λύση

Η λύση είναι στο αρχείο ask1.c

2o Πρόγραμμα σε C: Διαχείριση αντίστροφης Πολωνικής σημειογραφίας

Υλοποιήστε ένα πρόγραμμα το οποίο να υπολογίζει την τιμή παραστάσεων που βρίσκονται σε αντίστροφη Πολωνική σημειογραφία. Πληροφορίες για την αντίστροφη Πολωνική σημειογραφία μπορείτε να βρείτε μεταξύ άλλων στην ιστοσελίδα http://en.wikipedia.org/wiki/Reverse_Polish_Notation.

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

Για παράδειγμα:

·η εκτέλεση του προγράμματος polish_calculate 4 9 + θα πρέπει να υπολογίζει την παράσταση 4+9 και να εμφανίζει στην οθόνη το αποτέλεσμα, δηλαδή τον αριθμό 13.
η εκτέλεση του προγράμματος polish_calculate 4 9 2 + * θα πρέπει να υπολογίζει την παράσταση 4*(9+2) και να εμφανίζει στην οθόνη το αποτέλεσμα, δηλαδή τον αριθμό 44.

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

η εκτέλεση του προγράμματος polish_calculate 4 + 9 θα πρέπει να εμφανίζει αντίστοιχο μήνυμα λάθους (η είσοδος δεν είναι σε αντίστροφη Πολωνική μορφή).
η εκτέλεση του προγράμματος polish_calculate 4 9 + - θα πρέπει να εμφανίζει αντίστοιχο μήνυμα λάθους (οι τελεστές είναι περισσότεροι).
η εκτέλεση του προγράμματος polish_calculate 5 6 4 9 + - θα πρέπει να εμφανίζει αντίστοιχο μήνυμα λάθους (οι τελεστέοι είναι περισσότεροι).
η εκτέλεση του προγράμματος polish_calculate 4 a + - θα πρέπει να εμφανίζει αντίστοιχο μήνυμα λάθους (υπάρχει στην είσοδο μη έγκυρος χαρακτήρας).
η εκτέλεση του προγράμματος polish_calculate 4 9+ ή polish_calculate 4- 9 θα πρέπει να εμφανίζει αντίστοιχο μήνυμα λάθους (τελεστέοι και τελεστές δε διαχωρίζονται με κενό).

Λύση

Η λύση είναι στο αρχείο ask2.c

3o Πρόγραμμα σε C: Σύγκριση αρχείων

Κατασκευάστε ένα πρόγραμμα το οποίο να δέχεται ως ορίσματα δύο αρχεία κειμένου και να εμφανίζει στην οθόνη την πρώτη γραμμή στην οποία τα δύο αυτά αρχεία διαφέρουν. Στη σύγκριση των περιεχομένων των γραμμών των δύο αρχείων να λάβετε υπόψη σας ότι οι κεφαλαίοι και οι πεζοί γραμματικοί χαρακτήρες είναι διαφορετικοί.

Το πρόγραμμα σε περίπτωση που βρει κάποια γραμμή στην οποία τα δύο αρχεία διαφέρουν θα πρέπει να εμφανίζει στην οθόνη τα εξής:

File: <όνομα αρχείου 1> - Line: <αριθμός γραμμής> - Content: <περιεχόμενο γραμμής>
File: <όνομα αρχείου 2> - Line: <αριθμός γραμμής> - Content: <περιεχόμενο γραμμής>

Π.χ. εάν θέλουμε να συγκρίνουμε τα αρχεία a.txt και b.txt και αυτά διαφέρουν στην τρίτη γραμμή το πρόγραμμα θα πρέπει να εμφανίζει στην οθόνη τα εξής:

File: a.txt - Line: 3 - Content: xxxx

File: b.txt - Line: 3 - Content: yyyy

όπου xxxx είναι το περιεχόμενο της τρίτης γραμμής του αρχείου a.txt και yyyy είναι το περιεχόμενο της τρίτης γραμμής του αρχείου b.txt.

Σε περίπτωση που τα δύο αυτά αρχεία είναι όμοια θα πρέπει να εμφανίζεται κατάλληλο μήνυμα στην οθόνη.

Π.χ. File a.txt and file b.txt have the same content.

Θεωρείστε ότι ο μέγιστος αριθμός χαρακτήρων που μπορούν να είναι γραμμένοι σε μία γραμμή ενός αρχείου είναι 1000.

Λύση

Η λύση είναι στο αρχείο ask3.c

4o Πρόγραμμα σε C: Ανίχνευση Μαγικού Τετραγώνου 3Χ3

Στο συγκεκριμένο θέμα σας ζητάμε να κατασκευάστε ένα πρόγραμμα το οποίο θα ανιχνεύει την ύπαρξη μαγικού τετραγώνου με διαστάσεις 3Χ3.

Πληροφορίες για τις ιδιότητες του μαγικού τετραγώνου μπορείτε να βρείτε μεταξύ άλλων στην ιστοσελίδα http://en.wikipedia.org/wiki/Magic_square.

Πιο συγκεκριμένα, το πρόγραμμα θα πρέπει να κάνει τα εξής:

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

Λύση

Η λύση είναι στο αρχείο ask4.c

5o Πρόγραμμα σε C: Ανίχνευση Μαγικού Τετραγώνου με δυναμικές διαστάσεις

Τροποποιήστε το 4o πρόγραμμα, έτσι ώστε η διάσταση του μαγικού τετραγώνου να δίνεται από το χρήστη.

Πιο συγκεκριμένα το πρόγραμμα θα πρέπει να κάνει τα εξής:

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

Λύση

Η λύση είναι στο αρχείο ask5.c

6o Πρόγραμμα σε C: merge sort με κατώφλι διάσπασης Μ

Μία παραλλαγή του αλγορίθμου merge sort είναι ο merge sort με κατώφλι διάσπασης Μ. Ο αλγόριθμος αυτός λειτουργεί ως εξής: κατά την αναδρομική εκτέλεση του αλγορίθμου, αν οι υποπίνακες έχουν αριθμό στοιχείων μικρότερο ή ίσο με Μ (που καλείται κατώφλι διάσπασης – cutoff value), τότε οι υποπίνακες αυτοί ταξινομούνται με insertion sort και όχι με merge sort. Υλοποιήσετε αυτή την εκδοχή του merge sort. Θεωρείστε την τιμή cutoff σταθερά του προγράμματός σας.

Λύση

Η λύση είναι στο αρχείο ask6.c

7o Πρόγραμμα σε C: Ουρά διπλού τερματισμού

Ο σωρός (stack) επιτρέπει την εισαγωγή και διαγραφή στοιχείων από το ένα «άκρο» της δομής, η ουρά (queue) επιτρέπει την εισαγωγή στο ένα άκρο και τη διαγραφή από το άλλο άκρο. Η ουρά διπλού τερματισμού (double-ended queue, dequeue) επιτρέπει εισαγωγή και διαγραφή και από τα δυο άκρα.

Γράψτε σε C τέσσερις διαδικασίες για εισαγωγή και διαγραφή στοιχείων από τα δυο άκρα της dequeue.

Λύση

Η λύση είναι στο αρχείο ask7.c

8o Πρόγραμμα σε C: Αναπαράσταση πολυωνύμων με συνδεδεμένη λίστα, άθροισμα πολυωνύμων

Θεωρήστε πολυώνυμα πολλών μεταβλητών, π.χ.

Χρησιμοποιήστε κυκλική απλά συνδεδεμένη λίστα (circular list) για να αναπαραστήσετε πο-λυώνυμα μέχρι τριών μεταβλητών (x,y,z). Θεωρήστε ότι κάθε κόμβος της λίστας κρατά πληροφορία για ένα όρο του πολυωνύμου ως εξής (σχηματικά):

Συντελεστής COEF
Symbol	Α	Β	C	Δείκτης

Ο συντελεστής COEF μπορεί να είναι αρνητικός (όπως το -4 στο πολυώνυμο πιο πάνω) ή θετικός. Το Symbol που εμφανίζεται ως πεδίο του κόμβου είναι πάντα +, εκτός από τον «τελικό» κόμβο του πολυωνύμου όπου θέτουμε

Symbol= −

Α=Β=C=1

COEF=0.

Oι κόμβοι διατάσσονται κατά την κατεύθυνση των δεικτών κατά φθίνουσα σειρά του αθροίσματος των Α,Β,C, λαμβάνοντας υπόψη και το πρόσημο. Έτσι ο «τελικός» κόμβος είναι τελευταίος στη διάταξη αυτή, και ο δείκτης του δείχνει στον πρώτο κόμβο (με το μεγαλύτερο άθροισμα Α+Β+C), δημιουργώντας κυκλική λίστα.

Α. Γράψτε πρόγραμμα που παίρνει από την οθόνη τιμές για τους συντελεστές και τους εκθέτες των όρων του πολυωνύμου και αποθηκεύει το πολυώνυμο σε κυκλική λίστα ως ανωτέρω. Η εισαγωγή των όρων δεν γίνεται απαραίτητα κατά φθίνουσα σειρά του Α+Β+C. H εισαγωγή κάθε πολυωνύμου τερματίζεται με την εισαγωγή όρου με συντελεστή 0. Το πρόγραμμα πρέπει να επιτρέπει τη διαδοχική εισαγωγή περισσότερων του ενός πολυωνύμων αν ο χρήστης το επιθυμεί.

Β. Γράψτε πρόγραμμα που να δέχεται δυο πολυώνυμα Π1, Π2, τα αναπαριστά (με τη χρήση του κώδικα που γράφτηκε για το μέρος Α) ως λίστες στις οποίες έχουμε πρόσβαση μέσω δεικτών P1, P2 και κάνει το άθροισμα τoυς, το οποίο αποθηκεύεται στη λίστα P2 (δηλ η P1 δεν επηρεάζεται.)

Λύση

Η λύση για το Α είναι στο αρχείο ask8a.c και για το Β στο ask8b.c

9o Πρόγραμμα σε C: depth first search

Υλοποιήστε ένα πρόγραμμα το οποίο εκτελεί τον depth first search αλγόριθμο στον ακόλουθο γράφο τον οποίο να αναπαραστήσετε με χρήση αναπαράστασης πίνακα (adjacency matrix) και εκτυπώνει την σειρά επίσκεψης των κορυφών (από 0 έως 11).

1 1 1 0 0 1 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 0 0 0 0 0 0

0 0 1 1 1 0 0 0 0 0 0 0

0 0 1 1 1 0 0 0 1 0 0 0

1 0 1 0 0 1 1 1 0 0 0 0

0 0 0 0 0 1 1 0 0 0 0 0

0 0 0 0 0 1 0 1 0 1 0 0

0 0 0 0 1 0 0 0 1 0 1 0

0 0 0 0 0 0 0 1 0 1 1 0

0 0 0 0 0 0 0 0 1 1 1 1

0 0 0 0 0 0 0 0 0 0 1 1

Λύση

Η λύση είναι στο αρχείο ask9.c

10o Πρόγραμμα σε C: Οι γέφυρες του Konigsberg

Η πόλη του Konigsberg ήταν ένα Γερμανικό λιμάνι στην Βαλτική. Είχε επτά γέφυρες οι οποίες περνούσαν το ποταμό Preger. Οι κάτοικοι είχαν συχνά την ακόλουθη απορία, αν μπορούν να περπατήσουν σε κάθε γέφυρα ακριβώς μια φορά και να καταλήξουν πίσω στην αρχή που ξεκίνησαν. (http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg)

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

Είσοδος: Κάθε γέφυρα έχει ένα όνομα μέχρι 19 χαρακτήρες. Οι περιοχές της πόλης είναι αριθμημένες με συνεχόμενους αριθμούς ακεραίους ξεκινώντας από το 1. Ο χρήστης θα εισάγει τα δεδομένα για τις γέφυρες στην ακόλουθη μορφή

Bridgename distinct1 distinct 2

Όπου το bridgename είναι το όνομα της γέφυρας και distinct1 και distinct2 είναι τα νούμερα των δύο περιοχών τα οποία ενώνει η γέφυρα.

Υποθέσεις

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

Έξοδος: Αν το πρόγραμμα δεν μπορεί να βρει μονοπάτι θα βγάζει το μήνυμα no path found αλλιώς θα πρέπει να τυπώνει τις γέφυρες με την σειρά που θα πρέπει να τις διασχίσουμε. Οι γέφυρες να τυπώνονται σε μια γραμμή με ένα κενό ανάμεσα τους. Μπορεί το πρόγραμμα να τυπώνει και ότι άλλα μηνύματα κρίνετε απαραίτητο.

Παράδειγμα:

Enter bridges in the following format

Bridgename distinct 1 distinct 2

(there are 4 distincts)

Enter “done” for the bridge name to stop

Kraemer 1 2

Gruene 2 4

Schmiede 1 2

Holz 1 3

Honig 3 2

Koettel 4 2

Hohe 3 4

done 0 0

Λύση

Η λύση είναι στο αρχείο ask10.c