Αρχική Forum
Ρωτήστε κάτι
Προσωπικές Συζητήσεις
Πανελλαδικές
Αγγελίες
Συνδεδεμένοι Χρήστες
Λίστα Αποκλεισμένων
Υπεύθυνοι του Forum
e-steki
infinity
Εκκολαπτόμενο μέλος
Ο Παναγιώτης αυτή τη στιγμή δεν είναι συνδεδεμένος. Έχει γράψει 190 μηνύματα.
10-06-12
14:36
Γειά σας,
Σε αυτό το thread θα δημοσιεύουμε προβλήματα και γρίφους που θα σχετίζονται με κάποιο αλγόριθμο και για να επιλυθούν, χρειάζεται συνδυαστική σκέψη και ευρηματικότητα.Η λύση του οποιουδήποτε προβλήματος θα θεωρείται σωστή, αν μπορεί να δώσει σωστή απάντηση σε πραγματικές συνθήκες.Η δημοσίευση ξερών, πηγαίων κωδίκων δεν ενδιαφέρει κανέναν, το θέμα με τα προβλήματα αυτά είναι να περιγράψουμε τον τρόπο σκέψης που θα ακολουθούσαμε για να τα λύσουμε, παρ' ολ'αυτά αν κάποιος μπορεί και θέλει να συνοδεύσει την σκέψη του με κάποιον κώδικα μπορεί κάλλιστα να το κάνει.
Ξεκινάω εγώ με ένα ωραίο και εύκολο:
Κρυμμένος θησαυρός
Εσύ και ένας φίλος σου παίζετε ένα παιχνίδι κρυμμένου θησαυρού. Υπάρχουν Ν (1<=Ν<=1.000.000) κουτιά αριθμημένα από το 1 έως το Ν και σε ένα από αυτά ο φίλος σου έχει κρύψει ένα αντικείμενο. Στόχος σου είναι να βρεις σε ποιο από αυτά είναι κάνοντας όσο το δυνατόν πιο λίγες ερωτήσεις.Οι ερωτήσεις που μπορείς να κάνεις είναι 2 διαφορετικές:
α) Ερώτηση για το αν το αντικείμενο βρίσκεται στο κουτί x μέσω της συνάρτησης ishidden(x). Οι πιθανές απαντήσεις στην ερώτηση αυτή είναι:
0 για όχι
1 για ναι
Σε περίπτωση καταφατικής απάντησης το παιχνίδι τελειώνει.
β) Ερώτηση για το αν το κουτί x βρίσκεται πιο κοντά στο στόχο από το κουτί y μέσω της συνάρτησης compare(x,y). Η ερώτηση αυτή έχει 3 διαφορετικές πιθανές απαντήσεις:
1 σε περίπτωση που το κουτί x βρίσκεται πιο κοντά στο στόχο από το κουτί y.
0 σε περίπτωση που τα κουτιά x και y ισαπέχουν από το στόχο.
-1 σε περίπτωση που το κουτί y βρίσκεται πιο κοντά στο στόχο από το κουτί x.
Πρέπει πρώτα να ζητήσεις το πλήθος Ν των κουτιών πριν κάνεις οποιαδήποτε ερώτηση μέσω της συνάρτησης getN().
Πηγή:hellenico.gr
Έχω αλλάξει λίγο την εκφώνηση του προβλήματος για να αποφύγουμε τις ανατριχιαστικές προγραμματιστικές λεπτομέρειες.Όποιoν τον μπερδεύουν οι συναρτήσεις μπορεί να αγνοήσει και αυτές και να επικεντρωθεί μόνο στις ερωτήσεις.
Bonus ερώτηση(για τους πληροφορικάριους): πως λέγεται ο αλγόριθμος που θα χρησιμοποιήσουμε για την επίλυση;Γράψτε πολυπλοκότητα χρόνου και μνήμης.
Σε αυτό το thread θα δημοσιεύουμε προβλήματα και γρίφους που θα σχετίζονται με κάποιο αλγόριθμο και για να επιλυθούν, χρειάζεται συνδυαστική σκέψη και ευρηματικότητα.Η λύση του οποιουδήποτε προβλήματος θα θεωρείται σωστή, αν μπορεί να δώσει σωστή απάντηση σε πραγματικές συνθήκες.Η δημοσίευση ξερών, πηγαίων κωδίκων δεν ενδιαφέρει κανέναν, το θέμα με τα προβλήματα αυτά είναι να περιγράψουμε τον τρόπο σκέψης που θα ακολουθούσαμε για να τα λύσουμε, παρ' ολ'αυτά αν κάποιος μπορεί και θέλει να συνοδεύσει την σκέψη του με κάποιον κώδικα μπορεί κάλλιστα να το κάνει.
Ξεκινάω εγώ με ένα ωραίο και εύκολο:
Κρυμμένος θησαυρός
Εσύ και ένας φίλος σου παίζετε ένα παιχνίδι κρυμμένου θησαυρού. Υπάρχουν Ν (1<=Ν<=1.000.000) κουτιά αριθμημένα από το 1 έως το Ν και σε ένα από αυτά ο φίλος σου έχει κρύψει ένα αντικείμενο. Στόχος σου είναι να βρεις σε ποιο από αυτά είναι κάνοντας όσο το δυνατόν πιο λίγες ερωτήσεις.Οι ερωτήσεις που μπορείς να κάνεις είναι 2 διαφορετικές:
α) Ερώτηση για το αν το αντικείμενο βρίσκεται στο κουτί x μέσω της συνάρτησης ishidden(x). Οι πιθανές απαντήσεις στην ερώτηση αυτή είναι:
0 για όχι
1 για ναι
Σε περίπτωση καταφατικής απάντησης το παιχνίδι τελειώνει.
β) Ερώτηση για το αν το κουτί x βρίσκεται πιο κοντά στο στόχο από το κουτί y μέσω της συνάρτησης compare(x,y). Η ερώτηση αυτή έχει 3 διαφορετικές πιθανές απαντήσεις:
1 σε περίπτωση που το κουτί x βρίσκεται πιο κοντά στο στόχο από το κουτί y.
0 σε περίπτωση που τα κουτιά x και y ισαπέχουν από το στόχο.
-1 σε περίπτωση που το κουτί y βρίσκεται πιο κοντά στο στόχο από το κουτί x.
Πρέπει πρώτα να ζητήσεις το πλήθος Ν των κουτιών πριν κάνεις οποιαδήποτε ερώτηση μέσω της συνάρτησης getN().
Πηγή:hellenico.gr
Έχω αλλάξει λίγο την εκφώνηση του προβλήματος για να αποφύγουμε τις ανατριχιαστικές προγραμματιστικές λεπτομέρειες.Όποιoν τον μπερδεύουν οι συναρτήσεις μπορεί να αγνοήσει και αυτές και να επικεντρωθεί μόνο στις ερωτήσεις.
Bonus ερώτηση(για τους πληροφορικάριους): πως λέγεται ο αλγόριθμος που θα χρησιμοποιήσουμε για την επίλυση;Γράψτε πολυπλοκότητα χρόνου και μνήμης.
Σημείωση: Το μήνυμα αυτό γράφτηκε 12 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
