Αποστολέας Θέμα: ΑΛΓΟΡΙΘΜΟΣ ΛΑΒΥΡΙΝΘΟΣ  (Αναγνώστηκε 1891 φορές)

akhs7

  • Νέος
  • *
  • Μηνύματα: 3
ΑΛΓΟΡΙΘΜΟΣ ΛΑΒΥΡΙΝΘΟΣ
« στις: 20 Ιαν 2013, 11:49:59 μμ »
Χρειάζομαι βοήθεια για να λύσω μια άσκηση η οπία θέλει να αναπτύξουμε αλγόριθμο που να δημιουργεί "λαβύρινθους" ως εξής:

Θα τοποθετεί σε έναν πίνακα ΝxN με τυχαίο τρόπο Κ "τοίχους" (όπου Κ<2Ν) όπου ο "τοίχος" μπορεί να παρασταθεί όπως και στο παιχνίδι του Ναρκαλιευτή με την τιμή "-1".

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

Πιο συγκεκριμένα, θα εξετάζει αν πχ ένα robot μπαίνοντας στο λαβύρινθο από τη θέση του πίνακα (0,0) θα μπορούσε να φτάσει χωρίς να πέσει επάνω σε τοίχο στη θέση έξοδο (Ν,Ν).

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2370
Απ: ΑΛΓΟΡΙΘΜΟΣ ΛΑΒΥΡΙΝΘΟΣ
« Απάντηση #1 στις: 21 Ιαν 2013, 01:08:31 πμ »
Αυτή την άσκηση την έχεις στα πλαίσια του μαθήματος "Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον";;;;;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 571
  • There can be only one...may it be AEPP.
Απ: ΑΛΓΟΡΙΘΜΟΣ ΛΑΒΥΡΙΝΘΟΣ
« Απάντηση #2 στις: 21 Ιαν 2013, 01:14:29 πμ »
Πίνακα με αρχική θέση (0,0) δεν νομίζω να συναντάς στην ΑΕΠΠ.
Επίσης μήπως θα ήθελες να πείς κ <Ν^2-Ν ο περιορισμός για τους "τοίχους";
Μερεντίτης Νικόλαος
Πληροφορικός

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 571
  • There can be only one...may it be AEPP.
Απ: ΑΛΓΟΡΙΘΜΟΣ ΛΑΒΥΡΙΝΘΟΣ
« Απάντηση #3 στις: 21 Ιαν 2013, 03:11:48 πμ »
Νομίζω πως κάτι τέτοιο είχες στο μυαλό σου.

Αλγόριθμος Λαβύρινθος
Για i από 1 μέχρι 3
  Για j από 1 μέχρι 3
    Αν i = 1 και j = 1 τότε
      Αρχή_επανάληψης
        Εμφάνισε "Δώσε το (", i, ",", j, ") στοιχείο"
        Διάβασε Π[i, j]
        Αν Π[1, 1] ≠ 0 τότε
          Εμφάνισε "Εδωσες λανθασμένο στοιχείο"
        Τέλος_αν
      Μέχρις_ότου Π[1, 1] = 0
    αλλιώς
      Αρχή_επανάληψης
        Εμφάνισε "Δώσε το (", i, ",", j, ") στοιχείο"
        Διάβασε Π[i, j]
        Αν Π[i, j] ≠ 0 και Π[i, j] ≠ -1 τότε
          Εμφάνισε "Εδωσες λανθασμένο στοιχείο"
        Τέλος_αν
      Μέχρις_ότου Π[i, j] = 0 ή Π[i, j] = -1
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
ρομπότ_i ← 1
ρομπότ_j ← 1
i ← 1
j ← 1
flag ← Ψευδής
Όσο ρομπότ_i ≠ 3 και ρομπότ_j ≠ 3 και flag = Ψευδής επανάλαβε
  flag2 ← Ψευδής
  Όσο i < 3 και flag2 = Ψευδής επανάλαβε
    Αν Π[i + 1, j] ≠ -1 τότε
      i ← i + 1
      Εμφάνισε "(", i, ",", j, ")"
    αλλιώς
      flag2 ← Αληθής
    Τέλος_αν
  Τέλος_επανάληψης
  ρομπότ_i ← i
  flag3 ← Ψευδής
  Όσο j < 3 και flag3 = Ψευδής επανάλαβε
    Αν Π[i, j + 1] ≠ -1 τότε
      j ← j + 1
      Εμφάνισε "(", i, ",", j, ")"
    αλλιώς
      flag3 ← Αληθής
    Τέλος_αν
  Τέλος_επανάληψης
  ρομπότ_j ← j
  Αν ρομπότ_i < 3 και ρομπότ_j < 3 τότε
    Αν Π[ρομπότ_i + 1, ρομπότ_j] = -1 και Π[ρομπότ_i, ρομπότ_j + 1] = -1 τότε
      flag ← Αληθής
    Τέλος_αν
  αλλιώς_αν ρομπότ_i = 3 και ρομπότ_i ≠ ρομπότ_j τότε
    Αν Π[ρομπότ_i, ρομπότ_j + 1] = -1 τότε
      flag ← Αληθής
    Τέλος_αν
  αλλιώς_αν ρομπότ_j = 3 και ρομπότ_i ≠ ρομπότ_j τότε
    Αν Π[ρομπότ_i + 1, ρομπότ_j] = -1 τότε
      flag ← Αληθής
    Τέλος_αν
  Τέλος_αν
Τέλος_επανάληψης
Αν flag = Αληθής τότε
  Εμφάνισε "Κόλησες"
Τέλος_αν
Τέλος Λαβύρινθος

Οι τοίχοι είναι -1 και η δίοδος 0. Τα δεδομένα τα εισάγεις από το πληκτρολόγιο.
Κινείσαι πρώτα γραμμή και έπειτα στήλη.
Όχι διαγώνια και όχι προς τα πίσω.
Αν και πιστέυω πως η άσκηση είναι έξω από τα πλαίσια του μαθήματος της ΑΕΠΠ.
Μερεντίτης Νικόλαος
Πληροφορικός

akhs7

  • Νέος
  • *
  • Μηνύματα: 3
Απ: ΑΛΓΟΡΙΘΜΟΣ ΛΑΒΥΡΙΝΘΟΣ
« Απάντηση #4 στις: 22 Ιαν 2013, 05:53:18 μμ »
οκ ευχαριστω πολυ !! ο καθηγητης του σχολειου μας την εβαλε :/