Μέθοδος Διαίρει και Βασίλευε -1

Μέθοδος Διαίρει και Βασίλευε
Σε μια κατασκήνωση, μια ομάδα 13 παιδιών αποφασίζει να παίξει
το παιχνίδι «βρες το δαχτυλίδι».
Σύμφωνα με τους κανόνες, ένα από τα παιδιά (στο εξής Παιδί-1)
δίνει ένα δαχτυλίδι σε ένα από τα υπόλοιπα 12και γυρνάει το σώμα του,
δίχως να έχει οπτική επαφή με τα υπόλοιπα.
Ένα παιδί κρύβει το δαχτυλίδι στην τσέπη του και όλοι μαζί κάθονται σε μια γραμμή
γνωρίζοντας ποιος έχει κρύψει το δαχτυλίδι.
Το Παιδί-1 που δε βλέπει τα υπόλοιπα, ισχυρίζεται ότι θα μαντέψει πάρα πολύ γρήγορα
πού βρίσκεται το δαχτυλίδι με την προϋπόθεση
ότι κάποιο παιδί (εκπρόσωπος) θα απαντά στις ερωτήσεις
που θα του κάνει με ένα ναι ή ένα όχι.
Το Παιδί-1 ζητά από τα μισά παιδιά της γραμμής
να κάνουν ένα βήμα μπροστά.
Στη συνέχεια, ρωτά τον εκπρόσωπο
εάν το δαχτυλίδι βρίσκεται στο δεύτερο «μισό» της γραμμής,
που είναι ένα βήμα πιο πίσω.
Όταν μάθει σε ποιο από τα δύο «μισά» βρίσκεται το δαχτυλίδι,
ζητά από τα παιδιά που βρίσκονται στο άλλο «μισό» να βγουν εκτός παιχνιδιού.
Η ίδια διαδικασία επαναλαμβάνεται με το «μισό» που βρίσκεται ακόμη στο παιχνίδι,
μέχρι να μείνουν μόνο δύο παιδιά, όπου θα γίνει και η τελευταία ερώτηση από το Παιδί-1.
Επομένως με τέσσερις ερωτήσεις, το Παιδί-1 εντόπισε το παιδί που έχει κρυμμένο το δαχτυλίδι.
Στο παρακάτω σχήμα παρουσιάζεται η περιγραφόμενη διαδικασία
κατά την οποία το παιδί με τη μπλε τσέπη έχει το δαχτυλίδι
και η διακεκομμένη κόκκινη γραμμή σηματοδοτεί το σημείο,
όπου κάθε φορά (σε κάθε επανάληψη) μειώνεται η γραμμή των παιδιών στο μισό.
Όλα τα παιδιά εντυπωσιάστηκαν από την ταχύτητα με την οποία το Παιδί-1 βρήκε το δαχτυλίδι
και προσπαθούν να ανακαλύψουν τον συστηματικό τρόπο με τον οποίο σκέφτηκε.
Το μόνο που ήξεραν ήταν ότι το Παιδί-1 χώρισε αρχικά το σύνολο των παιδιών σε δύο «μισά» (ίσες ομάδες)
και όταν ανακάλυπτε σε ποιο μισό βρισκόταν το δαχτυλίδι,
επαναλάμβανε την ίδια διαδικασία μέχρι τελικά να απομείνουν δύο παιδιά που υποχρεωτικά το ένα είχε το δακτυλίδι.
Για να μάθουν περισσότερα έψαξαν στο Διαδίκτυο και εντόπισαν ότι το παιχνίδι στο οποίο συμμετείχαν,
αποτελεί συγκεκριμένη μέθοδο επίλυσης προβλημάτων,
που εφαρμόζεται για τη γρήγορη αναζήτηση δεδομένων σε μια υπάρχουσα δομή δεδομένων
και ονομάζεται «Διαίρει και Βασίλευε».
(Divide and conquer)
Η «Διαίρει και Βασίλευε» (divide and conquer) αποτελεί μια μέθοδο σχεδίασης αλγορίθμων
στην οποία εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα,
που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα,
αλλά είναι μικρότερα σε μέγεθος.
Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ.
Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων,
ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος.
Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).
Προσπαθήστε να εφαρμόσετε τη μέθοδο «Διαίρει και Βασίλευε» στην παρακάτω δραστηριότητα.
Είστε εκτιμητής χρυσών νομισμάτων.
Κάποιος σας φέρνει 128 χρυσά νομίσματα
και σας λέει ότι ένα από αυτά είναι κάλπικο.
Το κάλπικο νόμισμα είναι πανομοιότυπο στην εμφάνιση με τα υπόλοιπα,
αλλά επειδή περιέχει λιγότερη ποσότητα χρυσού είναι λίγο πιο ελαφρύ.
Έχετε στη διάθεσή σας μια ζυγαριά ακριβείας με δύο δίσκους.
Πώς θα εντοπίσετε το κάλπικο νόμισμα με όσο το δυνατό λιγότερα ζυγίσματα;
Η μέθοδος σχεδίασης αλγορίθμων «Διαίρει και Βασίλευε» μπορεί να αποδοθεί με τα επόμενα βήματα:
1. Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος.
2. Το στιγμιότυπο του προβλήματος υποδιαιρείται
σε υπο-στιγμιότυπα του ίδιου προβλήματος.
3. Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο.
4. Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν
για τα υπο-στιγμιότυπα,
έτσι ώστε να δοθεί η συνολική λύση του προβλήματος.

[mariettatsitsimeli]

Εξαιρετικά τα γραφικά σου!! Πολύ ξεκάθαρος ο λόγος σου!! Είμαι της θεωρητικής κατεύθυνσης θα ήταν ευλογία να μας τα έλεγαν με τον δικό σου τρόπο οι καθηγητές των θετικών κατευθύνσεων..εκείνα τα χρόνια που πήγαινα σχολείο...
Μπράβο Μαριέττα 🍀

[anatoliichaika]

στο 4:20 στο προβλημα 3+6=9
Παντως ευχαριστω πολυ ηταν πολυ βοηθητικο το βιντεο σας