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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ процедура RectPS (перевести с паскаля) http://www.cyberforum.ru/cpp-beginners/thread1034279.html
Привет всем!!!Помогите перевести с паскаля на С++ rectPS(x1, y1, x2, y2, P, S), вычисляющую периметр P и площадь S прямоугольника со сторонами, параллельными осям координат, по координатам (x1, y1), (x2, y2) его противоположных вершин (x1, y1, x2, y2 — входные, P и S — выходные параметры). В качестве результирующего значения функция должна возвращать истину, если прямоугольник не является...
C++ После ввода с клавиатуры произвольного строки выдать на экран протокол о количестве вхождений каждого символа. В протоколе символы расположить по алфа После ввода с клавиатуры произвольного строки выдать на экран протокол о количестве вхождений каждого символа. В протоколе символы расположить по алфавиту, отдельными группами для различных алфавитов, другие символы расположить последними; символы не повторять. На С++. Помогите пожалуйста сделать. Вообще не могу понять как ее делать. Заранее спасибо. http://www.cyberforum.ru/cpp-beginners/thread1034250.html
C++ Классы, наследование
Доброго времени суток! Объясните пожалуйста, как работает операция "::" на примере этой программы. И работу конструкции Time::Time() : TimeBase() main.cpp #include <stdio.h> #include <stdlib.h> #include <locale.h> #include <iostream>
Определить пересекается ли парабола и прямая C++
Определите, пересекается ли парабола y=cx^2+dx+f и прямая y=ax+b . При положительном ответе найти точки пересечения. Заранее благодарен.
C++ И что делать дальше?Поделитесь опытом http://www.cyberforum.ru/cpp-beginners/thread1034234.html
Итак вопрос немного необычного характера. Дела обстоят так: 1) В университете нам вообще не преподают нормально програмирование 2)Я уже выучила хорошо синтаксис С++ 3)Но синтаксис этот не применение. Из этого вытекает вопрос...как развивать свои умения програмировать на этом языке? Задания вроде "создайте иерархию классов линия - прямоугольник- куб" и " напишите программу которая добавляет...
C++ Вычислить сумму положительных чисел, кратных 3 и не кратных 5 Не могу сделать прогу на c++,можете,пожалуйста,сделать ее для меня? Вводится последовательность чисел признак окончания 0,вычеслить сумму полож. чисел кратных 3 и не кратных 5. подробнее

Показать сообщение отдельно
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
09.12.2013, 13:26     Задача о НОП (динамическое программирование)
Здравствуйте!!! Мне нужно решить задачу о нахождении наибольшей общей подстроки. Поискал в интернете, нашёл такой код на 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);
Но этот код не работает и я не знаю, то ли я неправильно перевёл, то ли этот код вообще не рабочий. Подскажите, что здесь не так. Заранее спасибо!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 00:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru