2018, Α ΘΕΜΑ, ΕΠΑΝΑΛΗΠΤΙΚΕΣ, ΕΣΠΕΡΙΝΑ, ΗΜΕΡΗΣΙΑ, ΠΙΝΑΚΕΣ, ΣΩΣΤΟ ΛΑΘΟΣ, ΥΠΟΠΡΟΓΡΑΜΜΑΤΑ
Α1. Να γράψετε στο τετράδιό σας τον αριθμό καθεμιάς από τις παρακάτω προτάσεις 1 έως 5 και δίπλα τη λέξη ΣΩΣΤΟ, αν η πρόταση είναι σωστή, ή τη λέξη ΛΑΘΟΣ, αν η πρόταση είναι λανθασμένη.
- Τα λογικά λάθη εμφανίζονται στο στάδιο της μεταγλώττισης.
- Η τελική τιμή μιας έκφρασης εξαρτάται, μεταξύ άλλων, από την ιεραρχία των πράξεων και τη χρήση των παρενθέσεων.
- Η δυαδική αναζήτηση δεν μπορεί να λειτουργήσει σε μη ταξινομημένο πίνακα.
- Αν τα δεδομένα που εισάγονται σε ένα πρόγραμμα πρέπει να διατηρούνται στη μνήμη μέχρι το τέλος της εκτέλεσης, τότε η χρήση πινάκων βοηθάει ή συχνά είναι απαραίτητη για την επίλυση του προβλήματος.
- Η λειτουργία των διαδικασιών είναι πιο περιορισμένη από τη λειτουργία των συναρτήσεων.
Μονάδες 10
ΝΕΑ
Έστω ότι δίνεται ένας ηλεκτρονικός τηλεφωνικός κατάλογος, δηλαδή ένας πίνακας με n ονόματα και έναν αριθμό τηλεφώνου για κάθε όνομα. Ο κατάλογος είναι ταξινομημένος κατά αύξουσα αλφαβητική τάξη ως προς τα ονόματα. Έστω ότι τα n ονόματα με τα αντίστοιχα τηλέφωνα είναι αποθηκευμένα σε δύο πίνακες: names[1 ..n] και phones[1 ..n] αντίστοιχα. Σε μία τέτοια περίπτωση, λοιπόν, το ζητούμενο είναι να βρεθεί το τηλέφωνο που αντιστοιχεί σε δεδομένο όνομα συνδρομητή (υποθέτοντας ότι το δεδομένο αναζητούμενο όνομα πράγματι υπάρχει στον κατάλογο).Το πρόβλημα επιλύεται με τη μέθοδο Διαίρει και Βασίλευε με βάση την παρατήρηση ότι όταν δοθεί ένα όνομα, τότε υπάρχουν οι εξής 3 περιπτώσεις:
- το όνομα βρίσκεται στη μεσαία θέση του πίνακα names,
- το όνομα βρίσκεται σε μία θέση στο πρώτο μισό κομμάτι του πίνακα names, ή
- το όνομα βρίσκεται σε μία θέση στο δεύτερο μισό κομμάτι του πίνακα names.
Η παρατήρηση αυτή οδηγεί στη σύνταξη του επόμενου αλγορίθμου. Σημειώνεται ότι ο αλγόριθμος αυτός ισχύει μόνο για την περίπτωση που το αναζητούμενο όνομα υπάρχει στον κατάλογο (δηλαδή, στον πίνακα names). Ο αλγόριθμος αυτός μπορεί εύκολα να τροποποιηθεί ώστε να αντιμετωπίζει και την περίπτωση της “ανεπιτυχούς αναζήτησης”, δηλαδής της περίπτωσης όπου το αναζητούμενο όνομα δεν υπάρχει στον πίνακα.
! Αλγόριθμος επεξήγησης (αναδρομικός - εκτός ύλης), βλέπε παρακάτω το πρόγραμμα
Αλγόριθμος Δυαδική_αναζήτηση
Δεδομένα //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 Διαδοχικές συγκρίσεις σε αρχικό πίνακα και υπο-πίνακες για την αναζήτηση του ονόματος Δανάη.
θέσεις ελέγχεται η μεσαία, δηλαδή η τρίτη, όπου βρίσκεται το όνομα Κατερίνα. Το όνομα Δανάη είναι λεξικογραφικά μικρότερο από το όνομα Κατερίνα και επομένως η αναζήτηση περιορίζεται στο πρώτο μισό του πίνακα που αποτελείται από δυο θέσεις. Από τις δύο αυτές θέσεις, σε μία δεύτερη προσπάθεια ελέγχεται η πρώτη θέση, όπου βρίσκεται το τηλέφωνο του Γιάννη. Επειδή, το όνομα Δανάη είναι λεξικογραφικά μεγαλύτερο από το όνομα Γιάννης, η αναζήτηση περιορίζεται στον υπο-πίνακα που αποτελείται από τη δεύτερη θέση μόνο. Έτσι, στη θέση αυτή με μία τρίτη προσπάθεια βρίσκουμε το τηλέφωνο της Δανάης.
! ΟΔΗΓΙΕΣ ΔΙΔΑΣΚΑΛΙΑΣ 2016-2017, Παράρτημα Γ
! Αναζήτηση σε ΤΑΞΙΝΟΜΕΝΟ πίνακα 20 θέσεων
ΠΡΟΓΡΑΜΜΑ δυαδική_αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: A[20], Left, Right, M, k, S, i
ΛΟΓΙΚΕΣ: found
ΑΡΧΗ
ΓΡΑΨΕ 'Οι αριθμοί που θα δοθούν πρέπει να είναι ταξινομημένοι κατά αύξουσα τάξη'
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20
ΓΡΑΨΕ 'Δώσε το', i, ' στοιχείο του πίνακα'
ΔΙΑΒΑΣΕ A[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δωσε τιμή για αναζήτηση: '
ΔΙΑΒΑΣΕ S
Left <-- 1
Right <-- 20
k <-- 0
found <-- ΨΕΥΔΗΣ
ΟΣΟ (Left <= Right) ΚΑΙ (found = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ
M <-- (Left + Right) DIV 2
ΑΝ A[M] = S ΤΟΤΕ
k <-- M
found <-- ΑΛΗΘΗΣ
ΑΛΛΙΩΣ
ΑΝ A[M] < S ΤΟΤΕ
Left <-- M + 1
ΑΛΛΙΩΣ
Right <-- M - 1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ found = ΑΛΗΘΗΣ ΤΟΤΕ
ΓΡΑΨΕ 'Το στοιχείο,', S, 'υπάρχει στη θέση:', M
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Το στοιχείο,', S, ' δεν υπάρχει στον πίνακα'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ δυαδική_αναζήτηση
*Ως άσκηση μπορεί να δοθεί η βελτιστοποίηση του αλγορίθμου δυαδικής αναζήτησης έτσι ώστε να επιτρέπει διαδοχικές αναζητήσεις πολλών στοιχείων. Η αναζήτηση να τερματίζεται όταν δοθεί κάποιος συγκεκριμένος αριθμός ή με ερώτηση “Θέλετε άλλη αναζήτηση (Ν/Ο)”
ΑΝΑΖΗΤΗΣΗ, Κεφάλαιο 10, ΔΣ, ΥΠΟΠΡΟΓΡΑΜΜΑΤΑ
Δίνεται η εξίσωση e^x – 2x – 1 = 0. Να γραφεί πρόγραμμα το οποίο να βρίσκει μια ρίζα της εξίσωσης αυτής στο διάστημα [1,2] με τη μέθοδο της διχοτόμησης, όπως περιγράφηκε στην παράγραφο 4.3 του βιβλίου σου.
…” Ο τρόπος που λειτουργεί η δυαδική αναζήτηση είναι ανάλογος με αυτόν της μεθόδου της διχοτόμησης. Η μέθοδος της διχοτόμησης (ή του Bolzano) χρησιμοποιείται για την εύρεση μιας ρίζας της εξίσωσης f(x)=0 στο διάστημα [a, b]. Ως γνωστό, στο διάστημα αυτό υπάρχει μία τουλάχιστον ρίζα, αν ισχύει f(a).f(b)<0 (για την ακρίβεια μπορεί να υπάρχει περιττός αριθμός ριζών). Με τη μέθοδο της διχοτόμησης βρίσκεται ένα σημείο x1 ( = (a+b)/2) στο μέσο του διαστήματος [a, b] και εξετάζεται, αv f(a).f(x1)<0. Αν ναι, τότε η ρίζα υπάρχει στο διάστημα [a, x1], αλλιώς στο [x1, b]. Στη συνέχεια βρίσκεται το μέσο x2 του υποδιαστήματος που υπάρχει η ρίζα και επαναλαμβάνονται τα ίδια. Έτσι σε κάθε επανάληψη εξαιρείται από την έρευνα το μισό διάστημα και προφανώς η ακολουθία τιμών x1, x2,… συγκλίνει προς τη ρίζα της εξίσωσης. Η διαδικασία τερματίζεται, όταν η προσέγγιση της ρίζας θεωρείται ικανοποιητική.”
ΛΥΣΗ (περισσότερα…)
Πρόσφατα σχόλια