Рекурсия
17.06.2018, 16:23. Показов 424. Ответов 0
Суть задания тут: Динамическое программирование. Требуется идея для решения. Общая подпоследовательность
КОД (методом ДП)
Матрицу пропускайте. Переходите сразу к ф-и LCS. 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
| #include <iostream>
#include <stdexcept> // std::out_of_range
#include <algorithm> // std::max
#include <iomanip> // std::setw
#include <cstring> // std::strlen
template<typename _Ty>
class Matrix
{
private:
_Ty *mData;
unsigned mRows;
unsigned mCols;
public:
Matrix(unsigned rows, unsigned cols)
{
mRows = rows;
mCols = cols;
mData = new _Ty[rows * cols]{};
}
Matrix(const Matrix &other)
: mData{ new _Ty[other.mRows * other.mCols] },
mRows{ other.mRows }, mCols{other.mCols}
{
for (unsigned i{}; i < (other.mRows * other.mCols); ++i)
{
mData[i] = other.mData[i];
}
}
template<typename _Ty2>
Matrix(const Matrix<_Ty2> &other)
: mData{ new _Ty[other.sizeRows() * other.sizeCols()] },
mRows{ other.sizeRows() }, mCols{ other.sizeCols() }
{
for (unsigned i{}; i < other.sizeRows(); ++i)
{
for (unsigned j{}; j < other.sizeCols(); ++j)
{
this->get(i, j) = other.get(i, j);
}
}
}
Matrix& operator=(const Matrix &rhs)
{
if (this != &rhs)
{
delete[] mData;
mData = new _Ty[rhs.mRows * rhs.mCols];
mRows = rhs.mRows;
mCols = rhs.mCols;
for (unsigned i{}; i < (rhs.mRows * rhs.mCols); ++i)
{
mData[i] = rhs.mData[i];
}
}
return *this;
}
template<typename _Ty2>
Matrix& operator=(const Matrix<_Ty2> &rhs)
{
if (this != &rhs)
{
delete[] mData;
mData = new _Ty[rhs.sizeRows() * rhs.sizeCols()];
mRows = rhs.sizeRows();
mCols = rhs.sizeCols();
for (unsigned i{}; i < rhs.sizeRows(); ++i)
{
for (unsigned j{}; j < rhs.sizeCols(); ++j)
{
this->get(i, j) = rhs.get(i, j);
}
}
}
return *this;
}
unsigned sizeRows(void) const
{
return mRows;
}
unsigned sizeCols(void) const
{
return mCols;
}
_Ty& get(const unsigned &i, const unsigned &j)
{
if ((i > (mRows - 1)) || (j > (mCols - 1)))
{
throw std::out_of_range("index of matrix out of range");
}
return mData[(i * mRows) + j];
}
const _Ty& get(const unsigned &i, const unsigned &j) const
{
if ((i > (mRows - 1)) || (j > (mCols - 1)))
{
throw std::out_of_range("index of matrix out of range");
}
return mData[(i * mRows) + j];
}
~Matrix(void)
{
delete[] mData;
}
};
int LCS(const char *_firstStr, const char *_secondStr,
const unsigned &_firstLength, const unsigned &_secondLength, const int &w)
{
Matrix<int> L{ _firstLength + 1, _secondLength + 1 }; // Scores
Matrix<unsigned> kx{ _firstLength + 1, _secondLength + 1 }; // индексы для первой строки
Matrix<unsigned> ky{ _firstLength + 1, _secondLength + 1 }; // индексы для второй строки
for (unsigned i{}; i < (_firstLength + 1); i++)
{
for (unsigned j{}; j < (_secondLength + 1); j++)
{
if (!i || !j) // Если один из индексов равен нулю...
{
L.get(i, j) = 0;
kx.get(i, j) = 0;
ky.get(i, j) = 0;
}
else if (_firstStr[i - 1] == _secondStr[j - 1]) // Если буквы совпали...
{
const int Score = L.get(i - 1, j - 1) + 1 + w
* (((kx.get(i - 1, j - 1) == (i - 1)) ? 0 : 1)
- ((ky.get(i - 1, j - 1) == (j - 1)) ? 0 : 1));
// 0 - слова не дробятся 1 - слова дробятся
// Т.к. нужно максмизировать Score, находим наилучший Score между текущей и 2-я предыдущими подзадачами
const int max = std::max({ Score, L.get(i - 1, j), L.get(i, j - 1) });
if (max == Score)
{
kx.get(i, j) = i;
ky.get(i, j) = j;
L.get(i, j) = Score;
}
else if (max == L.get(i - 1, j))
{
kx.get(i, j) = kx.get(i - 1, j);
ky.get(i, j) = ky.get(i - 1, j);
L.get(i, j) = L.get(i - 1, j);
}
else
{
kx.get(i, j) = kx.get(i, j - 1);
ky.get(i, j) = ky.get(i, j - 1);
L.get(i, j) = L.get(i, j - 1);
}
}
else // Если буквы не совпали...
{
if (L.get(i - 1, j) > L.get(i, j -1))
{
kx.get(i, j) = kx.get(i - 1, j);
ky.get(i, j) = ky.get(i - 1, j);
L.get(i, j) = L.get(i - 1, j);
}
else
{
kx.get(i, j) = kx.get(i, j - 1);
ky.get(i, j) = ky.get(i, j - 1);
L.get(i, j) = L.get(i, j - 1);
}
}
}
}
/*
///================================== Вывод матриц =======================================
auto print = [=](const Matrix<int> &_matrix, const unsigned &_spaceNum)
{
for (unsigned i{}; i < _matrix.sizeRows(); ++i)
{
for (unsigned j{}; j < _matrix.sizeCols(); ++j)
{
std::cout << std::setw(_spaceNum) << _matrix.get(i, j) << std::setw(0) << ' ';
}
std::cout << std::endl;
}
};
std::cout << "------------------[ L ]--------------------" << std::endl;
print(L, 4);
std::cout << "------------------[ kx ]-------------------" << std::endl;
print(kx, 4);
std::cout << "------------------[ ky ]-------------------" << std::endl;
print(ky, 4);
std::cout << "-------------------------------------------" << std::endl;
=======================================================================================
//*/
return L.get( _firstLength, _secondLength); // возвращаем наибольший Score
}
int main()
{
char firstStr[]{ "FABABCCCC" };
char secondStr[]{ "FCBCBCACA" };
const int w = 100;
const unsigned fLen = std::strlen(firstStr);
const unsigned sLen = std::strlen(secondStr);
std::cout << "Result: " << LCS(firstStr, secondStr, fLen, sLen, w) << std::endl;
} |
|
Можно заметить что код для решения задачи схож чем-то с обычной LCS задачей (или задачей с геномом).
При переписывании данного кода ДП в рекурсию столкнулся с зацикливанием
Собственно вот код.
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| template<typename _Ty, typename _Ty2, typename _Ty3>
struct Triad
{
// Переменные структуры
_Ty first; // 1-я переменная. score
_Ty2 second; /// 2-я переменная. i
_Ty3 third; /// 3-я переменная. j
// Определения типов
typedef _Ty first_type;
typedef _Ty2 second_type;
typedef _Ty3 third_type;
};
using triad = Triad<int, int, int>; // Используем 'triad' вместо того, чтобы каждый раз писать аргументы шаблона
triad LCSr(const char *_firstStr, const char *_secondStr,
const int &_idx_i, const int &_idx_j, const int &w)
{
// #1. Один из индексов меньше нуля
if ((_idx_i == -1) || (!_idx_j == -1))
{
return{ 0, -1, -1 };
}
// #2. Если символ конца строки
else if (_firstStr[_idx_i] == '\0' || _secondStr[_idx_j] == '\0')
{
return std::max(LCSr(_firstStr, _secondStr, _idx_i - 1, _idx_j, w),
LCSr(_firstStr, _secondStr, _idx_i, _idx_j - 1, w),
[=](const triad &lhs, const triad &rhs)
{
return (lhs.first > rhs.first);
});
}
// #3. Символ 1-й строки равен символу 2-й строки
else if (_firstStr[_idx_i] == _secondStr[_idx_j])
{
// Получаем результат для 3-х предыдущим подзадачь
triad res[3]{
LCSr(_firstStr, _secondStr, _idx_i + 1, _idx_j + 1, w), // res[0]: Будет использоваться при расчете Score
/* именно тут и зацикливается, далее срабатывает пункт #2 и всё опять по новой */
LCSr(_firstStr, _secondStr, _idx_i + 1, _idx_j, w),
LCSr(_firstStr, _secondStr, _idx_i, _idx_j + 1, w)
};
// Считаем Score
const int Score = res[0].first + 1 + w
* (((res[0].second == (_idx_i + 1)) ? 0 : 1)
- ((res[0].third == (_idx_j + 1)) ? 0 : 1));
// Находим максимальный Score из 3-х
const triad max = std::max({ triad{Score, 0, 0}, res[1], res[2] },
[=](const triad &lhs, const triad &rhs)
{
return (lhs.first > rhs.first);
});
if (max.first == Score)
{
return{ Score + LCSr(_firstStr, _secondStr, _idx_i - 1, _idx_j - 1, w).first, _idx_i, _idx_j };
}
else if (max.first == res[1].first)
{
res[1].first += LCSr(_firstStr, _secondStr, _idx_i - 1, _idx_j - 1, w).first;
return res[1];
}
else
{
res[2].first += LCSr(_firstStr, _secondStr, _idx_i - 1, _idx_j - 1, w).first;
return res[2];
}
}
// #4. Если символы не равны
else
{
return std::max(LCSr(_firstStr, _secondStr, _idx_i - 1, _idx_j, w),
LCSr(_firstStr, _secondStr, _idx_i, _idx_j - 1, w),
[=](const triad &lhs, const triad &rhs)
{
return (lhs.first > rhs.first);
});
}
} |
|
0
|