динамический 2d массив дает неверный результат - PullRequest
Новая
       5

динамический 2d массив дает неверный результат

0 голосов
/ 10 февраля 2019

Я пишу код для вычисления длины самой длинной общей подпоследовательности.

Может кто-нибудь объяснить мне, почему эти две процедуры дают разные результаты при создании экземпляра с X = {2, 3, 4}, n =3 и Y = {3, 5, 3, 2, 4}, m = 5

Код # 1 

template<typename T>
int LLCS(T X[], const int& n, T Y[], const int& m){
    array<int>d(n+1,m+1);
    int i,j;
    for(i = 0; i <= m; ++i)d(0,i) = 0;
    for(i = 1; i <= n; ++i){
        d(i,0) = 0;
        for(j = 1; j <= m; ++j)
            if(X[i-1] == Y[j-1])d(i,j) = 1 + d(i-1,j-1);
            else d(i,j) = max(d(i-1,j), d(i,j-1));
    }
    return d(n,m);
}

Код # 2 

const int N = 10;   //n, m < N-1

template<typename T>
int _LLCS(T X[], const int& n, T Y[], const int& m){
    T d[N][N];
    int i, j;
    for(i = 0; i <= m; ++i)d[0][i] = 0;
    for(i = 1; i <= n; ++i){
        d[i][0] = 0;
        for(j = 1; j <= m; ++j)
            if(X[i-1] == Y[j-1])d[i][j] = 1 + d[i-1][j-1];
            else d[i][j] = max(d[i-1][j], d[i][j-1]);
    }
    return d[n][m];
}

Результат от Код # 1 равен 1

Результат от Код # 2 равен 2 (что является правильнымответ)

код контейнера массива 

template<typename T>
class array {
private:
    T *root;
    std::size_t _n, _m;
public:
    array(const std::size_t& n) : root(new T[n]), _n(1), _m(1) {}
    array(const std::size_t& n, const std::size_t& m)
         : root(new T[n * m]), _n(m), _m(1) {}

    ~array() { delete[] root; }
    T& operator[](const std::size_t& x) { return root[x]; }
    T& operator()(const std::size_t& x, const std::size_t& y){
        return root[_n * x + y];
    }
};
...