Επιλογή Σελίδας

4.3 Δυαδική Αναζήτηση

Έστω ότι δίνεται ένας ηλεκτρονικός τηλεφωνικός κατάλογος, δηλαδή ένας πίνακας με n ονόματα και έναν αριθμό τηλεφώνου για κάθε όνομα. Ο κατάλογος είναι ταξινομημένος κατά αύξουσα αλφαβητική τάξη ως προς τα ονόματα. Έστω ότι τα n ονόματα με τα αντίστοιχα τηλέφωνα είναι αποθηκευμένα σε δύο πίνακες: names[1 ..n] και phones[1 ..n] αντίστοιχα. Σε μία τέτοια περίπτωση, λοιπόν, το ζητούμενο είναι να βρεθεί το τηλέφωνο που αντιστοιχεί σε δεδομένο όνομα συνδρομητή (υποθέτοντας ότι το δεδομένο αναζητούμενο όνομα πράγματι υπάρχει στον κατάλογο).Το πρόβλημα επιλύεται με τη μέθοδο Διαίρει και Βασίλευε με βάση την παρατήρηση ότι όταν δοθεί ένα όνομα, τότε υπάρχουν οι εξής 3 περιπτώσεις:

  1. το όνομα βρίσκεται στη μεσαία θέση του πίνακα names,
  2. το όνομα βρίσκεται σε μία θέση στο πρώτο μισό κομμάτι του πίνακα names, ή
  3. το όνομα βρίσκεται σε μία θέση στο δεύτερο μισό κομμάτι του πίνακα names.

Η παρατήρηση αυτή οδηγεί στη σύνταξη του επόμενου αλγορίθμου. Σημειώνεται ότι ο αλγόριθμος αυτός ισχύει μόνο για την περίπτωση που το αναζητούμενο όνομα υπάρχει στον κατάλογο (δηλαδή, στον πίνακα names). Ο αλγόριθμος αυτός μπορεί εύκολα να τροποποιηθεί ώστε να αντιμετωπίζει και την περίπτωση της «ανεπιτυχούς αναζήτησης», δηλαδής της περίπτωσης όπου το αναζητούμενο όνομα δεν υπάρχει στον πίνακα.

Σχ. 4. 2. Δυαδική αναζήτηση

! Αλγόριθμος επεξήγησης (αναδρομικός - εκτός ύλης), βλέπε παρακάτω το πρόγραμμα 
Αλγόριθμος Δυαδική_αναζήτηση
Δεδομένα  //names, phones, onoma, arhi, telos // ! παρόραμα arxi
meso <-- [arhi + telos] / 2
Αν onoma = names[meso] τότε
   Tel <-- phones[meso]
Αλλιώς
   Αν onoma < names[meso] τότε
      Δυαδική_αναζήτηση(names, phones, onoma, arhi, meso-1)
   αλλιώς
      Δυαδική αναζήτηση(names, phones, onoma, meso+1, telos)
   Τέλος_αν
Τέλος_αν
Αποτελέσματα // Tel //
Τέλος Δυαδική_αναζήτηση

 

Παρατήρηση: Η δυαδική αναζήτηση χρησιμοποιείται μόνο στην περίπτωση ταξινομημένου πίνακα.

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

Σχ. 4.3 Διαδοχικές συγκρίσεις σε αρχικό πίνακα και υπο-πίνακες για την αναζήτηση του ονόματος Δανάη.

Σχ. 4.3 Διαδοχικές συγκρίσεις σε αρχικό πίνακα και υπο-πίνακες για την αναζήτηση του ονόματος Δανάη.

