Форум программистов, компьютерный форум CyberForum.ru

Задача о НОП (динамическое программирование) - C++

Восстановить пароль Регистрация
 
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
09.12.2013, 13:26     Задача о НОП (динамическое программирование) #1
Здравствуйте!!! Мне нужно решить задачу о нахождении наибольшей общей подстроки. Поискал в интернете, нашёл такой код на Pascal:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var x,y,z:string;
 
a:array[0..250,0..250] of byte;
 
i,j:byte;
 
begin
 
readln(x);
 
readln(y);
 
fillchar(a,sizeof(a),0);
 
for i:=1 to length(x) do
 
for j:=1 to length(y) do
 
if x[i]=y[j] then a[i,j]:=a[i-1,j-1]+1
 
else if a[i-1,j]>=a[i,j-1] then a[i,j]:=a[i-1,j]
 
else a[i,j]:=a[i,j-1];{длина НОП найдена в a[length(x),length(y)]}
 
z:='';{строим саму НОП}
 
i:=length(x);
 
j:=length(y);
 
while (i>0) and (j>0) do
 
if x[i]=y[j] then begin z:=x[i]+z; i:=i-1; j:=j-1 end
 
else if a[i-1,j]>=a[i,j-1] then i:=i-1 else j:=j-1;
 
writeln(z)
 
end.
Попробовал перевести его на C++, вот, что получилось:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int len[200][200];
char str1[N],str2[N],nop[N];
//ввод строк
for(int i=0;i<strlen(str1);i++)
        for(int j=0;j<strlen(str2);j++)
        {
            if(strcmp(str1,str2)==0)
                len[i][j]=len[i-1][j-1]+1;
            else 
                if(len[i-1][j]>=len[i][j-1])
                    len[i][j]=len[i-1][j];
                else
                    len[i][j]=len[i][j-1];
        }
    int i=strlen(str1),j=strlen(str2);
    while((i>0) && (j>0))
    {
        if(strcmp(str1,str2)==0)
        {
            nop=str1[i]+nop;
            i--;
            j--;
        }
        else 
            if(len[i-1][j]>=len[i][j-1])
                i--;
            else 
                j--;
    }
    puts(nop);
Но этот код не работает и я не знаю, то ли я неправильно перевёл, то ли этот код вообще не рабочий. Подскажите, что здесь не так. Заранее спасибо!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2013, 13:26     Задача о НОП (динамическое программирование)
Посмотрите здесь:

C++ Динамическое программирование
C++ динамическое программирование
Задача на динамическое программирование. C++
C++ Динамическое программирование, задача "Уменьшение числа"
C++ Задача на динамическое программирование(скорее всего) (сколькими способами в сумме получить N, без подряд идущих одинаковых чисел)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
09.12.2013, 13:50     Задача о НОП (динамическое программирование) #2
попробуйте так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int len[256][256];
char str1[N],str2[N],nop[N];
//ввод строк
for(int i=0;i<strlen(str1);i++)
    for(int j=0;j<strlen(str2);j++)
    {
    if(str1[i]==str[j])
        len[i+1][j+1]=len[i][j+1]+1;
    else 
        if(len[i][j+1]>=len[i+1][j])
            len[i+1][j+1]=len[i][j+1];
        else
            len[i][j]=len[i][j-1];
    }
int i=strlen(str1),j=strlen(str2);
int z=N;
nop[z] = 0;
while((i>0) && (j>0))
{
    if(str1[i]==str[j])
    {
        --z;
        nop[z]=str1[i];
        i--;
        j--;
    }
    else 
        if(len[i][j+1]>=len[i+1][j])
            i--;
        else 
            j--;
}
puts(nop+z);
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
09.12.2013, 14:17  [ТС]     Задача о НОП (динамическое программирование) #3
Да, теперь вроде всё работает, но только, если подстрока начинается с начала исходной строки, то не выводится первый символ

Добавлено через 14 минут
И ещё, если есть две подстроки одинаковой длины, то ни одна из них не выводится. Как это исправить, не подскажете?
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
09.12.2013, 15:40     Задача о НОП (динамическое программирование) #4
попробуйте заменить строку 18 на
C++
1
while((i>=0) && (j>=0))
Добавлено через 3 минуты
и строку 15 на
C++
1
int i=strlen(str1)-1,j=strlen(str2)-1;
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
09.12.2013, 15:44  [ТС]     Задача о НОП (динамическое программирование) #5
Да, первая проблема ушла, а вот вторая, к сожалению, осталась
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
09.12.2013, 16:13     Задача о НОП (динамическое программирование) #6
Вот, вроде норм работает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
 
int main() {
    const int N1 = 20;
    const int N2 = 25;
    const int NN = (N1+N2)/2;
 
    int  len[N1+1][N2+1]={{0}};
 
    char str1[N1]="abcdabcd";
    char str2[N2]="abcdaef";
    char nop [NN]="";
 
    for(int i=0;i<strlen(str1);i++)
        for(int j=0;j<strlen(str2);j++) {
            if(str1[i]==str2[j])
                len[i+1][j+1]=len[i][j]+1;
            else 
                if(len[i][j+1]>=len[i+1][j])
                    len[i+1][j+1]=len[i][j+1];
                else
                    len[i+1][j+1]=len[i+1][j];
        }
    int i=strlen(str1)-1,j=strlen(str2)-1;
    int z=NN;
    nop[z] = 0;
    while((i>=0) && (j>=0)) {
        if(str1[i]==str2[j]) {
            --z;
            nop[z]=str1[i];
            i--;
            j--;
        }
        else 
            if(len[i][j+1]>=len[i+1][j])
                i--;
            else 
                j--;
    }
    puts(nop+z);
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2013, 16:21     Задача о НОП (динамическое программирование)
Еще ссылки по теме:

C++ Динамическое программирование!
C++ Задача на динамическое программирование
Задача "Движение по клеткам таблицы" (Динамическое программирование) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
09.12.2013, 16:21  [ТС]     Задача о НОП (динамическое программирование) #7
Спасибо большое!!!
Yandex
Объявления
09.12.2013, 16:21     Задача о НОП (динамическое программирование)
Ответ Создать тему
Опции темы

Текущее время: 09:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru