遞歸矩陣乘法算法未能計算

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)。一旦你解決了斷言，這將以堆棧溢出的形式將你踢出。

最後，還不清楚代碼的意圖是什麼，您應該花時間用筆和紙來解決問題，然後將解決方案映射到您選擇的編程語言。