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

Ξεκίνησε από nikolasmer, 12 Μαρ 2013, 01:09:53 ΠΜ

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

nikolasmer

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

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

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

Επισυνάπτω έναν κώδικα για την άσκηση με πίνακα 100 χαρακτήρων.
Μερεντίτης Νικόλαος
Πληροφορικός

evry

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

Αποτελεί επίσης εξαιρετική άσκηση αν αποφασίσει κανείς να ασχοληθεί με αναδρομή. Έχει έναν αρκετά εύκολο και απλό αλγόριθμο για να σκεφτεί ο μαθητής
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

apoldem

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


Έπειτα ο προηγούμενος αλγόριθμος γράφεται πιο απλά
  ...
μεγ <- 0
  ΓΙΑ αριστ ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΙΑ δεξια ΑΠΟ Ν ΜΕΧΡΙ αριστ + 1 ΜΕ_ΒΗΜΑ -1
      μηκος <- δεξια - αριστ + 1
      ΑΝ Παλιν(Α, αριστ, δεξια) ΚΑΙ μηκος > μεγ ΤΟΤΕ
        μεγ <- μηκος
        μεγΑριστ <- αριστ
        μεγΔεξια <- δεξια
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ μεγ, μεγΑριστ, μεγΔεξια
...

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

Gnirut


apoldem

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

programmer

#5
όντως πολύ ωραία ασκηση ειχα βρει μια λυση αλλα τελικα δεν δουλευει πάντα και 8ελει καποιες μικροαλλαγές