Αποστολέας Θέμα: Ο Λαβύρινθος του Θησέα και ο κανόνας δεξιού χεριού.  (Αναγνώστηκε 2203 φορές)

unpsofable

  • Νέος
  • *
  • Μηνύματα: 2
Καλησπέρα! Παρακάτω παραθέτω μια ωραία άσκηση κατ εμε η οποία βασίζεται στον προγραμματισμό η/υ με χρηση της γλωσσας Java.

Στην ελληνική μυθολογία ο Θησέας κατoρθώνει να δραπετεύσει από το λαβύρινθο του Μινώταυρου ξετυλίγοντας
ένα κουβάρι σπάγκο καθώς προχωρά και ακολουθώντας τη διαδρομή του σπάγκου μέχρι την έξοδο. Η στρατηγική
του Θησέα παριστάνει έναν αλγόριθμο για την έξοδο από έναν λαβύρινθο, αλλά δεν είναι και ο μοναδικός
αλγόριθμος που θα μπορούσε να έχει χρησιμοποιήσει για να λύσει αυτό το πρόβλημα. Για παράδειγμα, εάν ένας
λαβύρινθος δεν έχει εσωτερικούς βρόχους, μπορείτε να βγείτε από αυτόν αν αγγίζετε πάντα με το δεξιό σας χέρι
τον τοίχο. Αυτός ο αλγόριθμος ονομάζεται κανόνας του δεξιού χεριού (right-hand rule).
Για παράδειγμα, φανταστείτε ότι ο Θησέας χάνεται στο λαβύρινθο που φαίνεται παρακάτω. Σε αυτό το διάγραμμα,
η θέση του Θησέα σημειώνεται με το γράμμα θήτα (Θ)


Για να βγει από τον λαβύρινθο, ο Θησέας ακολούθησε τη διαδρομή που παρουσιάζεται στο επόμενο διάγραμμα
με τη διακεκομμένη γραμμή, την οποία μπόρεσε να ακολουθήσει ακουμπώντας συνεχώς το δεξί του χέρι στον
τοίχο.  (θα το δειτε στα συνημμένα)

Υποθέστε ότι σας έχει ζητηθεί να γράψετε ένα πρόγραμμα ώστε να δραπετεύσει από έναν λαβύρινθο ένα ρομπότ.
Υποθέστε ότι έχετε πρόσβαση σε μια κλάση με το όνομα MazeRunningRobot που υλοποιεί τις ακόλουθες
μεθόδους:
 
void moveForward() /* Κίνηση εμπρός κατά ένα τετράγωνο */
void turnRight() /* Δεξιά στροφή χωρίς μετακίνηση */
void turnLeft() /* Αριστερή στροφή χωρίς μετακίνηση */
boolean isBlocked() /* Αληθής αν βλέπει τοίχο */
boolean isOutside() /* Αληθής αν είναι έξω από λαβύρινθο */
 
Χρησιμοποιήστε αυτές τις μεθόδους για να γράψετε μια αλγοριθμική μέθοδο
private void solveMaze (robot MazeRunningRobot)
που βγάζει το ρομπότ έξω από το λαβύρινθο χρησιμοποιώντας τον κανόνα του δεξιού χεριού.


Ως προς την επίλυση λοιπόν της άσκησης χρειάζεται να φτιάξουμε μόνο τη μέθοδο που το ρομποτ θα καταλαβαίνει για να βγει από τον λαβύρινθο,βασει πάντα του κανόνα του δεξιου χεριού.

Θεωρώ πως με μια επανάληψη και μέσα της κάποιες συνθήκες if επιλύεται.
Τι πιστεύετε;

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3517
  • to Iterate is human to Recurse divine
Απ: Ο Λαβύρινθος του Θησέα και ο κανόνας δεξιού χεριού.
« Απάντηση #1 στις: 23 Δεκ 2013, 10:29:30 μμ »
Θα μας επιτρέψεις να σου απαντήσουμε μετά την προθεσμία παράδοσης της εργασίας που είναι στις 2-3 Ιανουαρίου αν θυμάμαι καλά?
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

unpsofable

  • Νέος
  • *
  • Μηνύματα: 2
Απ: Ο Λαβύρινθος του Θησέα και ο κανόνας δεξιού χεριού.
« Απάντηση #2 στις: 26 Δεκ 2013, 11:20:58 μμ »
Θα μας επιτρέψεις να σου απαντήσουμε μετά την προθεσμία παράδοσης της εργασίας που είναι στις 2-3 Ιανουαρίου αν θυμάμαι καλά?

Το έλυσα,οπότε πιστευω μπορω να περιμένω μεχρι τη διόρθωση των ασκήσεων.Ευχαριστώ για την προθυμία.

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Ο Λαβύρινθος του Θησέα και ο κανόνας δεξιού χεριού.
« Απάντηση #3 στις: 28 Δεκ 2013, 06:19:10 πμ »
Πιστεύω ότι θα ήταν πιο ενδιαφέρον ένα γενικό πρόβλημα maze, που να σε έβαζε στη λογική του A* πχ για να το επιλύσεις.