Καστορο-φράγμα
(Βαθμός δυσκολίας: μέτριο)
Οι κάστορες μιας κοινότητας θέλουν να κατασκευάσουν ένα νέο φράγμα για τον ποταμό χρησιμοποιώντας τον ελάχιστο αριθμό ξύλινων κορμών. Επειδή είναι έξυπνοι, σκέφτονται να εκμεταλλευτούν τα μικρά νησάκια που υπάρχουν στον ποταμό. Στην παρακάτω εικόνα φαίνονται ο ποταμός, τα νησάκια, καθώς και ο αριθμός των κορμών που χρειάζονται για να φτιαχτεί κάθε τμήμα του φράγματος.
Ποιος είναι ο ελάχιστος αριθμός κορμών που χρειάζονται για να κατασκευαστεί το νέο φράγμα;
1. 14 κορμοί
2. 15 κορμοί
3. 16 κορμοί
4. 17 κορμοί
Λύση:
Αυτό είναι το βέλτιστο σχέδιο φράγματος:
Οι κάστορες θα χρειαστούν 4+4+3+4=15 κορμούς.
Θα έχετε δει δραστηριότητες στις οποίες αναζητάτε τη συντομότερη διαδρομή μεταξύ δυο σημείων. Η κατασκευή του φράγματος με τον μικρότερο αριθμό κορμών είναι ίδια με την περίπτωση της εύρεσης της συντομότερης διαδρομής μεταξύ δυο σημείων. Όταν προσπαθείτε να φτιάξετε το φράγμα με τον μικρότερο αριθμό κορμών, είναι σαν να προσπαθείτε να βρείτε τη συντομότερη διαδρομή από τη μια όχθη του ποταμού έως την άλλη, όπου το μήκος του μονοπατιού μετριέται με τον αριθμό των κορμών.
Είναι Πληροφορική!
Οι επιστήμονες Πληροφορικής είναι έξυπνοι αλλά βαριούνται εύκολα, πράγμα που είναι πολύ ωραίος συνδυασμός. Μαθαίνουν κάποια κόλπα και, όποτε αντιμετωπίζουν πρόβλημα, προσπαθούν να εφαρμόσουν κάποιο από αυτά. Στην περίπτωση αυτή, θα παρατηρούσαν ότι το να φτιάξουν ένα φράγμα κατά μήκος του ποταμού με τον μικρότερο αριθμό κορμών είναι ίδιο με το πέρασμα στην απέναντι όχθη με τον συντομότερο τρόπο. Με τον τρόπο αυτό μετατρέπουν ένα νέο πρόβλημα (την κατασκευή φραγμάτων) σε ένα γνωστό πρόβλημα (την εύρεση του συντομότερου μονοπατιού). Ο αλγόριθμος που χρησιμοποιούμε για την περίπτωση αυτή λέγεται αλγόριθμος του Dijkstra, από τον δημιουργό του E. W. Dijkstra, που υπήρξε ένας από τους επιστήμονες Πληροφορικής με τη σημαντικότερη επιρροή και ανακάλυψε πολλούς ενδιαφέροντες αλγόριθμους. Έτσι, οι επιστήμονες Πληροφορικής έχουν πολλά κόλπα στη διάθεσή τους!
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου