Developing.ru

Извиняюсь за такую наглость!!! Но вообще не знаю, что делать! Уже руки опустились! помогите пожалуйста в создании алгоритма для следующей задачи! Заранее благодарен!
Условие



На вход подаются две символьные последовательности A и B, каждая последовательность состоит из маленьких латинских букв и длинной не более 1000 символов. Необходимо преобразовать последовательность A в последовательность B с минимальным суммарным штрафом, который определяется следующим образом:

1) удаление символа из строки A равно x баллов;

2) вставка символа в строку A равна y баллов;

3) замена символа в строке A на любой другой равна z баллов.



Входные данные



Входные данные находятся в файле in.txt.

· В первой строке находится число x.

· Во второй строке – число y.

· В третьей строке - число z.

· В следующих двух строках файла находятся символьные последовательности A и B (тип элементов последовательности string).



Выходные данные



Выходные данные находятся в файле out.txt, который содержит минимальный суммарный штраф.



Пример входных данных



2

3

1

abcd

bce



Пример выходных данных



3



Очень нуждаюсь в вашей помощи!!! Спасите!

Почитайте про "Расстояние Левенштейна". Данный алгоритм позволяет вычислить места различия строк и определиться с тем, что предпринять в этих местах: вставку, удаление или замену символов. По-моему это то, что вам нужно.

Спасибо за ответ! Вы понимаете я это тоже заметил и реализован! но оно проходит только 8 тестов из 12 на сайте, на который мне надо посылать задачу!!! Взяв один из тестов (642
735
963
weyufweuvhjbvjhvdsjfhvsjck
sdjahfvdhjkgfweyiufhoyebfoyubfoywebyfuowbfweybfwiefbewfbwiebfiiwebfjapaj
ответ 48255)
то я увидел, что мой алгоритм работает не верно!!! и я не знаю, что сделано не верно! может вы увидите!

#include <fstream.h>
#include <string.h>
#include <iostream.h>

//using namespace std;

const int N = 10000;

long min(long,long);

int main ()
{
ifstream in ("in.txt");
ofstream out ("out.txt");
long x,y,z;
int i,j;
in >> x >> y >> z;
char* str1 = new char [N];
char* str2 = new char [N];
in.getline(str1, N);
in.getline(str1, N);
in.getline(str2, N);
in.close();
/* char* temp = "weyufweuvhjbvjhvdsjfhvsjck";

if(!strncmp(str1,temp,strlen(temp)-1)) //
{
out<<"48255";
return 0;
} */

int dlinstr1 = strlen (str1);
int dlinstr2 = strlen (str2);
int **shtraf = new int* [dlinstr1+1];
for (i=0; i<=dlinstr1; ++i)
shtraf = new int[dlinstr2+1];
for (i=0; i<=dlinstr1; ++i)
shtraf [0]=i*x;
for (j=0; j<=dlinstr2;++j)
shtraf [0][j]=j*y;
for (i=1; i<=dlinstr1; ++i)
for (j=1; j<=dlinstr2;++j)
{
a = shtraf[i-1][j-1]+((str1[i-1]==str2[j-1])?0:z);
b = min (x+shtraf[i-1][j], y+shtraf[j-1]);
shtraf[j]=min(a,b);
//shtraf[j]=min (shtraf[i-1][j-1]+z,x+shtraf[i-1][j],shtraf[j-1]+y);
}
out<<shtraf[dlinstr1][dlinstr2];
delete str1;
delete str2;
out.close();
return 0;
}

long min(long a,long b)
{
if( a < b)
return a;
else
return b;
}

Я не вникал в приведенный код, но что-то слишком мало кода для реализации алгоритма Левенштейна. В этом алгоритме должна строиться и заполняться особым образом таблица. По результатам заполнения вычисляется необходимое действие. В основном, в описаниях данного алгоритма, указывается на использование его в алгоритмах поиска, когда просто вычисляется расстояние Левенштейна (реализация есть в википедии) и делается вывод о схожести слов, но можно реализовать его и под Вашу задачу, нужно только немного подумать.

решил задачку!!! Мот кому понадобится!!!

#include <iostream>
#include <string>
#define infinity 1234567890;
using namespace std;
int x,y,z;
string str1,str2;
int a[1001][1001];
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
cin>>x>>y>>z;
cin>>str1;
cin>>str2;
int n=str1.size();
int m=str2.size();
for (int j=0; j<=m;j++)
a[0][j]=j*y;
for(int i=0;i<=n;i++)
a[0]=i*x;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
a[j]=infinity;
if (str1[i-1]==str2[j-1])
{
a[j]=a[i-1][j-1];
}
if (a[j]>a[i-1][j-1])a[j]=a[i-1][j-1]+z;
if (a[j]>a[i-1][j]+x) a[j]=a[i-1][j]+x;
if (a[j]>a[j-1]+y) a[j]=a[i][j-1]+y;
}
cout<<a[n][m];
return 0;
}