Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον => Μονοδιάστατοι πίνακες => Μήνυμα ξεκίνησε από: nikolasmer στις 12 Μάρ 2013, 01:09:53 πμ

Τίτλος: Το μεγαλύτερο Παλλίνδρομο
Αποστολή από: nikolasmer στις 12 Μάρ 2013, 01:09:53 πμ
Δεν ξέρω αν έχει ξανασυζητηθεί στο forum

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

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

Επισυνάπτω έναν κώδικα για την άσκηση με πίνακα 100 χαρακτήρων.
Τίτλος: Απ: Το μεγαλύτερο Παλλίνδρομο
Αποστολή από: evry στις 12 Μάρ 2013, 08:42:40 πμ
Η άσκηση έχει εξαιρετικό ενδιαφέρον αν προσπαθήσει να βρει κανείς τη βέλτιστη λύση.
ή τουλάχιστον στα πλαίσια του μαθήματος να βελτιώσει λίγο την απόδοση αν αυτό είναι δυνατόν

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

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

έχει και άλλα ωραία σε αυτό το blog.
Τίτλος: Απ: Το μεγαλύτερο Παλλίνδρομο
Αποστολή από: apoldem στις 23 Μάι 2014, 10:47:42 πμ
Ευχαριστούμε πολύ Gnirut. Ο ινδός που συντηρεί το blog γράφει απαίσια αγγλικά αλλά έχει μαζεμένα πολλά ωραία προβλήματα.
Τίτλος: Απ: Το μεγαλύτερο Παλλίνδρομο
Αποστολή από: programmer στις 08 Φεβ 2015, 09:25:31 πμ
όντως πολύ ωραία ασκηση ειχα βρει μια λυση αλλα τελικα δεν δουλευει πάντα και 8ελει καποιες μικροαλλαγές