Κεφάλαιο 16.1 (σελ. 68-69) – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Δραστηριότητες

Δραστηριότητα 1 — Το κάλπικο νόμισμα (σελ. 68)

Είστε εκτιμητής χρυσών νομισμάτων. Κάποιος σας φέρνει 128 χρυσά νομίσματα και σας λέει ότι ένα από αυτά είναι κάλπικο. Το κάλπικο νόμισμα είναι πανομοιότυπο στην εμφάνιση με τα υπόλοιπα, αλλά επειδή περιέχει λιγότερη ποσότητα χρυσού είναι λίγο πιο ελαφρύ. Έχετε στη διάθεσή σας μια ζυγαριά ακριβείας με δύο δίσκους. Πώς θα εντοπίσετε το κάλπικο νόμισμα με όσο το δυνατό λιγότερα ζυγίσματα;

Σκέψη / Μεθοδολογία: Εφαρμόζουμε τη λογική «Διαίρει και Βασίλευε»: σε κάθε ζύγισμα χωρίζουμε το σύνολο των υποψήφιων νομισμάτων σε δύο ίσα μέρη και συγκρίνουμε το ένα έναντι του άλλου· η πλευρά που ανεβαίνει (είναι ελαφρύτερη) περιέχει σίγουρα το κάλπικο νόμισμα.

Λύση:

Χωρίζουμε τα 128 νομίσματα σε δύο ομάδες των 64 και τις ζυγίζουμε τη μία έναντι της άλλης. Η ζυγαριά δεν θα δείξει ισορροπία, αφού μία από τις δύο ομάδες περιέχει το ελαφρύτερο (κάλπικο) νόμισμα — κρατάμε την ελαφρύτερη ομάδα. Επαναλαμβάνουμε: 64→32→16→8→4→2→1, χωρίζοντας κάθε φορά στη μέση και κρατώντας την ελαφρύτερη ομάδα. Στο τελευταίο βήμα (2 νομίσματα) η ζυγαριά δείχνει απευθείας το κάλπικο.

Απάντηση: Χωρίζουμε επαναλαμβανόμενα το σύνολο των νομισμάτων στη μέση και ζυγίζουμε τις δύο ομάδες τη μία έναντι της άλλης, κρατώντας κάθε φορά την ελαφρύτερη ομάδα, μέχρι να απομείνουν δύο νομίσματα, όπου ένα τελευταίο ζύγισμα αποκαλύπτει το κάλπικο. Για 128 νομίσματα χρειάζονται ακριβώς 7 ζυγίσματα (log2(128)=7).

Πρόσεξε:

• Δεν χρειάζεται να ζυγίσουμε κάθε νόμισμα ξεχωριστά (128 ζυγίσματα) — η «Διαίρει και Βασίλευε» μειώνει το πλήθος των ζυγισμάτων από γραμμικό σε λογαριθμικό.

Δραστηριότητα 2 — Μάντεψε τον αριθμό (παιχνίδι με συμμαθητή) (σελ. 69)

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

Σκέψη / Μεθοδολογία: Ο παίκτης-1 πρέπει να ρωτά πάντα για τον μεσαίο αριθμό του τρέχοντος διαστήματος (δυαδική αναζήτηση), ώστε κάθε ερώτηση να αποκλείει το μισό των εναπομεινάντων υποψήφιων αριθμών. (Ενδεικτική απάντηση.)

Λύση:

Διαδικασία: ο παίκτης-1 ρωτά κάθε φορά για τον μεσαίο αριθμό του τρέχοντος διαστήματος [αρχή, τέλος] (αρχικά το 50 στο [1,100]) και ρωτά αν ο ζητούμενος αριθμός είναι μεγαλύτερος, μικρότερος ή ίσος· περιορίζει το διάστημα στο μισό ανάλογα με την απάντηση.

• Για [1,100]: μέγιστος αριθμός προσπαθειών = [log2(100)+1] = [6,643856+1] = 7.
• Για [1,1000]: μέγιστος αριθμός προσπαθειών = [log2(1000)+1] = [9,965784+1] = 10.

Παρότι τα δεδομένα δεκαπλασιάστηκαν, οι προσπάθειες αυξήθηκαν μόλις κατά 3 — λογαριθμική, όχι ανάλογη αύξηση.

Απάντηση: Ο παίκτης-1 ακολουθεί τη δυαδική αναζήτηση: προτείνει κάθε φορά τον μεσαίο αριθμό του τρέχοντος διαστήματος και περιορίζει το διάστημα στο μισό ανάλογα με την απάντηση. Για το [1,100] χρειάζονται το πολύ 7 προσπάθειες, για το [1,1000] το πολύ 10. Η αύξηση των προσπαθειών είναι λογαριθμική ως προς το πλήθος των δεδομένων — αποδεικνύοντας ότι η «Διαίρει και Βασίλευε» είναι εξαιρετικά αποτελεσματική ακόμη και για πολύ μεγάλο όγκο δεδομένων.

Πρόσεξε:

• Λάθος στρατηγική (τυχαίες μαντεψιές ή αύξηση κατά 1) δεν αξιοποιεί τη μέθοδο και μπορεί να χρειαστεί έως 100 ή 1000 προσπάθειες αντί για 7 ή 10.