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