Αποστολέας Θέμα: Πώς βρίσκω τη διαδρομή  (Αναγνώστηκε 1560 φορές)

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 516
  • There can be only one...may it be AEPP.
Πώς βρίσκω τη διαδρομή
« στις: 11 Δεκ 2013, 11:31:38 πμ »
Γειά σε όλους.
Ας υποθέσουμε πως έχω ενα δισδιάστατο πίνακα 50χ5. Σε κάθε θέση του πίνακα αποθηκεύεται ενα νούμερο από το 1 μέχρι το 50 ανακατεμένα και επιτρέπονται και επαναλήψεις. Διαβάζω από το πληκτρολόγιο μια γραμμά του πίνακα από εκεί που ξεκινάω και μια γραμμή του πίνακα εκεί όπου θέλω να καταλλήξω(αυτές να είναι διαφορετικές). Παράδειγμα το 5 και το 14  Στη γραμμή 5 υπάρχουν τα νούμερα 3,7,45,9,2. Οπότε ξεκινάω με το 3 το οποίο μας οδηγεί στη γραμμή 3 του πίνακα η οποία έχει άλλους 5 αριθμούς και ξαναεπιλέγω τον πρώτο αριθμό κτλ μέχρι να βρεθεί στη διαδρομή μου ο αριθμός 14 οπότε και σταματάω. Συνεχίζω με το 3 πάλι από την αρχή αλλά στη 3η γραμμή δεν παίρνω πλέον το 1ο νούμερο που συναντάω αλλά το δεύτερο με συνέπεια η διαδρομή μου να αλλάξει.
Υπάρχει κάποιος τρόπος να βρεθούν όλες οι "διαδρομές" που ζητάω , γιατί δεν μπορώ να σκεφτώ κάτι. :D

Υ.Γ. Όποιος κατάλαβε τί ρωτάω είναι "ήρωας ανάμεσά μας"  :)
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2153
Απ: Πώς βρίσκω τη διαδρομή
« Απάντηση #1 στις: 11 Δεκ 2013, 02:11:05 μμ »
Πώς εξασφαλίζεται ότι δεν θα μπει σε ατέρμονα;
Ότι σε κάθε γραμμή παίρνει πάντα το επόμενο;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

odysseas

  • Ομάδα διαγωνισμάτων 2011
  • *
  • Μηνύματα: 842
Απ: Πώς βρίσκω τη διαδρομή
« Απάντηση #2 στις: 11 Δεκ 2013, 02:33:29 μμ »
Αν κατάλαβα καλά περιγράφεις --περίπου-- μια πρώτα-κατά-βάθος αναζήτηση. Αυτή είναι μια διαδικασία που χρησιμοποιεί μια στοίβα S και πάει περίπου ως εξής:

Push στην S την γραμμή εκκίνησης
ΟΣΟ η S δεν είναι άδεια ΕΠΑΝΑΛΑΒΕ
  Pop από την S τον αριθμό μια γραμμής
  Αν η γραμμή δεν είναι η τελική TOTE
    Push στην S τα περιεχόμενα της γραμμής
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
 
Αν, όπως γράφει ο petrosp13, υπάρχει το ενδεχόμενο κύκλων, τότε θα πρέπει να χρησιμοποιήσεις επιπλέον και μια λίστα V των γραμμών που έχεις ήδη επισκεφθεί και να μην τις ξαναβάζεις στην στοίβα S.

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 516
  • There can be only one...may it be AEPP.
Απ: Πώς βρίσκω τη διαδρομή
« Απάντηση #3 στις: 13 Δεκ 2013, 10:27:59 πμ »
Βασικά το όλο concept ήταν το εξής:
Έχω εναν πίνακα ορισμένων θέσεων ο οποίος θα είχε τα ονόματα όλων των δρόμων ενός μικρού χωριού.
Και έναν πίνακα δισδιάστατο ο οποίος σε κάθε του γραμμή θα είχε το πολύ μέχρι 10 νούμερα που θα έδειχναν στο μονοδιάστατο πίνακα τον δρόμο με τον οποίο διασταυρώνονται.
Οπότε με μια αναζήτηση κάποιος θα έδινε την αφετηρία και τον τερματικό δρόμο και θα βρίσκονταν όλες οι δυνατές διαδρομές μέσω των τιμών του διασδιάστατου που θα έδειχναν σε άλλο κελί του μονοδιάστατου και συνεπώς σε άλλη γραμμή του μονοδιάτατου, για να φτάσει κάποιος στον προορισμό του.
Έπειτα θα ψάχναμε να βρούμε την διαδρομή με τους λιγότερους δρόμους στη διαδρομή.
Αυτό θα μπορούσε τότε να εμπλουτιστεί με εναν πίνακα με χιλιομετρικές αποστάσεις και λοιπά. Σαν ενα υποτυπώδες GPS δηλαδή.
Δεν ξέρω πως γίνεται γι'αυτό το σταματάω εδώ.
Ευχαριστώ τον Πέτρο και το Γιώργο παραπάνω για τα post τους.
« Τελευταία τροποποίηση: 13 Δεκ 2013, 10:12:18 μμ από nikolasmer »
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 179
Απ: Πώς βρίσκω τη διαδρομή
« Απάντηση #4 στις: 26 Μάι 2018, 07:18:44 πμ »
Γειά σε όλους.
Ας υποθέσουμε πως έχω ενα δισδιάστατο πίνακα 50χ5. Σε κάθε θέση του πίνακα αποθηκεύεται ενα νούμερο από το 1 μέχρι το 50 ανακατεμένα και επιτρέπονται και επαναλήψεις. Διαβάζω από το πληκτρολόγιο μια γραμμά του πίνακα από εκεί που ξεκινάω και μια γραμμή του πίνακα εκεί όπου θέλω να καταλλήξω(αυτές να είναι διαφορετικές). Παράδειγμα το 5 και το 14  Στη γραμμή 5 υπάρχουν τα νούμερα 3,7,45,9,2. Οπότε ξεκινάω με το 3 το οποίο μας οδηγεί στη γραμμή 3 του πίνακα η οποία έχει άλλους 5 αριθμούς και ξαναεπιλέγω τον πρώτο αριθμό κτλ μέχρι να βρεθεί στη διαδρομή μου ο αριθμός 14 οπότε και σταματάω. Συνεχίζω με το 3 πάλι από την αρχή αλλά στη 3η γραμμή δεν παίρνω πλέον το 1ο νούμερο που συναντάω αλλά το δεύτερο με συνέπεια η διαδρομή μου να αλλάξει.
Υπάρχει κάποιος τρόπος να βρεθούν όλες οι "διαδρομές" που ζητάω , γιατί δεν μπορώ να σκεφτώ κάτι. :D

Υ.Γ. Όποιος κατάλαβε τί ρωτάω είναι "ήρωας ανάμεσά μας"  :)

τσεκαρε τη λυση που εδωσα.νομιζω κατι τετοιο θες.τη δοκιμασα για πινακα 4*5 και  ξεκινωντας παντα απο την 1 να παω στην 4 γραμμη.η μετατροπη της να  επιλεγει ο χρηστης ειναι απλη.περασαν χρονια απο τοτε που την εβαλες αλλα μου φανηκε ενδιαφερον και την εκανα.δεν ξερω αν μου ξεφυγε κατι απο τα αποτελεσματα που εβγαλε νομιζω ειναι σωστη