矩阵中对角线元素之和的求解

Question

矩阵中对角线元素之和的求解

10

我目前正在为一项考试学习，并尝试处理动态矩阵。我遇到了一个问题，关于计算用户选择的值和大小的矩阵的每个对角线的总和。我的程序旨在通过一个函数打印出每个对角线总和的值，该函数的参数是矩阵及其大小。我将展示代码并深入描述它。

----------------
| 52 | 35 | 5  |  Example of matrix.
----------------  Imagine the first diagonal to be the one which goes right-to-left
| 2  | 71 | 1  |  and only consists in the number "47".
----------------  The second diagonal would be the one which goes right-to-left and
| 3  | 60 | 25 |  consists in the number "15" and "79".
----------------  So to get the sum of the second diagonal it would be:
| 79 | 55 | 98 |     
----------------  sum = m[n_rows - 1][diag - 2] + m[n_rows - 2][diag - 1]
| 47 | 15 | 66 | 
----------------  When diag > columns, in order to avoid error regarding matrix size,
                  I should lower the quantity "n_rows - 1" by the quantity "diag - n_columns".

这就是我根据描述想要做的事情：

void diag_matrix(int** m, int righe, int colonne){//righe = rows, colonne = columns. 
//M is the matrix.

// diag is the number of the diagonal I'm considering.
    for(int diag = 1; diag < (righe + colonne); diag++){ 

        int sum = 0;// the sum
        int i = 0;// the counter of the cicle
        int l = 0;// this is the value to riallign the row in case diag > column
        int temp = diag;//I use this variable not to modify the value of diag.

        // What I want is: when the column-index/row-index of the matrix reaches 0, the cicle will interrupt (after final iteration);
        while(righe - i - l - 1 > 0 || diag - 1 - i > 0){

            if (diag > colonne){//this condition changes l-value only if diag value is greater than column. Explanation outside the code
                l = diag - colonne;//this is the value to subtract to row-index
                temp = colonne;//this position is necessary to set column-index to its maxium.
            }

            sum = sum + m[righe - 1 - l - i][temp -1 - i];//pretty clear I think.
            i++;//the i is incremented by one.

        }// end of while-statement

        cout << "Somma Diagonale " << diag << " = " << sum << ".\n";

    }// end of for-statement

}//end of function declaration

显然它不起作用，但我无法弄清问题所在。

- King Powa

1

只是想澄清一下...你想从右下角开始，然后向上，向右工作吗？ - Support Ukraine

1

你是否被那个数组的表示和函数签名所限制，或者如果需要，你可以使用不同的数据结构吗？ - Davislor

1

在这种情况下，模运算非常有用。知道矩阵中的起始位置后，您可以对i、j进行模加/减，具体取决于您前进的四个对角方向之一，直到检测到i或j的环绕。 - CJPN

@Davislor 如果使用不同的数据结构可以实现更高效的数据管理，我很乐意尝试。然而，我的主要目的是理解代码中的错误。 - King Powa

这里的一个通用原则是：始终、始终、始终检查数组访问是否存在缓冲区溢出和下溢。 - Davislor

显示剩余6条评论

2个回答

2

这里曾经有一段话，但仔细看后，您并没有犯它所提到的错误。

既然您没有在代码审查中发布帖子，那么这里提供一个解决方案，而不是详细的代码审查。（如果您想让原始方法起作用，我建议您在调试器中逐步执行它，并检查变量何时首次获得错误值。）它有很多样板文件使其编译和运行，但您最感兴趣的部分是diag_sums()及其注释。

这里的一个想法是使用面向对象编程自动检查数组访问的边界。后者对于捕获一些偏移错误非常重要。如果您想，在生产中可以关闭它，但当您的程序存在缓冲区溢出时，您真的不想消除警告。其他优化包括数据访问的局部性和操作的强度降低：与其在每次迭代中检查是否已到达右侧和底部，我们可以预先计算每个对角线的长度。

对于具有M行的矩阵a的对角线数k的定义等价于：所有元素a[i][j]满足条件M - k = i - j。该算法通过维护不变量确保正确性，当我们从i和j中的任一值为0开始，在加1到两个值时保持不变，直到i = 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 )))。

- Davislor

非常感谢您的时间和耐心。我是这个论坛的新手，也许我应该在您指出的部分发布帖子。无论如何，您的解决方案涉及到类，这是我的考试范围之外的一个主题。我应该指出来的。然而，我会尝试运行代码并学习它，以便理解其结构，这似乎并不难完全理解。再次感谢您的耐心，并为我的错误道歉。 - King Powa

为什么要使用模板？难道不是过度设计吗？ - Sugar

@Sugar 可能吧！ - Davislor

@KingPowa 你问了一个好问题。如果有帮助的话，你可以基本上忽略使用模板的解决方案的部分。也许我应该将其拆分为模块，以更加强调与你的问题相关的部分。基本上，这个类是一种非常高级的方式，可以写成a(i,j)而不是a[i][j]。虽然我是这样写的，因为我认为它有优势，特别是在捕捉错误方面。 - Davislor

例如，当我第一次编写 diag_sums() 函数时，在两个位置中的一个位置上，我最初键入了 m-1 作为 m-i。（这可能意味着我应该写 min() 而不是重复自己。）这立即且可重现地触发了一个断言，我可以在调试器和回溯中捕获它。同样，当我在某个地方交换了 rows 和 cols 时也是如此。也许有些 C++ 程序员不会这样自残，而且不需要进行防御性编码，但我不行。 - Davislor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tevemadar · Accepted Answer

你可以简化你的代码，找到每条对角线的起始位置，然后只要坐标在矩阵内，就可以在矩阵中移动。类似这样：

#include <iostream>

using namespace std;

void diag_matrix(int** m, int rows, int cols)
{
    for (int diag = 1; diag < rows + cols; diag++)
    {
        int x, y;
        if (diag < rows)
        {
            y = rows - diag;
            x = 0;
        }
        else
        {
            y = 0;
            x = diag - rows;
        }
        int sum = 0;
        cout << "Summing diagonal #" << diag << ":";
        while ((x < cols) && (y < rows))
        {
            sum += m[y][x];
            cout << " " << m[y][x];
            x++;
            y++;
        }
        cout << " result: " << sum << "." << endl;
    }
}

int main(int argc, char* argv[])
{
    int rows = 5, cols = 3;
    int **m = new int*[rows];
    for (int i = 0; i < rows; i++)
        m[i] = new int[cols];
    m[0][0] = 52; m[0][1] = 35; m[0][2] =  5;
    m[1][0] =  2; m[1][1] = 71; m[1][2] =  1;
    m[2][0] =  3; m[2][1] = 60; m[2][2] = 25;
    m[3][0] = 79; m[3][1] = 55; m[3][2] = 98;
    m[4][0] = 47; m[4][1] = 15; m[4][2] = 66;
    diag_matrix(m, rows, cols);
    for (int i = 0; i < rows; i++)
        delete[] m[i];
    delete[] m;
    return 0;
}