Πόρτες ντουλαπιών (locker doors)

Share

Σας παραθέτω μια ενδιαφέρουσα σπαζοκεφαλιά που συνάντησα ξεφυλλίζοντας ένα βιβλίο σχετικό με την ανάλυση και τη σχεδίαση αλγορίθμων (The design and analysis of algorithms, Anany Levitin). Σας καλώ να αναπτύξετε αλγόριθμο σε ψευδογλώσσα ο οποίος θα λύνει το πρόβλημα. Αν ο αλγόριθμός σας είναι σωστός θα μπορέσετε να δείτε την λύση του προβλήματος τρέχοντάς τον σε κάποιο περιβάλλον εκτέλεσης της ΓΛΩΣΣΑΣ όπως είναι αυτό ή αυτό. Αρκούν γνώσεις χειρισμού μονοδιάστατων πινάκων και ...λίγη σκέψη:

Υπάρχουν ν ντουλάπια σε έναν θάλαμο, διαδοχικά αριθμημένα από το 1 μέχρι το ν. Αρχικά οι πόρτες των ντουλαπιών είναι όλες κλειστές. Πραγματοποιούμε ν περάσματα, ξεκινώντας κάθε φορά από το ντουλάπι #1. Στο ι-οστό πέρασμα (ι=1,2,...,ν) αλλάζουμε την κατάσταση κάθε ι-οστής πόρτας ντουλαπιού (αν η πόρτα είναι κλειστή την ανοίγουμε και αν είναι ανοιχτή την κλείνουμε).

Για παράδειγμα, μετά το πρώτο πέρασμα, κάθε πόρτα είναι ανοιχτή. Στο δεύτερο πέρασμα πειράζουμε μόνο τα άρτια αριθμημένα ντουλάπια (2ο, 4ο κλπ), οπότε μετά το δεύτερο πέρασμα οι άρτιες πόρτες είναι κλειστές και οι περιττές ανοιχτές. Την τρίτη φορά, κλείνουμε την πόρτα του ντουλαπιού #3 (που είχε ανοίξει στο πρώτο πέρασμα), ανοίγουμε την πόρτα #6 (που είχε κλείσει στο δεύτερο πέρασμα) κλπ.

Μετά το τελευταίο πέρασμα, ποιές πόρτες είναι ανοιχτές και ποιες κλειστές;

Σημείωση: Αν θελήσετε να εκτελέσετε τον αλγόριθμο σε κάποιο από τα παραπάνω περιβάλλοντα, θα πρέπει να ορίσετε μια τιμή για το ν (μην ξεχνάτε, οι πίνακες είναι στατικές δομές Laughing)

Μια λύση μπορείτε να δείτε εδώ.