Παράδειγμα 1, Τετράδιο Εργασιών, Υπολογισμός μέγιστου ποσού

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

ΛΥΣΗ: (περισσότερα…)

Παράδειγμα 2, Κεφάλαιο 3, Τετράδιο Εργασιών, Υπολογισμός αριθμού συνδυασμών

Είναι γνωστό από τα μαθηματικά ότι ο αριθμός των συνδυασμών των n πραγμάτων ανά k δίνεται από τον τύπο:

par2kef3temath

Να προταθεί ένας αλγόριθμος για τον υπολογισμό του αριθμού των συνδυασμών αυτών.
ΛΥΣΗ: (περισσότερα…)

Παράδειγμα 3, Τετράδιο Εργασιών, Υπολογισμός μέσου όρου

Σε ένα Λύκειο υπάρχουν τρία τμήματα για την Γ΄ Λυκείου και κάθε τμήμα έχει 35 μαθητές. Να γραφεί ένας αλγόριθμος που θα διαβάζει το μέσο όρο βαθμολογίας κάθε μαθητή και θα υπολογίζει το γενικό μέσο όρο βαθμολογίας για όλη την τάξη της Γ΄ Λυκείου. Ο αλγόριθμος που ακολουθεί υπολογίζει τον παραπάνω μέσο όρο με χρήση της δομής του πίνακα.

ΛΥΣΗ: (περισσότερα…)

Παράδειγμα 4, Τετράδιο Εργασιών, Χρήση δισδιάστατων πινάκων

Έστω ότι δίνονται δύο δισδιάστατοι πίνακες Α και Β διαστάσεων 5×5 ο καθένας. Να γραφεί ένας αλγόριθμος που θα διαβάζει τα στοιχεία των πινάκων και θα υπολογίζει το άθροισμα των πινάκων, το οποίο θα αποθηκεύεται σε ένα νέο πίνακα.

ΛΥΣΗ: (περισσότερα…)

Παράδειγμα 5, Τετράδιο Εργασιών, Αραιοί πίνακες

Ένας πίνακας λέγεται αραιός (sparse) αν ένα μεγάλο ποσοστό των στοιχείων του έχουν μηδενική τιμή. Δεν υπάρχει ακριβές ποσοστό σε σχέση με τον αριθμό των μηδενικών στοιχείων, επάνω από το οποίο ένας πίνακας χαρακτηρίζεται ως αραιός. Αρκεί όμως, για παράδειγμα, να πούμε ότι με περισσότερο από 80% μηδενικά ένας πίνακας χαρακτηρίζεται ως αραιός. Αραιοί πίνακες συναντώνται συχνά σε μεγάλα επιστημονικά προβλήματα (επίλυση εξισώσεων κ.λπ.). Το πρόβλημα με τη διαχείριση των αραιών πινάκων είναι ότι δαπανάται πολύ χώρος για την αποθήκευση μηδενικών. Άρα πρέπει να βρεθεί ένας οικονομικός τρόπος αποθήκευσης των αραιών πινάκων. Στην πράξη έχουν προταθεί αρκετοί τρόποι. Ένας από αυτούς τους τρόπους περιγράφεται στη συνέχεια. Έστω, λοιπόν, ότι δίνεται ο επόμενος πίνακας, που θέλουμε να τον διαχειρισθούμε ως αραιό.
par5kef3temath
Αντί να αποθηκεύσουμε αυτόν το δισδιάστατο πίνακα 4×5, θα θεωρήσουμε ένα μονοδιάστατο πίνακα όπου θα τοποθετήσουμε μόνο τα μη μηδενικά στοιχεία, για τα οποία όμως χρειαζόμαστε τα στοιχεία των αντίστοιχων γραμμών και στηλών. Έτσι καταλήγουμε κάθε μη μηδενικό στοιχείο να αντιπροσωπεύεται από μία τριάδα στοιχείων, δηλαδή <γραμμή,στήλη,τιμή>. Για το λόγο αυτό δημιουργούμε ένα μονοδιάστατο πίνακα 18 θέσεων για τα 6 μη μηδενικά στοιχεία του αρχικού πίνακα. Ο νέος πίνακας έχει τη μορφή:
par5kef3temath2
Πλέον, το πρόβλημα έγκειται στην αναγνώριση της τιμής μίας θέσης του παλαιού πίνακα, δεδομένου ότι ο πίνακας είναι αποθηκευμένος με τη νέα του μορφή. Ο επόμενος αλγόριθμος “Αραιός” επιστρέφει την τιμή του στοιχείου που βρίσκεται στη θέση <γραμμή Ι, στήλη m> του αρχικού πίνακα επεξεργαζόμενος τη νέα μορφή του πίνακα που αποτελείται από 3n θέσεις, όπου n ο αριθμός των μη μηδενικών στοιχείων.

ΛΥΣΗ: (περισσότερα…)