Επιλογή Σελίδας

Παλίνδρομο ονομάζεται μια συμβολοσειρά που το ίδιο τόσο από αριστερά όσο και από δεξιά. Για παράδειγμα η συμβολοσειρά «ΝΙΨΟΝΑΝΟΜΗΜΑΤΑΜΗΜΟΝΑΝΟΨΙΝ», είναι ένα παλίνδρομο.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε Γλώσσα το οποίο αφού διαβάσει μια συμβολοσειρά θα υπολογίζει το μήκος του μικρότερου παλίνδρομου που μπορεί να κατασκευαστεί. Ως ενδεικτικό μήκος συμβολοσειράς μπορεί να ληφθεί ο αριθμός 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

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ


					
Share This