Click to Translate Whole Page to Read and Solve

Δευτέρα 22 Ιουλίου 2013

▪ Χρυσός Αλγόριθμος

"Η ερμηνεία είναι ο τρόπος που χρησιμοποιεί η διανόηση για να εκδικηθεί την τέχνη"
Susan Sontag
Ένα κουτί περιέχει 1359 νομίσματα τριών ειδών: Χρυσά,ασημένια και χάλκινα. Η πλειοψηφία των νομισμάτων (τουλάχιστον τα 680) είναι χρυσά. Δεν έχουμε όμως τρόπο (ας πούμε ότι είναι "καμουφλαρισμένα" ή βαμμένα) να ξεχωρίσουμε το είδος τους. Έχουμε όμως μία μηχανή που δέχεται 2 νομίσματα κάθε φορά, και μας απαντάει αν τα νομίσματα είναι από το ίδιο είδος ή όχι.
Ας ορίσουμε έναν αλγόριθμο που βρίσκει ένα χρυσό νόμισμα, να έχει έστω "Βάθος ν", αν κάθε νόμισμα που εισάγεται στη μηχανή, εισάγεται το πολύ ν φορές.
Βρείτε έναν αλγόριθμο (το σύστημα δηλαδή με το οποίο θα "τροφοδοτηθεί" με νομίσματα η μηχανή) που να έχει το μικρότερο δυνατό (το ελάχιστο) "βάθος ν", και βρίσκει σίγουρα κάποιο χρυσό νόμισμα.