θέσεις ελέγχεται η μεσαία, δηλαδή η τρίτη, όπου βρίσκεται το όνομα Κατερίνα. Το όνομα Δανάη είναι λεξικογραφικά μικρότερο από το όνομα Κατερίνα και επομένως η αναζήτηση περιορίζεται στο πρώτο μισό του πίνακα που αποτελείται από δυο θέσεις. Από τις δύο αυτές θέσεις, σε μία δεύτερη προσπάθεια ελέγχεται η πρώτη θέση, όπου βρίσκεται το τηλέφωνο του Γιάννη. Επειδή, το όνομα Δανάη είναι λεξικογραφικά μεγαλύτερο από το όνομα Γιάννης, η αναζήτηση περιορίζεται στον υπο-πίνακα που αποτελείται από τη δεύτερη θέση μόνο. Έτσι, στη θέση αυτή με μία τρίτη προσπάθεια βρίσκουμε το τηλέφωνο της Δανάης.

! ΟΔΗΓΙΕΣ ΔΙΔΑΣΚΑΛΙΑΣ 2016-2017, Παράρτημα Γ
! Αναζήτηση σε ΤΑΞΙΝΟΜΕΝΟ πίνακα 20 θέσεων
ΠΡΟΓΡΑΜΜΑ δυαδική_αναζήτηση 
ΜΕΤΑΒΛΗΤΕΣ 
ΑΚΕΡΑΙΕΣ: A[20], Left, Right, M, k, S, i 
ΛΟΓΙΚΕΣ: f 
ΑΡΧΗ 
ΓΡΑΨΕ 'Οι αριθμοί που θα δοθούν πρέπει να είναι ταξινομημένοι κατά αύξουσα τάξη' 
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20 
    ΓΡΑΨΕ 'Δώσε το', i, ' στοιχείο του πίνακα' 
    ΔΙΑΒΑΣΕ A[i] 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΓΡΑΨΕ 'Δωσε τιμή για αναζήτηση: ' 
