Алгоритм рекурсивного матричного умножения не в состоянии вычислить

Нам дали задание использовать динамическое программирование для кодирования программы на 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
}

0

Решение

Ошибка кажется вполне понятной, вы звоните 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), Как только вы исправите утверждение, вы получите удар в виде переполнения стека.

Наконец, неясно, какова цель кода, вам нужно время, чтобы решить проблему ручкой и бумагой, а затем сопоставить решение с вашим языком программирования по вашему выбору.

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector