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

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

1. Υπολογισμός μήκους ευθύγραμμου τμήματος

Να κατασκευάσετε μια συνάρτηση length η οποία να δέχεται ως ορίσματα τις καρτεσιανές συντεταγμένες δύο σημείων Α(x₁, y₁) και Β(x₂, y₂) στο επίπεδο και να επιστρέφει το μήκος του ευθύγραμμου τμήματος ΑΒ. Τόσο οι συντεταγμένες όσο και το μήκος πρέπει να είναι πραγματικοί αριθμοί. Ο υπολογισμός του μήκους να γίνεται με χρήση του Πυθαγορείου θεωρήματος.

Να χρησιμοποιήσετε τη length καλώντας την από ένα κύριο πρόγραμμα, το οποίο να διαβάζει από το πληκτρολόγιο τις συντεταγμένες x₁, y₁, x₂, y₂, να καλεί τη συνάρτηση length με αυτές ως παραμέτρους και να τυπώνει το αποτέλεσμα που επιστρέφει η συνάρτηση. Η διαδικασία αυτή να επαναλαμβάνεται μέχρις ότου δοθούν σημεία που ταυτίζονται.

Σημείωση: Θα σας χρειαστεί η συνάρτηση sqrt που υπολογίζει την τετραγωνική ρίζα πραγματικών αριθμών και βρίσκεται στο αρχείο επικεφαλίδας <math.h>. Επίσης, θα χρειαστεί να προσθέσετε την παράμετρο -lm στο τέλος της εντολής μεταγλώττισης (βιβλιοθήκη μαθηματικών συναρτήσεων της C).

Λύση: ex2-1.c

2. Υπολογισμός εμβαδού τριγώνου με τον τύπο του Ήρωνα

Δίνονται οι συντεταγμένες των κορυφών ενός τριγώνου ΑΒC, όπως στο διπλανό σχήμα. Να κατασκευάσετε τη συνάρτηση area η οποία να δέχεται ως παραμέτρους τις τιμές των συντεταγμένων x₁, y₁, x₂, y₂, x₃, y₃, και να επιστρέφει το εμβαδόν του τριγώνου ΑΒC χρησιμοποιώντας τον τύπο του Ήρωνα:

όπου a, b και c είναι τα μήκη των πλευρών BC, AC και AB αντίστοιχα, τα οποία μπορείτε να υπολογίσετε καλώντας τη συνάρτηση length που έχετε κατασκευάσει στην άσκηση 1.

Να χρησιμοποιήσετε την area καλώντας την από ένα κύριο πρόγραμμα το οποίο να διαβάζει από το πληκτρολόγιο τις συντεταγμένες x₁, y₁, x₂, y₂, x₃, y₃, να καλεί τη συνάρτηση area με αυτές ως παραμέτρους και να τυπώνει το αποτέλεσμα που επιστρέφει η συνάρτηση. Η διαδικασία αυτή να επαναλαμβάνεται μέχρις ότου το εμβαδόν είναι μηδέν.

Λύση: ex2-2.c

3. Στατιστική σε πίνακα με τυχαίους αριθμούς

Να κατασκευάσετε ένα πρόγραμμα το οποίο να γεμίζει με τυχαίες ακέραιες τιμές μεταξύ 0 και Ì, έναν τετραγωνικό πίνακα r διαστάσεων N × N. Θεωρήστε ότι τα Ì και Í είναι σταθερές του προγράμματος. Στη συνέχεια, το πρόγραμμα να υπολογίζει και να εκτυπώνει τα ακόλουθα:

• Τη συχνότητα εμφάνισης κάθε τιμής στον πίνακα r, δηλαδή πόσες φορές κάθε τιμή εμφανίζεται στον πίνακα. Θα χρειαστείτε ένα δεύτερο μονοδιάστατο πίνακα freq με M+1 στοιχεία.
• Τη μέση τιμή μ και την τυπική απόκλιση σ των στοιχείων του πίνακα r. Η μέση τιμή μ και η τυπική απόκλιση σ ενός συνόλου n στοιχείων { x₁, x₂, ... x_n } είναι πραγματικοί αριθμοί και ορίζονται ως:

Σημείωση: Προσπαθήστε να υπολογίσετε το σ αποδοτικά μετασχηματίζοντας τον παραπάνω τύπο. Εκτός από την sqrt θα σας χρειαστεί η συνάρτηση rand που βρίσκεται στο <stdlib.h>.

Λύση: ex2-3.c

4. Χρήση της γεννήτριας τυχαίων αριθμών της C

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

Λύση: ex2-4.c

5. Χαρακτηρισμός πινάκων

Να κατασκευάσετε δυο συναρτήσεις που να δέχονται ως παράμετρο έναν τετραγωνικό πίνακα a ακεραίων αριθμών διαστάσεων N × N. Η πρώτη πρέπει να αποφασίζει αν ο πίνακας είναι συμμετρικός, δηλαδή αν ισχύει a[i][j]==a[j][i] για κάθε τιμή των i και j, κάνοντας τις ελάχιστες δυνατές συγκρίσεις στοιχείων. Η δεύτερη πρέπει να αποφασίζει αν ο πίνακας είναι άνω ή κάτω τριγωνικός ή αν δεν είναι τριγωνικός. Ένας πίνακας είναι άνω (κάτω) τριγωνικός αν τα στοιχεία του που βρίσκονται κάτω (πάνω) από την κύρια διαγώνιο είναι όλα μηδενικά. Και οι δύο συναρτήσεις θα πρέπει να επιστρέφουν κατάλληλα κωδικοποιημένες ακέραιες τιμές, χωρίς να διαβάζουν ή να εκτυπώνουν τίποτα.

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

Λύση: ex2-5.c

6. Τετραγωνική ρίζα με τη μέθοδο του Newton

Η τετραγωνική ρίζα x ενός πραγματικού αριθμού r > 0 με σχετική ακρίβεια e > 0 μπορεί να υπολογιστεί με την ακόλουθη επαναληπτική διαδικασία:

Να κατασκευάσετε μια συνάρτηση mysqrt που να δέχεται ως παραμέτρους δύο πραγματικούς αριθμούς r και e και να υπολογίζει, με τη μέθοδο αυτή, την τετραγωνική ρίζα του r με σχετική ακρίβεια e.

Να χρησιμοποιήσετε τη mysqrt σε ένα πρόγραμμα που να ζητά από το χρήστη ένα θετικό πραγματικό αριθμό και να εκτυπώνει την τετραγωνική του ρίζα με σχετική ακρίβεια 10^-6. Η διαδικασία αυτή να επαναλαμβάνεται μέχρις ότου δοθεί αριθμός που δεν είναι θετικός.

Λύση: ex2-6.c

7. Εκτύπωση λέξεων σε πλαίσιο

Να κατασκευάσετε ένα πρόγραμμα που να διαβάζει από το πληκτρολόγιο μια λέξη και να την εμφανίζει στην οθόνη με όλα τα γράμματά της κεφαλαία, περιβαλλόμενα από αστερίσκους. Για παράδειγμα, η λέξη "War" πρέπει να εμφανίζεται ως:

*************
* W * A * R *
*************

Η διαδικασία αυτή πρέπει να επαναλαμβάνεται μέχρις ότου δοθεί η λέξη "peace" από το πληκτρολόγιο.

Λύση: ex2-7.c

8. Συχνότητα εμφάνισης γραμμάτων

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

Λύση: ex2-8.c

9. Κρυπτογράφηση κειμένου

Μια σχετικά απλή μέθοδος κρυπτογράφησης κειμένου είναι η μέθοδος Βιζενέρ. Παίρνουμε το αρχικό κείμενο και μια λέξη-κλειδί P, η οποία έχει μήκος n χαρακτήρες. Κωδικοποιούμε τα γράμματα του αλφαβήτου με τους αριθμούς από το 1 έως το 26 (για το λατινικό αλφάβητο). Αντικαθιστούμε το πρώτο γράμμα c του αρχικού κειμένου με το γράμμα που προκύπτει αν προσθέσουμε στον κωδικό του c τον κωδικό του πρώτου γράμματος του κλειδιού P. Αν το αποτέλεσμα αυτής της πρόσθεσης είναι εκτός ορίων του αλφαβήτου, τότε αφαιρούμε 26. Επαναλαμβάνουμε για το επόμενο γράμμα του αρχικού κειμένου και το επόμενο γράμμα του κλειδιού και συνεχίζουμε έτσι μέχρι το τέλος του κειμένου. Κάθε φορά που εξαντλούμε τα n γράμματα του κλειδιού, ξεκινάμε πάλι από το πρώτο γράμμα του.

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

Λύση: ex2-9.c