Μια αλυσίδα αποτελείται από 2047 κρίκους. Θέλουμε να την κόψουμε σε κάποια σημεία, ώστε με τα κομμάτια που προκύπτουν να μπορούμε να συνθέσουμε οποιοδήποτε μήκος — από 1 κρίκο έως 2047 κρίκους.
Ερώτημα: Πόσους κρίκους πρέπει να κόψουμε το ελάχιστο δυνατό για να το πετύχουμε;
🧩 Παράδειγμα με 7 κρίκους
Αν η αλυσίδα είχε μόνο 7 κρίκους, αρκεί να κόψουμε δύο κρίκους ώστε να προκύψουν κομμάτια με 1, 2 και 4 κρίκους. Με αυτά μπορούμε να συνθέσουμε όλα τα μήκη από 1 έως 7:
| Επιθυμητό μήκος | Κομμάτια που χρειάζονται |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2 + 1 |
| 4 | 4 |
| 5 | 4 + 1 |
| 6 | 4 + 2 |
| 7 | 4 + 2 + 1 |
❓ Το γενικό ερώτημα
Με βάση τη λογική του παραδείγματος, βρες τον ελάχιστο αριθμό κομμένων κρίκων για αλυσίδα 2047 κρίκων ώστε να μπορούμε να σχηματίζουμε κάθε δυνατό μήκος από 1 έως 2047.
1 σχόλιο:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 = 11 κομμάτια = 7 κομμένοι κρίκοι (με τους κομμένους φτιάχνουμε τα κομμάτια 1, 2 και 4)
ΑπάντησηΔιαγραφή