Субота
22.09.2018
18:29


ФОРМА ВХОДУ

Вітаю Вас Гість | RSS
Солонянська шкільна лабораторія
нових інформаційних технологій

Відділ освіти Солонянської РДА
Головна Задача14 Реєстрація Вхід


Україна - єдина країна

Меню


Информатика и ИКТ в современной школе

Как создать свой сайт

Всё для создания сайта на ucoz


Паліндром.
Паліндром - слово, яке читається з обох сторін однаково. Скласти програму, яка перетворює у паліндром довільне слово, викреслюючи з нього мінімальну кількість букв. Словом будемо вважати послідовність маленьких літер алфавіту.
Це - класична задача динамічного програмування.
Нехай задано послідовність символів:
X=(q,w,e,r,t).
Утворимо нову послідовність:
Y=(t,r,e,w,q),
записавши символи заданої послідовності ззаду наперед. Знайдемо довжину найбільшої спільної послідовності.
Якщо розв'язувати задачу "в лоб", перебираючи всі можливі підпослідовності послідовності Х та перевіряючи для кожної з них, чи не буде вона підпослідовністю послідовності Y, то алгоритм буде правильним, але неефективним.
Візьмемо матрицю A[0..Length(X), 0..Length(Y)], у якій будемо зберігати довжину спільної послідовності. Будемо порівнювати і-й елемент послідовності Х з кожним елементом послідовності Y і заповнюватимемо матрицю А за таким правилом:

Покажемо заповнення матриці на прикладі тесту з умови задачі:

Таким чином, у клітинці А[m,m] записано загальну довжину найбільшої спільної послідовності. Для знаходження мінімальної кількості символів, яку потрібно вилучити, достатньо від загальної кількості символів відняти довжину найбільшої спільної послідовності.


Місцевий час



Корисні посилання
Солонянська СЗШ №1
Солонянський РНМК
відділ освіти
**********
Освітній портал
ДОІППО
Єдиний освітній центр



Copyright MyCorp © 2018Безкоштовний хостинг uCoz