ΔΙΑΙΡΕΙ ΚΑΙ ΒΑΣΙΛΕΥΕ II - Μάντεψε τον αριθμό

ΔΙΑΙΡΕΙ ΚΑΙ ΒΑΣΙΛΕΥΕ II - Μάντεψε τον αριθμό

Η «Διαίρει και Βασίλευε» (divide and conquer) αποτελεί μια μέθοδο σχεδίασης αλγορίθμων στην οποία εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα, που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα, αλλά είναι μικρότερα σε
μέγεθος. Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα
υποπροβλήματα κ.ο.κ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο
το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος.
Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).

Χρησιμοποιώντας τη μέθοδο «Διαίρει και Βασίλευε» δοκιμάστε να παίξετε με έναν συμμαθητή ή μία συμμαθήτριά σας το παιχνίδι «Μάντεψε τον αριθμό», ως εξής: Σκεφθείτε έναν αριθμό από το 1 έως το 100 και ζητήστε από τον συμμαθητή ή τη συμμαθήτριά σας (παίκτης-1) να
μαντέψει τον αριθμό αυτόν με όσο το δυνατόν λιγότερες προσπάθειες.
• Ποια διαδικασία πρέπει να ακολουθήσει ο παίκτης-1 για να βρει τον αριθμό; Τι είδους
ερωτήσεις πρέπει να κάνει, ώστε να ελαχιστοποιήσει τις προσπάθειες που θα χρειαστούν;
• Ποιος είναι ο μέγιστος αριθμός προσπαθειών που θα χρειαστεί ο παίκτης-1 για να μαντέψει τον αριθμό;