Κεφάλαιο 3, Παραδείγματα, Τετράδιο Εργασιών, ΠΙΝΑΚΕΣ
Σε μία εταιρεία εργάζονται 200 υπάλληλοι και είναι γνωστός ο μισθός του καθενός. Να χρησιμοποιηθεί η δομή του πίνακα για να αποθηκεύονται οι μισθοί των υπαλλήλων και να βρεθεί ο κατάλληλος αλγόριθμος υπολογισμού του μεγαλύτερου μισθού. Στο τέλος αυτού του κεφαλαίου προσδοκάται ότι θα έχεις συνειδητοποιήσει τη σπουδαιότητα των δεδομένων για την επίλυση ενός προβλήματος. Θα έχεις ενστερνισθεί τη θεώρηση ότι οι αλγόριθμοι και οι δομές δεδομένων αποτελούν αδιάσπαστη ενότητα. Θα μπορείς να χειρίζεσαι με ευχέρεια προβλήματα σχετικά με εργασίες με πίνακες. Ακόμα θα μπορείς να κάνεις μια περιληπτική αναφορά σε άλλες δομές δεδομένων (στοίβα, ουρά, λίστα, δένδρο). Τέλος εκτιμάται ότι θα έχεις κατανοήσει τη λειτουργία της αναδρομής. Έτσι έρχεσαι σε επαφή με ένα πανόραμα δομών και αλγορίθμων, που αποτελεί ένα ικανοποιητικό σύνολο εργαλείων για την επίλυση πρακτικών προβλημάτων.
ΛΥΣΗ: (περισσότερα…)
Κεφάλαιο 3, Παραδείγματα, Τετράδιο Εργασιών
Είναι γνωστό από τα μαθηματικά ότι ο αριθμός των συνδυασμών των n πραγμάτων ανά k δίνεται από τον τύπο:
Να προταθεί ένας αλγόριθμος για τον υπολογισμό του αριθμού των συνδυασμών αυτών.
ΛΥΣΗ: (περισσότερα…)
Κεφάλαιο 3, Παραδείγματα, Τετράδιο Εργασιών, ΠΙΝΑΚΕΣ
Σε ένα Λύκειο υπάρχουν τρία τμήματα για την Γ΄ Λυκείου και κάθε τμήμα έχει 35 μαθητές. Να γραφεί ένας αλγόριθμος που θα διαβάζει το μέσο όρο βαθμολογίας κάθε μαθητή και θα υπολογίζει το γενικό μέσο όρο βαθμολογίας για όλη την τάξη της Γ΄ Λυκείου. Ο αλγόριθμος που ακολουθεί υπολογίζει τον παραπάνω μέσο όρο με χρήση της δομής του πίνακα.
ΛΥΣΗ: (περισσότερα…)
Κεφάλαιο 3, Παραδείγματα, Τετράδιο Εργασιών, ΠΙΝΑΚΕΣ
Έστω ότι δίνονται δύο δισδιάστατοι πίνακες Α και Β διαστάσεων 5×5 ο καθένας. Να γραφεί ένας αλγόριθμος που θα διαβάζει τα στοιχεία των πινάκων και θα υπολογίζει το άθροισμα των πινάκων, το οποίο θα αποθηκεύεται σε ένα νέο πίνακα.
ΛΥΣΗ: (περισσότερα…)
ΑΝΑΖΗΤΗΣΗ, Κεφάλαιο 3, Παραδείγματα, Τετράδιο Εργασιών, ΠΙΝΑΚΕΣ
Ένας πίνακας λέγεται αραιός (sparse) αν ένα μεγάλο ποσοστό των στοιχείων του έχουν μηδενική τιμή. Δεν υπάρχει ακριβές ποσοστό σε σχέση με τον αριθμό των μηδενικών στοιχείων, επάνω από το οποίο ένας πίνακας χαρακτηρίζεται ως αραιός. Αρκεί όμως, για παράδειγμα, να πούμε ότι με περισσότερο από 80% μηδενικά ένας πίνακας χαρακτηρίζεται ως αραιός. Αραιοί πίνακες συναντώνται συχνά σε μεγάλα επιστημονικά προβλήματα (επίλυση εξισώσεων κ.λπ.). Το πρόβλημα με τη διαχείριση των αραιών πινάκων είναι ότι δαπανάται πολύ χώρος για την αποθήκευση μηδενικών. Άρα πρέπει να βρεθεί ένας οικονομικός τρόπος αποθήκευσης των αραιών πινάκων. Στην πράξη έχουν προταθεί αρκετοί τρόποι. Ένας από αυτούς τους τρόπους περιγράφεται στη συνέχεια. Έστω, λοιπόν, ότι δίνεται ο επόμενος πίνακας, που θέλουμε να τον διαχειρισθούμε ως αραιό.
Αντί να αποθηκεύσουμε αυτόν το δισδιάστατο πίνακα 4×5, θα θεωρήσουμε ένα μονοδιάστατο πίνακα όπου θα τοποθετήσουμε μόνο τα μη μηδενικά στοιχεία, για τα οποία όμως χρειαζόμαστε τα στοιχεία των αντίστοιχων γραμμών και στηλών. Έτσι καταλήγουμε κάθε μη μηδενικό στοιχείο να αντιπροσωπεύεται από μία τριάδα στοιχείων, δηλαδή <γραμμή,στήλη,τιμή>. Για το λόγο αυτό δημιουργούμε ένα μονοδιάστατο πίνακα 18 θέσεων για τα 6 μη μηδενικά στοιχεία του αρχικού πίνακα. Ο νέος πίνακας έχει τη μορφή:
Πλέον, το πρόβλημα έγκειται στην αναγνώριση της τιμής μίας θέσης του παλαιού πίνακα, δεδομένου ότι ο πίνακας είναι αποθηκευμένος με τη νέα του μορφή. Ο επόμενος αλγόριθμος “Αραιός” επιστρέφει την τιμή του στοιχείου που βρίσκεται στη θέση <γραμμή Ι, στήλη m> του αρχικού πίνακα επεξεργαζόμενος τη νέα μορφή του πίνακα που αποτελείται από 3n θέσεις, όπου n ο αριθμός των μη μηδενικών στοιχείων.
ΛΥΣΗ: (περισσότερα…)
Πρόσφατα σχόλια