Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Рекурсия >> Номер 17

[Назад]    [Содержание ]    [Вперед]

  


Номер 17


  Условие: Номер 17


Задача 16. Пусть x=(a1,a2,...,am) и y=(b1,b2,...,bn) - две заданных строки символов. Определим d(x,y) как минимальное число вставок, удалений и замен символа, которое необходимо для преобразования x в y. Например: d(ptslddf,tsgldds)=3 Для заданных x и y найти d(x,y).

  Решение задачи: Номер 17


Решение задачи 16. Для x=a(1)...a(m) и y=b(1)...b(n), a(i) и b(i) символы, 1<=i<=m, 1<=j<=n, d(x,y) можно вычислить, применяя метод динамического программирования. Определим массив d[0..m,0..n], элементы которого d[i,j] = d(a(1)...a(i), b(1)...b(j)), 0<=i<=m,0<=j<=n, так что d[0,j]=j; d[i,0]=i; очевидным образом получаем d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij} где Pij=1 если a(i)<>b(i) и Pij=0 иначе (в правой части приведенного выше выражения первому элементу в min соответствует операция удаления из строки a(1)...a(i-1)a(i) последнего элемента a(i), после чего за d[i-1,j] операцию строка a(1)...a(i-1) преобразуется в строку b(1)...b(j), второму элементу - операция вставки символа b(j) в конец строки b(1)...b(j-1), полученной за d[i,j-1] операцию из строки a(1)...a(i), а третьему - контекстная замена ai на bj, замена осуществляется в случае ai<>bj (тогда Pij=1) и не происходит при совпадении ai и bj). Получаем необходимое d(x,y)=d[m,n]. Алгоритм может быть записан так: for i:=1 to m do d[i,0]:=i; for j:=1 to n do d[0,j]:=j; for i:=1 to m do for j:=1 to n do d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij};

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017