Γενικό Λύκειο > Μονοδιάστατοι πίνακες

Το μεγαλύτερο Παλλίνδρομο

(1/2) > >>

nikolasmer:
Δεν ξέρω αν έχει ξανασυζητηθεί στο forum

Παλλίνδρομο είναι μια λέξη και γενικότερα ακολουθίες χαρακτήρων οι οποίες μπορούν να γραφτούν και ανάποδα πχ sabbas .
Να γίνει αλγόριθμος ο οποίος να διαβάζει μια ακολουθία χαρακτήρων και να την αποθηκεύει σε πίνακα. Κάθε θέση του πίνακα και εναν χαρακτήρα. Ο αλγόριθμος να υπολογίζει και να εμφανίζει το μεγαλύτερο παλίνδρομο και από πόσους χαρακτήρες αυτό αποτελείται.

Θα ήθελα την άποψή σας πάνω σε αυτό. Με ενδιαφέρει κάποια άλλη προσέγγιση από αυτή που είχα στο μυαλό μου, ιδίως αν είναι πιο εύκολη.

Επισυνάπτω έναν κώδικα για την άσκηση με πίνακα 100 χαρακτήρων.

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

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

apoldem:
Πολύ ωραία άσκηση που δεν την είχα προσέξει πριν (μόνο για παρουσίαση της λύσης, είναι πολύ δύσκολη για μαθητή). Το κατάλληλο όνομα νομίζω είναι "μέγιστος παλίνδρομος υποπίνακας". Είναι ένα θαυμάσιο παράδειγμα επίδειξης της φιλοσοφίας του τμηματικού προγραμματισμού και πως αλλάζει δραστικά τον κώδικα που γράφουμε. Αρχικά χρειαζόμαστε μια συνάρτηση που να ελέγχει αν ένας υποπίνακας του αρχικού είναι παλίνδρομος ή όχι.

--- Κώδικας: ---ΣΥΝΑΡΤΗΣΗ Παλιν(Χ, αριστ, δεξια): ΛΟΓΙΚΗ
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: Χ[10]
  ΑΚΕΡΑΙΕΣ: αριστ, δεξια
ΑΡΧΗ
  ΟΣΟ αριστ < δεξια ΚΑΙ Χ[αριστ] = Χ[δεξια] ΕΠΑΝΑΛΑΒΕ
    αριστ <- αριστ + 1
    δεξια <- δεξια - 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ! Αν πάνε όλα καλά τότε οι δείκτες ή θα δείχνουν το ίδιο μεσαίο στοιχείο
  ! ή θα έχουν ξεπεράσει ο ένας τον άλλον (περίπτωση άρτιου μήκους Χ)
  Παλιν <- αριστ >= δεξια
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
--- Τέλος κώδικα ---

Έπειτα ο προηγούμενος αλγόριθμος γράφεται πιο απλά

--- Κώδικας: ---  ...
μεγ <- 0
  ΓΙΑ αριστ ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΙΑ δεξια ΑΠΟ Ν ΜΕΧΡΙ αριστ + 1 ΜΕ_ΒΗΜΑ -1
      μηκος <- δεξια - αριστ + 1
      ΑΝ Παλιν(Α, αριστ, δεξια) ΚΑΙ μηκος > μεγ ΤΟΤΕ
        μεγ <- μηκος
        μεγΑριστ <- αριστ
        μεγΔεξια <- δεξια
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ μεγ, μεγΑριστ, μεγΔεξια
...
--- Τέλος κώδικα ---
Το ωραίο με τον τμηματικό προγραμματισμό είναι ότι όχι μόνο κάνει τον κώδικα κατανοητό αλλά μας οδηγεί και σε αποδοτικότερες λύσεις. Στην περίπτωσή μας, αφού ψάχνουμε τον μεγαλύτερο παλίνδρομο, δεν χρειάζεται να ψάξουμε όλους τους δυνατούς υποπίνακες. Αν ξεκινήσουμε από τα μεγαλύτερα μήκη υποπινάκων προς τα μικρότερα, τότε ο πρώτος παλίνδρομος που θα βρούμε θα είναι και ο μεγαλύτερος.
Η παρακάτω υλοποίηση δείχνει πόσο κοντόφθαλμη ήταν η τακτική του βιβλίου να πετσοκόψει τις εντολές της PASCAL και επίσης πόσο λάθος έχουν όσοι προτείνουν να μην χρησιμοποιούνται ποτέ οι εντολές break και continue. Ο παρακάτω κώδικας γραμμένος με ΟΣΟ γίνεται απαίσιος

--- Κώδικας: ---...
  βρεθηκε <- ΨΕΥΔΗΣ
  ΓΙΑ μηκος ΑΠΟ Ν ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
    ΓΙΑ αριστ ΑΠΟ 1 ΜΕΧΡΙ Ν - μηκος + 1
      δεξια <- αριστ + μηκος - 1
      ΑΝ Παλιν(Α, αριστ, δεξια) ΤΟΤΕ
        βρεθηκε <- ΑΛΗΘΗΣ
        *ΣΠΑΣΕ*
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΑΝ βρεθηκε ΤΟΤΕ *ΣΠΑΣΕ*
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ μηκος
--- Τέλος κώδικα ---

Gnirut:
algorithmsandme.blogspot.gr/2013/12/dynamic-programming-find-longest.html

έχει και άλλα ωραία σε αυτό το blog.

apoldem:
Ευχαριστούμε πολύ Gnirut. Ο ινδός που συντηρεί το blog γράφει απαίσια αγγλικά αλλά έχει μαζεμένα πολλά ωραία προβλήματα.

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση