Ενότητα 2. Τεχνικές Σχεδίασης Αλγορίθμων 2.1 Μέθοδος Διαίρει και Βασίλευε
Διαίρει και Βασίλευε : Μέθοδος επίλυσης προβλημάτων, που εφαρμόζεται για τη γρήγορη αναζήτηση δεδομένων σε μια υπάρχουσα δομή δεδομένων.
Ορισμός : Η «Διαίρει και Βασίλευε» (divide and conquer) αποτελεί μια μέθοδο σχεδίασης αλγορίθμων στην οποία εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα, που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα, αλλά είναι μικρότερα σε μέγεθος.
Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος. Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).
Παράδειγμα βιβλίου : Το κάλπικο νόμισμα
Είστε εκτιμητής χρυσών νομισμάτων. Κάποιος σας φέρνει 128 χρυσά νομίσματα και σας λέει ότι ένα από αυτά είναι κάλπικο. Το κάλπικο νόμισμα είναι πανομοιότυπο στην εμφάνιση με τα υπόλοιπα, αλλά επειδή περιέχει λιγότερη ποσότητα χρυσού είναι λίγο πιο ελαφρύ.
Έχετε στη διάθεσή σας μια ζυγαριά ακριβείας με δύο δίσκους.
Πώς θα εντοπίσετε το κάλπικο νόμισμα με όσο το δυνατό λιγότερα ζυγίσματα;
Η μέθοδος σχεδίασης αλγορίθμων «Διαίρει και Βασίλευε» μπορεί να αποδοθεί με τα επόμενα βήματα:
- Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος.
- Το στιγμιότυπο του προβλήματος υποδιαιρείται σε υπο-στιγμιότυπα του ίδιου προβλήματος.
- Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο.
- Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υπο-στιγμιότυπα, έτσι ώστε να δοθεί η συνολική λύση του προβλήματος.
Η υλοποίηση της μεθόδου «Διαίρει και Βασίλευε» γίνεται με την επαναληπτική προσέγγιση (με διαδοχικές επαναλήψεις).
Ο μέγιστος αριθμός των συγκρίσεων (επαναλήψεων) που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο «n» ταξινομημένων στοιχείων, συμπεριλαμβανομένης και της περίπτωσης μη ύπαρξης του στοιχείου, δίνεται από το ακέραιο μέρος του [log2(n)+1] (με στρογγυλοποίηση προς τα κάτω).
(log2(n) = x => 2^x = n)
Επομένως, για την εύρεση του μέγιστου πλήθους των επαναλήψεων θεωρείται γνωστό το log2(n). Για παράδειγμα, σε ένα σύνολο 100 ταξινομημένων στοιχείων (n=100), ο μέγιστος αριθμός συγκρίσεων (επαναλήψεων) είναι: [log2(100)+1]=[6,643856+1]=[7,643856]=7.
Ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου «Διαίρει και Βασίλευε» είναι η «Δυαδική αναζήτηση», η οποία εφαρμόζεται μόνο στην περίπτωση ταξινομημένου συνόλου στοιχείων (π.χ. οι αριθμοί από το 1 έως το 100, τα στοιχεία ενός ταξινομημένου μονοδιάστατου πίνακα κ.ά.
Παράδειγμα 1 – Μάντεψε τον αριθμό (παιχνίδι με αντίπαλο τον υπολογιστή)σελ 70
Ένα παιδί παίζει με τον υπολογιστή το παιχνίδι «Μάντεψε τον αριθμό». Οι κανόνες του παιχνιδιού είναι οι εξής:
• Το παιδί αποτυπώνει στο μυαλό του έναν αριθμό από το 1 έως το 100.
• Ο υπολογιστής προσπαθεί να μαντέψει τον αριθμό το πολύ σε 7 προσπάθειες [log2(100)+1]=[6,643856+1]=[7,643856]=7
• Κάθε φορά που ο υπολογιστής προτείνει έναν αριθμό, με κατάλληλο μήνυμα στην οθόνη, ρωτά το παιδί να του απαντήσει, μέσω του πληκτρολογίου, αν ο αριθμός που μάντεψε ο υπολογιστής, είναι αυτός που έχει βάλει το παιδί στο μυαλό του ή αν είναι μεγαλύτερος ή
μικρότερος.
Να αναπτύξετε πρόγραμμα που να υλοποιεί το παραπάνω παιχνίδι:
1. Ο υπολογιστής με κατάλληλο μήνυμα σας ζητάει να σκεφτείτε έναν ακέραιο αριθμό από το 1 μέχρι το 100.
2. Ο υπολογιστής εμφανίζει κατάλληλο μήνυμα που σας πληροφορεί ότι θα βρει τον αριθμό το πολύ με 7 προσπάθειες.
3. Ο υπολογιστής με κατάλληλο μήνυμα προτείνει έναν ακέραιο αριθμό και στη συνέχεια (μέσω κατάλληλου μηνύματος) ζητάει να πληκτρολογήσετε αν ο αριθμός αυτός είναι ίδιος, μεγαλύτερος ή μικρότερος από τον αριθμό που είχατε σκεφτεί.
4. Όταν ο υπολογιστής μαντέψει τον αριθμό που σκεφθήκατε, εμφανίζει στην οθόνη κατάλληλο μήνυμα με τον αριθμό αυτό, καθώς και τον αριθμό των προσπαθειών που έκανε μέχρι να τον βρει.
|
ΠΡΟΓΡΑΜΜΑ μάντεψε_τον_αριθμό
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: προσ, αρχη_, τελος, μεση, απαντηση
ΛΟΓΙΚΕΣ: βρεθηκε
ΧΑΡΑΚΤΗΡΕΣ: απ
ΑΡΧΗ
ΓΡΑΨΕ 'Σκέψου έναν ακέραιο αριθμό από το 1 μέχρι το 100'
ΓΡΑΨΕ ' και θα τον μαντέψω το πολύ σε 7 προσπάθειες'
ΓΡΑΨΕ ' αρκεί να απαντάς ειλικρινά στις ερωτήσεις μου: '
ΓΡΑΨΕ
αρχη_<- 1
τελος <- 100
προσ <- 0
βρεθηκε <- ΨΕΥΔΗΣ
ΟΣΟ αρχη_<=τελος ΚΑΙ βρεθηκε=ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
|
Οι μεταβλητές : αρχη_ και τέλος ορίζουν το εύρος των αριθμών στο οποίο αναζητείται ένας αριθμός
Σε κάθε επανάληψη, το εύρος αυτό αλλάζει, οπότε σε κάθε επανάληψη διαχειριζόμαστε ένα μικρότερο στιγμιότυπο του ίδιου προβλήματος
|
προσ <- προσ + 1
μεση <- (αρχη_ + τελος) div 2
ΓΡΑΨΕ 'Προσπάθεια ', προσ, 'η'
ΓΡΑΨΕ ' Είναι ο αριθμός ', μεση, '; '
ΓΡΑΨΕ 'Δώσε Ν(ΝΑΙ) ή Ο(ΟΧΙ):' |
ενημέρωση του μετρητή προσπαθειών -προσ-
εύρεση του μεσαίου αριθμού (μεση) στο εύρος από : αρχή_ έως τελος
εμφάνιση του μεσαίου αριθμού και μηνυμάτων προς το χρήστη
|
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ απ
ΑΝ απ<>'Ν' ΚΑΙ απ<>'ν' ΚΑΙ απ<>'Ο' ΚΑΙ απ<>'ο' ΤΟΤΕ
ΓΡΑΨΕ 'Λάθος απάντηση. Ξαναπροσπάθησε....'
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ απ='Ν' Η απ='ν' Η απ='Ο' Η απ='ο' |
διάβασμα της απάντησης του χρήστης σχετικά με το αν ο αριθμός του, είναι ο μεσαίος αριθμός που προτείνει το πρόγραμμα, με έλεγχο εγκυρότητας της απάντησης
|
ΑΝ απ='Ν' Η απ ='ν' ΤΟΤΕ
βρεθηκε <- ΑΛΗΘΗΣ
ΓΡΑΨΕ 'Τον βρήκα σε ',προσ,' προσπάθεια/ες...' |
αν η απάντηση του χρήστη είναι Ν ή ν τότε το πρόγραμμα βρήκε τον αριθμό του χρήστη
η μεταβλητή βρέθηκε γίνεται αληθής ώστε να τερματίσει η επανάληψη
|
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Ο αριθμός που έβαλες είναι '
ΓΡΑΨΕ '(1)μεγαλύτερος ή (2)μικρότερος...'
ΓΡΑΨΕ 'Δώσε απάντηση 1 ή 2: '
ΔΙΑΒΑΣΕ απαντηση
ΑΝ απαντηση = 1 ΤΟΤΕ
αρχη_<- μεση + 1
ΑΛΛΙΩΣ
τελος <- μεση - 1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ |
αν η απάντηση του χρήστη δεν είναι Ν ή ν τότε το πρόγραμμα ρωτά το χρήστη αν ο αριθμός του είναι μεγαλύτερος ή μικρότερος από τον μεσαίο αριθμό
αν ο χρήστης απαντήσει ότι ο αριθμός του είναι μεγαλύτερος από τον μεσαίο αριθμό τότε ενημερώνεται η αρχή_ με τον αριθμό που αντιστοιχεί στο μεσαίο αριθμό (μέση) + 1
Με αυτόν το τρόπο απορρίπτονται, θέτονται εκτός ελέγχου, οι αριθμοί στο πρώτο μισό του εύρους των αριθμών
Αντίστοιχα, αν ο χρήστης απαντήσει ότι ο αριθμός του είναι μικρότερος από τον μεσαίο αριθμό τότε ενημερώνεται το τέλος με τον αριθμό που αντιστοιχεί στο μεσαίο αριθμό (μέση) - 1 και απορρίπτονται οι αριθμοί στο δεύτερο μισό του εύρους των αριθμών
|
|
ΓΡΑΨΕ '______________________________'
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
|
|
ΑΝ προσ > 7 Η αρχη_ > τελος ΤΟΤΕ
ΓΡΑΨΕ 'Δε βρήκα τον αριθμό σε 7 προσπάθειες'
ΓΡΑΨΕ 'γιατί δεν είσαι ειλικρινής ή '
ΓΡΑΨΕ 'έκανες κάτι λάθος στη διαδικασία '
ΓΡΑΨΕ ' που συμφωνήσαμε'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ μάντεψε_τον_αριθμό |
|
