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

Динамическое программирование.Удаление строки - C++

Восстановить пароль Регистрация
 
zaptos91
0 / 0 / 0
Регистрация: 30.03.2011
Сообщений: 4
30.03.2011, 00:51     Динамическое программирование.Удаление строки #1
Дана строка S, состоящая из n маленьких латинских букв. За один ход Вам разрешается удалить один или несколько подряд идущих одинаковых символов. Необходимо удалить все символы из строки S за минимальное количество ходов.

Помогите довести до ума код,защитил алгоритм у преподавателя,а нормальная реализация не выходит.Заодно хотелось бы узнать,оптимальное ли это решение.Спасибо!
*Модераторы,если я запостил не в нужном разделе форума,перенесите мою тему пожалуйста*

Алгоритм - пусть в строке S содержится N символов. Создаём матрицу NxN,на главной диагонали расставляем единицы-кол-во удалений для подстроки длины 1,на диагонали над главной - 2,или 1 в зависимости от того,состоит ли подстрока длинны 2 из одинаковых или разных символов.
Далее, увеличивая длины подстрок, пользуемся следующими формулами:

А(i,j)-подстрока,внутри неё бегаем по К
Если S(i)!=S(k),то в матрицу =>
A(i,j)=1+A(i+1,j)

Иначе - S(i)==S(k) -в матрицу =>
A(i,j)=MIN(A(i+1,k-1)+A(k,j)

Таким образом,в правом верхнем углу матрицы будет ответ.


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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <fstream>
using namespace std;
 
int main()
{
char S[300];
 
ifstream in("input.txt");
in>>S;
in.close();
 
 
int n = strlen(S);
int **A = new int*[n];
for(int i = 0; i < n; i++)
A[i] = new int[n];
 
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
    if(i!=j)
    A[i][j]=0;
    else
    A[i][i]=1;//главная диагональ
}
for(int i=0;i<n-1;i++)//заполнение диагонали над главной
{
if(S[i]==S[i+1])
A[i][i+1]=1;
else
A[i][i+1]=2;
 
 
}
 
 
bool flag;
 
 
for(int i=2;i<n;i++){
for(int j=0;j<n-i;j++){
    flag=true;
for(int k=j+1;k<i+j;k++){
     if(S[k]==S[j]){
         if(flag)
          A[j][i+j]=A[j+1][k-1]+A[k][i+j];
          flag=false;
          if(A[j][i+j]>=(A[j+1][k-1]+A[k][i+j]))//применение алгоритма к
                                                                  //последующим подстрокам
          A[j][i+j]=A[j+1][k-1]+A[k][i+j];
       
         }
    if(S[k]!=S[j])
         A[j][i+j]=1+A[j+1][i+j];
}
}
}
 
cout<<A[0][n-1];//Ответ
 
 
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2011, 00:51     Динамическое программирование.Удаление строки
Посмотрите здесь:

C++ Динамическое программирование
C++ Динамическое программирование
C++ динамическое программирование
Динамическое программирование C++
C++ ДП Динамическое программирование
C++ Динамическое программирование!
C++ Динамическое программирование. Разбиение абзаца на строки

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zaptos91
0 / 0 / 0
Регистрация: 30.03.2011
Сообщений: 4
01.04.2011, 03:51  [ТС]     Динамическое программирование.Удаление строки #2
Ау,люди! Ну подскажите хоть что-нибудь,третий день код переписываю!
Yandex
Объявления
01.04.2011, 03:51     Динамическое программирование.Удаление строки
Ответ Создать тему
Опции темы

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