Αποστολέας Θέμα: Το μεγαλύτερο Παλλίνδρομο  (Αναγνώστηκε 1598 φορές)

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 539
  • There can be only one...may it be AEPP.
Το μεγαλύτερο Παλλίνδρομο
« στις: 12 Μάρ 2013, 01:09:53 πμ »
Δεν ξέρω αν έχει ξανασυζητηθεί στο forum

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

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

Επισυνάπτω έναν κώδικα για την άσκηση με πίνακα 100 χαρακτήρων.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3101
  • to Iterate is human to Recurse divine
Απ: Το μεγαλύτερο Παλλίνδρομο
« Απάντηση #1 στις: 12 Μάρ 2013, 08:42:40 πμ »
Η άσκηση έχει εξαιρετικό ενδιαφέρον αν προσπαθήσει να βρει κανείς τη βέλτιστη λύση.
ή τουλάχιστον στα πλαίσια του μαθήματος να βελτιώσει λίγο την απόδοση αν αυτό είναι δυνατόν

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

apoldem

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

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

Gnirut

  • Επισκέπτης
Απ: Το μεγαλύτερο Παλλίνδρομο
« Απάντηση #3 στις: 22 Μάι 2014, 11:58:08 πμ »
algorithmsandme.blogspot.gr/2013/12/dynamic-programming-find-longest.html

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

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Το μεγαλύτερο Παλλίνδρομο
« Απάντηση #4 στις: 23 Μάι 2014, 10:47:42 πμ »
Ευχαριστούμε πολύ Gnirut. Ο ινδός που συντηρεί το blog γράφει απαίσια αγγλικά αλλά έχει μαζεμένα πολλά ωραία προβλήματα.

programmer

  • Θαμώνας
  • ***
  • Μηνύματα: 44
Απ: Το μεγαλύτερο Παλλίνδρομο
« Απάντηση #5 στις: 08 Φεβ 2015, 09:25:31 πμ »
όντως πολύ ωραία ασκηση ειχα βρει μια λυση αλλα τελικα δεν δουλευει πάντα και 8ελει καποιες μικροαλλαγές
« Τελευταία τροποποίηση: 08 Φεβ 2015, 06:57:44 μμ από programmer »