Μάθημα : Γ΄Λυκείου Πληροφορική

Η δυαδική αναζήτηση βασίζεται στη μέθοδο "Διαίρει και Βασίλευε"

Η μέθοδος "Διαίρει και Βασίλευε" βασίζεται στην "από πάνω προς τα κάτω" ανάλυση.

Η υλοποίηση της μεθόδου "Διαίρει και Βασίλευε" πραγματοποιείται με διαδοχικές επαναλήψεις.

Ο μέγιστος αριθμών των επαναλήψεων που απαιτούνται για την εύρεση ενός στοιχείου σε Ν ταξινομημένα στοιχεία είναι:

Η "Διαίρει και Βασίλευε" αποτελεί μια μέθοδο σχεδίασης αλγορίθμων

Η μέθοδος "Διαίρει και Βασίλευε" βασίζεται στην υποδιαίρεση ενός προβλήματος σε μικρότερα, των οποίων η σύνθεση των λύσεων οδηγεί στην επίλυση του αρχικού προβλήματος.

Ο συνδυασμός των λύσεων των υποπροβλημάτων στα οποία αναλύθηκε ένα πρόβλημα με τη μέθοδο "Διαίρει και Βασίλευε" είναι το τελικό βήμα της σχετικής μεθόδου.

Η μέθοδος "Διαίρει και Βασίλευε" υλοποιείται και με τη χρήση επαναληπτικών διαδικασιών.

Σύμφωνα με τη μέθοδο "Διαίρει και Βασίλευε", το κάθε στιγμιότυπο του προβλήματος μπορεί να αναλυθεί σε 2 ή περισσότερα μικρότερα υπο-στιγμιότυπα, μικρότερου μεγέθους.

Σύμφωνα με τη μέθοδο "Διαίρει και Βασίλευε", η λύση του αρχικού προβλήματος αναλύεται στις λύσεις των επιμέρους υποπροβλημάτων.

Η μέθοδος "Διαίρει και Βασίλευε" αποτελεί μια μέθοδο _______________ αλγορίθμων στην οποία ένα ____________ υποδιαιρείται σε μικρότερα υποπροβλήματα, που έχουν την ίδια _______________ με το αρχικό πρόβλημα, αλλά είναι __________________ σε μέγεθος. Τα ___________________ αυτά διαιρούνται σε σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ. Η επίλυση του αρχικού προβλήματος έγκειται στη σταδιακή ______________ των μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος.

Η μέθοδος σχεδίασης αλγορίθμων "Διαίρει και Βασίλευε" περιέχει τα επόμενα βήματα: α. Δίνεται για επίλυση ένα ______________ ενός προβλήματος. β. Το στιγμιότυπο του προβλήματος _________________ σε μικρότερα στιγμιότυπα του ίδιου προβλήματος. γ. Δίνεται ανεξάρτητη _________ σε κάθε υπο-στιγμιότυπο. δ. _________________ οι μερικές λύσεις που βρέθηκαν, ώστε να δοθεί η συνολική λύση του προβλήματος.

Ο μέγιστος αριθμός _________________ που απαιτούνται για την εύρεση ενός στοιχείου σε ένα σύνολο Ν _____________ στοιχείων με χρήση της μεθόδου "Διαίρει και Βασίλευε" είναι

Η μέθοδος σχεδίασης αλγορίθμων "Διαίρει και Βασίλευε" μπορεί να αποδοθεί με συγκεκριμένα βήματα. Να τα βάλετε σε σειρά:

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

Σε μια σειρά κάθονται αρκετοί άνθρωποι, με δείκτη αρίθμησης 1, 2, 3 κ.ο.κ., και παίζουν ένα παιχνίδι. Θεωρούμε ότι κάθε παίκτης έχει πόντους ζωής που είναι ο αριθμός που του αντιστοιχεί υψωμένος στο τετράγωνο. Για παράδειγμα ο παίκτης που κάθεται στη θέση 4 έχει 4^2 = 16 πόντους ζωής. Ένας παίκτης με πόντους ζωής Ρ, πόσους από τους παίκτες μπορεί να βγάλει από το παιχνίδι, αν θεωρήσουμε ότι α) κάθε φορά που αντιμετωπίζει κάποιον αντίπαλο χάνει τόσους πόντους όσοι είναι οι πόντοι του αντιπάλου και β) ότι τους αντιμετωπίζει με τη σειρά που κάθονται. Η λύση δίνεται στο παρακάτω πρόγραμμα, στο οποίο πρέπει να συμπληρώσετε τα κενά: