Πώς βρίσκω τη διαδρομή

Ξεκίνησε από nikolasmer, 11 Δεκ 2013, 11:31:38 ΠΜ

« προηγούμενο - επόμενο »

nikolasmer

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

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

petrosp13

Πώς εξασφαλίζεται ότι δεν θα μπει σε ατέρμονα;
Ότι σε κάθε γραμμή παίρνει πάντα το επόμενο;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

odysseas

Αν κατάλαβα καλά περιγράφεις --περίπου-- μια πρώτα-κατά-βάθος αναζήτηση. Αυτή είναι μια διαδικασία που χρησιμοποιεί μια στοίβα S και πάει περίπου ως εξής:

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

nikolasmer

#3
Βασικά το όλο concept ήταν το εξής:
Έχω εναν πίνακα ορισμένων θέσεων ο οποίος θα είχε τα ονόματα όλων των δρόμων ενός μικρού χωριού.
Και έναν πίνακα δισδιάστατο ο οποίος σε κάθε του γραμμή θα είχε το πολύ μέχρι 10 νούμερα που θα έδειχναν στο μονοδιάστατο πίνακα τον δρόμο με τον οποίο διασταυρώνονται.
Οπότε με μια αναζήτηση κάποιος θα έδινε την αφετηρία και τον τερματικό δρόμο και θα βρίσκονταν όλες οι δυνατές διαδρομές μέσω των τιμών του διασδιάστατου που θα έδειχναν σε άλλο κελί του μονοδιάστατου και συνεπώς σε άλλη γραμμή του μονοδιάτατου, για να φτάσει κάποιος στον προορισμό του.
Έπειτα θα ψάχναμε να βρούμε την διαδρομή με τους λιγότερους δρόμους στη διαδρομή.
Αυτό θα μπορούσε τότε να εμπλουτιστεί με εναν πίνακα με χιλιομετρικές αποστάσεις και λοιπά. Σαν ενα υποτυπώδες GPS δηλαδή.
Δεν ξέρω πως γίνεται γι'αυτό το σταματάω εδώ.
Ευχαριστώ τον Πέτρο και το Γιώργο παραπάνω για τα post τους.
Μερεντίτης Νικόλαος
Πληροφορικός

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

Παράθεση από: nikolasmer στις 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

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

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