Сумма независимой диагонали в матрице

(Раньше здесь был параграф, но при втором взгляде вы не ошиблись, о чем говорилось.)

Поскольку вы не публиковали в Code Reviews, вот решение вместо подробного анализа кода. (Если вы хотите, чтобы оригинальный подход работал, я бы предложил пошагово пройти его в отладчике и проверить, где ваши переменные вначале получают неправильное значение.) У него много шаблонов, чтобы он компилировался и выполнялся, но часть, которая вас больше всего интересует diag_sums() и его комментарии.

Одна идея здесь состоит в том, чтобы использовать ООП для автоматической проверки границ доступа к вашему массиву. Последнее очень важно для отлова отдельных ошибок и тому подобного. Вы можете отключить его в производственной среде, если хотите, но вы действительно не хотите отключать предупреждения, когда ваша программа переполнена буфером. Другие оптимизации здесь включают локальность доступа к данным и снижение прочности операций: вместо того, чтобы проверять на каждой итерации, достигли ли мы правого края и нижнего края, мы можем просто заранее вычислить длину каждой диагонали.

Поскольку определение диагонального числа К матрицы a с M Строки эквивалентны: все элементы a[i][j] такой что такой что M — К знак равно я — J, алгоритм обеспечивает корректность, поддерживая инвариант, который сохраняется всякий раз, когда мы добавляем 1 к обоим я а также J, начиная, когда либо я или же J 0 и останавливается всякий раз, когда я знак равно M или же J знак равно N, то есть, проходя каждый шаг диагонали от левого или верхнего края к правому или нижнему краю, в зависимости от того, что наступит раньше.

#include <assert.h>
#include <iostream>
#include <stddef.h>
#include <stdlib.h>
#include <utility>
#include <vector>

using std::cin;
using std::cout;

template <typename T>
class matrix {
public:
matrix( const ptrdiff_t rows,
const ptrdiff_t cols,
std::vector<T>&& elems )
: rows_(rows), cols_(cols), elems_(elems)
{
assert( rows_ > 0 );
assert( cols_ > 0 );
assert( elems_.size() == static_cast<size_t>(rows_*cols_) );
}

matrix( const ptrdiff_t rows,
const ptrdiff_t cols,
const std::vector<T>& elems )
: matrix( rows, cols, std::move(std::vector<T>(elems)) )
{}

matrix( const matrix<T>& ) = default;
matrix( matrix<T>&& ) = default;
matrix& operator= ( const matrix<T>& ) = default;
matrix& operator= ( matrix<T>&& ) = default;

T& operator() ( const ptrdiff_t m, const ptrdiff_t n )
{
assert( m >= 0 && m < rows_ );
assert( n >= 0 && n < cols_ );
return elems_[static_cast<size_t>(m*cols_ + n)];
}

const T& operator() ( const ptrdiff_t m, const ptrdiff_t n ) const
{
/* Because this call does not modify any data, and the only reason the
* member function above cannot be const is that it returns a non-const
* reference to an element of elems, casting away the const qualifier
* internally and then returning a const reference is a safe way to
* re-use the code.
*/
matrix<T>& nonconst = *const_cast<matrix<T>*>(this);
return nonconst(m,n);
}

ptrdiff_t rows() const { return rows_; }
ptrdiff_t cols() const { return cols_; }

private:
ptrdiff_t rows_;
ptrdiff_t cols_;
std::vector<T> elems_;
};

template<typename T>
std::ostream& operator<< ( std::ostream& out, const matrix<T>& x )
/* Boilerplate to print a matrix. */
{
const ptrdiff_t m = x.rows(), n = x.cols();

for ( ptrdiff_t i = 0; i < m; ++i ) {
out << x(i,0);
for ( ptrdiff_t j = 1; j < n; ++j )
out << ' ' << x(i,j);

out << '\n';
} // end for

return out;
}

using elem_t = int;

std::vector<elem_t> diag_sums( const matrix<elem_t>& a )
/* Return a vector of all the diagonal sums of a.
*
* The first diagonal sum is a(rows-1,0)
* The second is a(rows-2,0) + a(rows-1,1)
* The third is a(rows-3,0) + a(rows-2,1) + a(rows-1,2)
* And so on.  I.e., the kth diagonal is the sum of all elements a(i,j) such
* that i - j == rows - k.
*
* If a is a M×N matrix, there are M diagonals starting in column zero, and
* N-1 diagonals (excluding the one containing a(0,0) so we don't count it
* twice) starting in row 0.  We process them bottom to top, then left to
* right.
*
* The number of elements in a diagonal starting at a(i,0) is min{M-i, N}.  The
* number of elements in a diagonal starting at a(0,j) is min{M, N-j}.  This is
* because a diagonal stops at either the bottom edge or the left edge of a.
*/
{
const ptrdiff_t m = a.rows(), n = a.cols();
std::vector<elem_t> result;
result.reserve( static_cast<size_t>(m + n - 1) );

for ( ptrdiff_t i = m-1; i > 0; --i ) {
elem_t sum = 0;

const ptrdiff_t nk = (m-i) < n ? (m-i) : n;
for ( ptrdiff_t k = 0; k < nk; ++k )
sum += a(i+k, k);

result.emplace_back(sum);
} // end for i

for ( ptrdiff_t j = 0; j < n; ++j ) {
elem_t sum = 0;

const ptrdiff_t nk = m < (n-j) ? m : (n-j);
for ( ptrdiff_t k = 0; k < nk; ++k )
sum += a(k, j+k);

result.emplace_back(sum);
} // end for j

return result;
}

matrix<elem_t> read_input_matrix( const int row, const int column )
/* Reads in row*column consecutive elements from cin and packs them into a
* matrix<elem_t>.
*/
{
assert(row > 0);
assert(column > 0);

const ptrdiff_t nelements = row*column;
assert(nelements > 0); // Check for overflow.

std::vector<elem_t> result;
result.reserve(static_cast<size_t>(nelements));

for ( ptrdiff_t i = nelements; i > 0; --i ) {
int x;
cin >> x;
assert(cin.good());
result.push_back(x);
}

return matrix<elem_t>( row,
column,
std::move(result) );
}

template<typename T>
bool print_sequence( const T& container )
/* Prints the contents of a container in the format
* "{47, 94, 124, 160, 148, 36, 5}".
*/
{
cout << "{";

if ( container.begin() != container.end() )
cout << *container.begin();

for ( auto it = container.begin() + 1; it < container.end(); ++it )
cout << ", " << *it;

cout << "}\n";

return cout.good();
}

/* A simple test driver that reads in the number of rows, the number of
* columns, and then row*columns int values, from standard input.  It
* then passes the result to diag_matrix(), E.g.:
*
* 5 3
* 52 35  5
*  2 71  1
*  3 60 25
* 79 55 98
* 47 15 66
*/
int main()
{
int rows, columns;
cin >> rows;
cin >> columns;

assert(cin.good());

const matrix<elem_t> input_matrix = read_input_matrix( rows, columns );
// cout << input_matrix; // Instrumentation.
const std::vector<elem_t> sums = diag_sums(input_matrix);

print_sequence(sums);

return EXIT_SUCCESS;
}

Вы также можете просто сделать print_sequence(diag_sums(read_input_matrix( rows, columns ))),