Παλίνδρομο ονομάζεται μια συμβολοσειρά που το ίδιο τόσο από αριστερά όσο και από δεξιά. Για παράδειγμα η συμβολοσειρά «ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ», είναι ένα παλίνδρομο.
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε Γλώσσα το οποίο αφού διαβάσει μια συμβολοσειρά θα υπολογίζει το μήκος του μικρότερου παλίνδρομου που μπορεί να κατασκευαστεί. Ως ενδεικτικό μήκος συμβολοσειράς μπορεί να ληφθεί ο αριθμός 20.
Παράδειγμα
Η συμβολοσειρά abccbbabbc δίδει το παλίνδρομο abccbbabbccba με μήκος 13. ΕΠΥ, 24ος Π.Δ.Π. (2012) Γ’ Φάση (Θέμα 2ο)
ΛΥΣΗ
ΠΡΟΓΡΑΜΜΑ ΑΣΚ10_ΠΑΡ_Β_ΠΙΝ_ΠΑΛΙΝΔΡΟΜΟ_2 ΣΤΑΘΕΡΕΣ Ν=10 ΜΕΤΑΒΛΗΤΕΣ ΧΑΡΑΚΤΗΡΕΣ: Χ[Ν], Π[20] ΑΚΕΡΑΙΕΣ: i, left, right, anadromo, mi_anadromo, pos_kentro, mikos ΛΟΓΙΚΕΣ: symetry, einai_kentro ΑΡΧΗ ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν ΔΙΑΒΑΣΕ Χ[i] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ pos_kentro <-- 0 einai_kentro <-- ΨΕΥΔΗΣ ! ο χαρακτήρας είναι κέντρο συμμετρίας i <-- (Ν MOD 2) + 1 ! ξεκινώ την αναζήτηση από τον μεσαίο χαρακτήρα ΟΣΟ i<=Ν-1 ΚΑΙ einai_kentro = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ left <-- i - 1 right <-- i + 1 symetry <-- ΑΛΗΘΗΣ ΟΣΟ left>= 1 ΚΑΙ right <= Ν και symetry = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ ΑΝ Χ[left] = Χ[right] ΤΟΤΕ left <-- left - 1 right <-- right + 1 ΑΛΛΙΩΣ symetry <-- ΨΕΥΔΗΣ ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ symetry = ΑΛΗΘΗΣ και right > Ν ΤΟΤΕ ! έχω φτάσει στο δεξί άκρο einai_kentro <-- ΑΛΗΘΗΣ pos_kentro <-- i ΤΕΛΟΣ_ΑΝ i <-- i+1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ einai_kentro = ΑΛΗΘΗΣ ΤΟΤΕ anadromo <-- Ν - pos_kentro mi_anadromo <-- (pos_kentro - 1) - anadromo mikos <-- Ν + mi_anadromo ΑΛΛΙΩΣ !Καθόλου ανάδρομο mikos <-- 2*Ν-1 ΤΕΛΟΣ_ΑΝ ΓΡΑΨΕ mikos ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
Πρόσφατα σχόλια