ΔΙΑΒΑΣΕ S 
Left <-- 1 
Right <-- 20 
k <-- 0 
f <-- ΨΕΥΔΗΣ 
ΟΣΟ (Left <= Right) ΚΑΙ (f = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ 
     M <-- (Left + Right) DIV 2 
     ΑΝ A[M] = S ΤΟΤΕ 
        k <-- M 
        f <-- ΑΛΗΘΗΣ 
    ΑΛΛΙΩΣ 
       ΑΝ A[M] < S ΤΟΤΕ 
          Left <-- M + 1 
       ΑΛΛΙΩΣ 
          Right <-- M - 1 
       ΤΕΛΟΣ_ΑΝ 
    ΤΕΛΟΣ_ΑΝ 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΑΝ f = ΑΛΗΘΗΣ ΤΟΤΕ 
   ΓΡΑΨΕ 'Το στοιχείο,', S, 'υπάρχει στη θέση:', M 
ΑΛΛΙΩΣ 
   ΓΡΑΨΕ 'Το στοιχείο,', S, ' δεν υπάρχει στον πίνακα'
ΤΕΛΟΣ_ΑΝ 
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ δυαδική_αναζήτηση

*Ως άσκηση μπορεί να δοθεί η βελτιστοποίηση του αλγορίθμου δυαδικής αναζήτησης έτσι ώστε να επιτρέπει διαδοχικές αναζητήσεις πολλών στοιχείων. Η αναζήτηση να τερματίζεται όταν δοθεί κάποιος συγκεκριμένος αριθμός ή με ερώτηση «Θέλετε άλλη αναζήτηση (Ν/Ο)»

Επαναληπτική άσκηση, Θέμα Α, υποερώτημα

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

ΑΝ  (Χ1 mod 2 = 0 ΚΑΙ X2 mod 2 = 0) Ή (Χ1 mod 2 = 1 ΚΑΙ X2 mod 2 = 1) ΤΟΤΕ 

            Εντολές 

ΤΕΛΟΣ_ΑΝ

 (ΜΟΝΑΔΕΣ 5)

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

Επαναληπτική άσκηση, Θέμα Γ, Βασικές Έννοιες Αλγορίθμων, Μαιευτική Κλινική

Μια μαιευτική κλινική εφαρμόζει την παρακάτω πολιτική χρέωσης:

  • Το κόστος κάθε γέννας ξεκινάει με πάγιο 1500 ευρώ, το οποίο συμπεριλαμβάνει 2 διανυκτερεύσεις στην κλινική.
  • Το κόστος για κάθε επιπλέον διανυκτέρευση στην κλινική ακολουθεί κλιμακωτά τις χρεώσεις που φαίνονται στον παρακάτω πίνακα:
Διανυκτερεύσεις Τιμή (σε ευρώ) / Ημέρα
3-4 425
5-6 350
7-9 200
10 -….. 150
  • Το φιλανθρωπικό τμήμα της κλινικής ορίζει πως θα δίνεται επιστροφή χρημάτων σε κάθε μέλλουσα μητέρα, κλιμακωτά ανάλογα με τον αριθμό παιδιών της (μαζί με το καινούριο της μέλος !), σύμφωνα με τον παρακάτω πίνακα:
Αριθμός παιδιών Έκπτωση (σε ευρώ) / Παιδί
1-2 150
3-6 250
7-…… 400

 Να γίνει πρόγραμμα σε γλώσσα προγραμματισμού «ΓΛΩΣΣΑ» το οποίο:

  1. Να περιέχει τμήμα δήλωσης μεταβλητών και σταθερών.

(ΜΟΝΑΔΕΣ 2)

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

(ΜΟΝΑΔΕΣ 8)

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

(ΜΟΝΑΔΕΣ 8)

  1. Να υπολογίζει το τελικό ποσό που πρέπει να καταβάλλει στην κλινική (μαζί με το πάγιο) και να το εμφανίζει στην οθόνη μετά από το μήνυμα «ΝΑ ΣΑΣ ΖΗΣΕΙ».

(ΜΟΝΑΔΕΣ 2)

ΜΟΝΑΔΕΣ 20

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

Υπολογισμός της ημερομηνίας του ΠΑΣΧΑ

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

Y1 = X mod 4 
Y2 = X mod 7 
Y3 = X mod 19 
K = 19 * Y3 + 16 
Y4 = K mod 30 
L = 2*Y1 + 4 * Y2 + 6 * Y4 
Y5 = L mod 7 
N = Y4 + Y5 + 3

(να λάβετε υπ’ όψη σας ότι σε περίπτωση που το Ν υπερβαίνει τον αριθμό 30 τότε το Πάσχα αντιστοιχεί στο μήνα Μάιο, αλλιώς αντιστοιχεί στο μήνα Απρίλιο)

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

Υπολογίστε αν ένα έτος είναι δίσεκτο

Το σύστημα ημερομηνίας που χρησιμοποιείται από το Excel βασίζεται στο Γρηγοριανό ημερολόγιο, το οποίο καθιερώθηκε για πρώτη φορά το 1582 από τον Πάπα Γρηγόριο XIII. Αυτό το ημερολόγιο σχεδιάστηκε για να διορθώσει τα σφάλματα που παρουσιάστηκαν από το λιγότερο ακριβές Ιουλιανό ημερολόγιο.

Στο Γρηγοριανό ημερολόγιο, ένα κανονικό έτος αποτελείται από 365 ημέρες. Επειδή η πραγματική διάρκεια ενός αστρικού έτους (ο χρόνος που απαιτείται για μια πλήρη περιφορά της Γης γύρω από τον Ήλιο) είναι 365.25635 ημέρες, το «δίσεκτο έτος» των 366 ημερών χρησιμοποιείται μία φορά κάθε τέσσερα χρόνια προκειμένου να ελαχιστοποιηθεί το σφάλμα που προκαλείται από τα τρία κανονικά (αλλά ελλιπή) έτη. Κάθε έτος το οποίο διαιρείται ακριβώς σε 4 ίσα μέρη είναι δίσεκτο έτος. για παράδειγμα, τα έτη 1988, 1992 και 1996 είναι δίσεκτα έτη.

Ωστόσο, εξακολουθεί να υπάρχει ένα μικρό σφάλμα που πρέπει να ληφθεί υπόψη. Για να εξαλειφθεί αυτό το σφάλμα, το Γρηγοριανό ημερολόγιο ορίζει ότι ένα έτος που διαιρείται ακριβώς με το 100 (για παράδειγμα, το έτος 1900) είναι δίσεκτο έτος μόνο εάν διαιρείται ακριβώς και με το 400.

Για αυτόν το λόγο, τα ακόλουθα έτη

1700, 1800, 1900, 2100, 2200, 2300, 2500, 2600

ΔΕΝ είναι δίσεκτα, επειδή διαιρούνται ακριβώς με το 100 αλλά ΟΧΙ και με το 400.

Τα ακόλουθα έτη

1600, 2000, 2400

ΕΙΝΑΙ δίσεκτα, επειδή διαιρούνται ακριβώς τόσο με το 100 όσο και με το 400.

Για να προσδιορίσετε αν ένα έτος είναι δίσεκτο, ακολουθήστε τα εξής βήματα:

  1. Εάν το έτος διαιρείται ακριβώς με το 4, μεταβείτε στο βήμα 2. Διαφορετικά, προχωρείστε το βήμα 5.
  2. Εάν το έτος διαιρείται ακριβώς με το 100, μεταβείτε στο βήμα 3. Διαφορετικά, προχωρήστε το βήμα 4.
  3. Εάν το έτος διαιρείται ακριβώς με το 400, μεταβείτε στο βήμα 4. Διαφορετικά, προχωρείστε το βήμα 5.
  4. Αυτό το έτος είναι δίσεκτο έτος (έχει 366 ημέρες).
  5. Αυτό το έτος δεν είναι δίσεκτο έτος (έχει 365 ημέρες).
Πρόγραμμα Δίσεκτο
μεταβλητές
 Ακέραιες: ετ
 Λογικές: δισ
Αρχή
 διάβασε ετ
 δισ <-- Ψευδής
 Αν ετ mod 4 = 0 τότε
 Αν ετ mod 100 = 0 τότε
 Αν ετ mod 400 = 0 τότε
 δισ <-- Αληθής
 Τέλος_αν
 αλλιώς
 δισ <-- Αληθής
 Τέλος_αν
 Τέλος_αν
 Γράψε δισ
Τέλος_Προγράμματος


Πρόγραμμα Δίσεκτο_2
μεταβλητές
 Ακέραιες: ετ 
 Λογικές: δισ
Αρχή
 Γράψε 'δώσε Έτος:'
 διάβασε ετ
 δισ <-- (ετ mod 4 = 0 και ετ mod 100 <> 0) ή ετ mod 400 = 0 
 Γράψε δισ
Τέλος_Προγράμματος

 

Θέμα Γ, 2010, Μαΐου-Ιουνίου, Ημερήσια

Σε κάποιο σχολικό αγώνα, για το άθλημα «Άλμα εις μήκος» καταγράφεται για κάθε αθλητή η καλύτερη έγκυρη επίδοσή του. Τιμής ένεκεν, πρώτος αγωνίζεται ο περσινός πρωταθλητής. Η Επιτροπή του αγώνα διαχειρίζεται τα στοιχεία των αθλητών που αγωνίστηκαν. Να γράψετε αλγόριθμο ο οποίος:

Γ1. Να ζητάει το ρεκόρ αγώνων και να το δέχεται, εφόσον είναι θετικό και μικρότερο των 10 μέτρων.

Μονάδες 2

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

Μονάδες 4

Γ3. Να εμφανίζει το όνομα του αθλητή με τη χειρότερη επίδοση.

Μονάδες 4

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

Μονάδες 6

Γ5. Να βρίσκει και να εμφανίζει τη θέση που κατέλαβε στην τελική κατάταξη ο περσινός πρωταθλητής.

Μονάδες 4

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

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