递归矩阵乘法算法未能计算

Question

我们被赋予了使用动态编程在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 
} 

Answer 1

的错误似乎是很清楚，你所呼叫的at方法并传递值row和col这并不比行数和列数...这在代码很明显较小：

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)，就是因为参数at是rows和cols，而不是周围的其他方式...

除此之外，递归步骤是错误的，因为递归中的下一步没有比原始问题更小的问题（实际上它的大小完全相同，因为minmult(M,P,d)调用了minmult(M,P,d)。一旦你解决了断言，这将以堆栈溢出的形式将你踢出。

最后，还不清楚代码的意图是什么，您应该花时间用笔和纸来解决问题，然后将解决方案映射到您选择的编程语言。