Έχετε στη διάθεσή σας 2 αυγά και ένα κτίριο 100 ορόφων. Θέλετε να βρείτε τον υψηλότερο όροφο από τον οποίο ένα αυγό μπορεί να πέσει χωρίς να σπάσει (το «ασφαλές ύψος»), ελαχιστοποιώντας τον μέγιστο αριθμό ρίψεων που ίσως χρειαστούν.
Υποθέσεις:
-
Αν ένα αυγό δεν σπάσει, μπορεί να ξαναχρησιμοποιηθεί.
-
Αν ένα αυγό σπάσει, δεν ξαναχρησιμοποιείται.
-
Αν σπάσει σε κάποιον όροφο, θα σπάσει σε οποιονδήποτε ψηλότερο.
-
Αν δεν σπάσει σε κάποιον όροφο, τότε δεν θα σπάσει σε κανέναν χαμηλότερο.
Ζητούμενο:
-
Ποιος είναι ο ελάχιστος δυνατός αριθμός ρίψεων στη χειρότερη περίπτωση;
-
Διατυπώστε μια βέλτιστη στρατηγική που επιτυγχάνει αυτό το όριο.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου