0

動的計画法を使用して、行列乗算用のC++でプログラムをコーディングするという割り当てが与えられました。彼は再帰を使用するように私たちに言い、カスタムで書かれた行列クラスを私たちに与えました。次の再帰的アルゴリズムを作成しましたが、実行するとエラーが発生します。

Object& Matrix<Object>::at(uint, uint) [with Object = unsigned int, uint = unsigned int]: Assertions 'row < rows && col < cols' failed.

なぜこれが起こっているのかについてのアイデアはありますか?私は彼の行列クラスと私の再帰的行列乗算法を以下に含めました。

#ifndef MATRIX_H
#define MATRIX_H

#include <cassert>
typedef unsigned int uint;

template <class Object>
class Matrix
{
public:
    Matrix( uint rows, uint cols );
    Object & at( uint row, uint col );
    const Object & at( uint row, uint col ) const;
    ~Matrix();
    Matrix( const Matrix<Object> & m ); // Copy constructor
    Matrix & operator= ( const Matrix<Object> & m );   // Assignment operator
    uint numrows() const;
    uint numcols() const;

private:
    uint rows;
    uint cols;
    Object* data;
};

template <class Object>
Matrix<Object>::Matrix( uint rows, uint cols )
: rows( rows ), cols( cols )
{
    assert( rows > 0 && cols > 0 );
    data = new Object[ rows * cols ];
}

template <class Object>
Matrix<Object>::~Matrix()
{
    delete[] data;
}

template <class Object>
Object & Matrix<Object>::at( uint row, uint col )
{
    assert( row < rows && col < cols );
    return data[ cols * row + col ];
}

template <class Object>
const Object & Matrix<Object>::at( uint row, uint col ) const
{
    assert( row < rows && col < cols );
    return data[ cols * row + col ];
}

template <class Object>
uint Matrix<Object>::numrows() const
{
    return rows;
}

template <class Object>
uint Matrix<Object>::numcols() const
{
    return cols;
}

int minmult( Matrix<uint> & P,
         Matrix<uint> & M,
         const vector<uint> & d,
         uint i,
         uint j )
{


if( M.at(i,j) != INF )
{
    return M.at(i,j);               //already has been defined
}
else if( i == j )
{
    M.at(i,j) = 0;                  //base case
}
else
{
    //M.at(i,j) = UINT_MAX;         //initialize to infinity
    for( uint k = i; k <= j-1; k++)
    {
        uint ops = minmult(P, M, d, i, k)
            + minmult(P, M, d, k+1, j)
            + d.at(i-1)*d.at(k)*d.at(j);
        if( ops < M.at(i,j))
        {
            M.at(i,j) = ops;        
            P.at(i,j) = k;          
        }
    }
}
return M.at(i,j);                  //returns the final cost
}
4

1 に答える 1

1

エラーは非常に明確なようです。メソッドを呼び出して、行と列の数よりも小さくない値を渡しています...コードで明らかですatrowcol

uint i = M.numcols();
uint j = M.numrows();
if(i == j) {
    M.at(i,j) = 0;    // i == numcols() thus !(i<numcols()) 
                      // j == numrows() thus !(j<numrows())

を呼び出すつもりだったと仮定するとM.at(j,i)、つまり、 への引数atrowsandcolsであり、その逆ではないため...

それ以外は、再帰の次のステップには元の問題よりも小さな問題がないため、再帰ステップが間違っています (実際にはまったく同じサイズminmult(M,P,d)ですminmult(M,P,d)。スタック オーバーフローの形式。

最後に、コードの意図が明確でない場合は、時間をかけてペンと紙で問題を解決し、その解決策を選択したプログラミング言語にマッピングする必要があります。

于 2013-03-05T03:35:42.043 に答える