Παράδειγμα 3.2, Τηλεφωνικός Κατάλογος, Δομές Δεδομένων
Έστω ότι πρέπει να γραφεί ένας αλγόριθμος που να δέχεται ως είσοδο το όνομα ενός συνδρομητή του ΟΤΕ και να δίνει ως έξοδο το τηλέφωνό του.
Πρώτη Λύση (περισσότερα…)
Έστω ότι πρέπει να γραφεί ένας αλγόριθμος που να δέχεται ως είσοδο το όνομα ενός συνδρομητή του ΟΤΕ και να δίνει ως έξοδο το τηλέφωνό του.
Πρώτη Λύση (περισσότερα…)
Δίνεται ένας μονοδιάστατος πίνακας table 100 στοιχείων. Να σχεδιασθεί αλγόριθμος που να βρίσκει το μικρότερο στοιχείο του.
ΛΥΣΗ: (περισσότερα…)
Δίδεται ο δισδιάστατος πίνακας table με m γραμμές n στήλες. Να βρεθεί το άθροισμα κατά γραμμή, κατά στήλη και συνολικά.
ΛΥΣΗ: (περισσότερα…)
Όπως είδαμε η δομή της στοίβας λειτουργεί με τη μέθοδο FIFO. Οι δύο αυτές μέθοδοι έχουν αρκετές χρήσεις σε πραγματικά προβλήματα.
Ας θεωρήσουμε για παράδειγμα την περίπτωση ενός αποθηκευτικού χώρου μιας επιχείρησης. Σε κάθε αποθήκη γίνονται εισαγωγές ειδών που προέρχονται από αγορές από προμηθευτές, αν η επιχείρηση είναι εμπορική ή από την παραγωγή, αν πρόκειται για βιομηχανική επιχείρηση. Τα εμπορεύματα ή προϊόντα τοποθετούνται σε κάποιους χώρους, αποθήκες, ράφια κ.λπ. Όταν γίνονται πωλήσεις κάποιων ειδών, τα είδη αυτά βγαίνουν από την αποθήκη και αποστέλλονται στους πελάτες. Έτσι εισαγωγές και εξαγωγές ειδών γίνονται συνεχώς στην αποθήκη ανάλογα με τη διαδικασία προμηθειών και τη ροή των πωλήσεων. Σε μια δεδομένη στιγμή για κάποιο είδος μπορεί να υπάρχουν αποθηκευμένα κάποια τεμάχια που προέρχονται από μια παραλαβή και κάποια άλλα που υπήρχαν πιο πριν. Όταν πρέπει να εξαχθεί λοιπόν ένα τεμάχιο από αυτό το είδος, προκύπτει το πρόβλημα, από ποια παρτίδα πρέπει να είναι; Η απάντηση στο ερώτημα αυτό έχει φυσική και λογιστική αξία. Αν το είδος αυτό δεν επηρεάζεται από το χρόνο, τότε ίσως δεν έχει μεγάλη σημασία η επιλογή. Αν όμως πρόκειται για είδος που μπορεί να αλλοιωθεί ή έχει ημερομηνία λήξης (π.χ. φάρμακα), τότε είναι φανερό ότι πρέπει να επιλεγεί το παλαιότερο. Στην περίπτωση αυτή λοιπόν πρέπει η εξαγωγή των ειδών να γίνεται με τη μέθοδο FIFO και συνήθως επαφίεται στον αποθηκάριο να κάνει τη σωστή επιλογή. Εξίσου δύσκολο είναι το πρόβλημα αυτό από την οικονομική και λογιστική σκοπιά, που μάλιστα αφορά όλα τα είδη με ή χωρίς ημερομηνία λήξης. Ας υποθέσουμε ότι μια επιχείρηση έχει πραγματοποιήσει τις επόμενες αγορές και πωλήσεις για ένα είδος.
Η πιο απλή μορφή αναζήτησης στοιχείου σε πίνακα είναι η σειριακή (sequential) ή γραμμική (linear) μέθοδος. Έτσι για τον επόμενο αλγόριθμο Sequential Search υποτίθεται ότι αναζητείται η τιμή key στο μη ταξινομημένο πίνακα table. Μετά την εκτέλεση του αλγορίθμου η μεταβλητή position επιστρέφει την τιμή 0, αν η αναζήτηση είναι ανεπιτυχής, ενώ αν η αναζήτηση είναι επιτυχής, τότε επιστρέφει τη θέση του στοιχείου στον πίνακα (δηλαδή, έναν αριθμό από 1 ως n).
ΛΥΣΗ: (περισσότερα…)
Έστω ότι ο αρχικός πίνακας αποτελείται από εννέα κλειδιά τα εξής: 52, 12, 71, 56, 5, 10, 19, 90 και 45. Η μέθοδος εφαρμοζόμενη σε αυτά τα εννέα κλειδιά εξελίσσεται όπως φαίνεται στο επόμενο σχήμα. Κάθε φορά το ταξινομημένο τμήμα του πίνακα εμφανίζεται με χρώμα, ενώ τα στοιχεία που σαν φυσαλίδες ανέρχονται μέσα στον πίνακα εντοπίζονται με το αντίστοιχο βέλος στα δεξιά τους. Κάθε φορά εμφανίζεται η τάξη της επανάληψης (i).
Σχ.3.7 Ταξινόμηση φυσαλίδας.
ΛΥΣΗ: (περισσότερα…)
Η έννοια του παραγοντικού είναι γνωστή από τα μαθηματικά. Πιο συγκεκριμένα, για ένα ακέραιο n, το n παραγοντικό, που συμβολίζεται με n!, ορίζεται από τη σχέση: n! = 1 x 2 x 3 x … x (n – 1) x n Ισοδύναμος είναι και ο εξής ορισμός n • (n – 1)! αν n > 0 1 αν n = 0 n! = Ο ορισμός αυτός διακρίνεται από το βασικό χαρακτηριστικό ότι το παραγοντικό εκφράζεται με βάση μία απλούστερη περίπτωση του εαυτού του. Δηλαδή εξ ορισμού το παραγοντικό είναι μία αναδρομική αλγεβρική συνάρτηση. Με τον επόμενο αλγόριθμο υπολογίζεται με πολύ απλό αναδρομικό τρόπο το n παραγοντικό. (περισσότερα…)
Ένα ιστορικό πρόβλημα είναι η εύρεση του μέγιστου κοινού διαιρέτη (μκδ) δύο ακεραίων αριθμών. Ο αλγόριθμος εύρεσης του μκδ ανήκει στον Ευκλείδη. Ωστόσο η υλοποίηση και αυτού του αλγορίθμου μπορεί να γίνει κατά πολλούς τρόπους. Στη συνέχεια δίνεται ένας πρώτος αλγόριθμος για τον υπολογισμό του μκδ δύο ακεραίων x και y. Η μέθοδος αυτή είναι αρκετά αργή (και δεν στηρίζεται στον αλγόριθμο του Ευκλείδη), αλλά απλώς δίνεται για να διαφανεί η βελτίωση στην επίδοση από τους επόμενους αλγορίθμους. Ουσιαστικά λαμβάνει το μικρότερο από τους δύο ακεραίους, τον z, και εξετάζει με τη σειρά όλους τους ακεραίους ξεκινώντας από τον z και μειώνοντας συνεχώς κατά μία μονάδα μέχρι και οι δύο αριθμοί, x και y, να διαιρούνται από τη νέα τιμή του z. (περισσότερα…)
Για καλύτερη κατανόηση της διαφοράς μεταξύ επαναληπτικών και αναδρομικών μεθόδων, στη συνέχεια θα εξετασθεί ένα τελευταίο παράδειγμα, όπου υπολογίζεται η ακολουθία αριθμών Fibonacci πρώτης τάξης, που ορίζεται ως εξής:
ενώ οι πρώτοι όροι της ακολουθίας Fibonacci πρώτης τάξης είναι: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 κ.λπ.
ΛΥΣΗ: (περισσότερα…)
Πρόσφατα σχόλια