Tổng tiền tố của Ma trận (Hoặc Mảng 2D) trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng 2D gồm các giá trị số nguyên mat [] []. Nhiệm vụ của chúng ta là in ma trận tổng tiền tố của mat.

Ma trận tổng tiền tố: mọi phần tử của ma trận là tổng các phần tử ở trên và bên trái của nó. tức là

prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].

Hãy lấy một ví dụ để hiểu vấn đề

Input: arr =[
   [4   6   1]
   [5   7   2]
   [3   8   9]
]
Output:[
   [4   10   11]
   [9   22   25]
   [12   33   45]
]

Để giải quyết vấn đề này, một giải pháp đơn giản là tìm prefixSum bằng cách duyệt qua tất cả các phần tử cho đến vị trí i, j và thêm chúng. Nhưng nó hơi phức tạp đối với hệ thống.

Một giải pháp hiệu quả hơn sẽ là sử dụng công thức tìm giá trị của các phần tử của ma trận prefixSum.

Công thức chung cho phần tử ở vị trí ij là

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]

Một số trường hợp cụ thể là

For i = j = 0, prefixSum[i][j] = a[i][j]
For i = 0 and j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j]
For i > 0 and j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]

Mã để hiển thị việc triển khai giải pháp của chúng tôi

Ví dụ

#include <iostream>
using namespace std;
#define R 3
#define C 3
void printPrefixSum(int a[][C]) {
   int prefixSum[R][C];
   prefixSum[0][0] = a[0][0];
   for (int i = 1; i < C; i++)
   prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];
   for (int i = 0; i < R; i++)
   prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];
   for (int i = 1; i < R; i++) {
      for (int j = 1; j < C; j++)
      prefixSum[i][j]=prefixSum[i- 1][j]+prefixSum[i][j- 1]-prefixSum[i- 1][j- 1]+a[i][j];
   }
   for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++)
      cout<<prefixSum[i][j]<<"\t";
      cout<<endl;
   }
}
int main() {
   int mat[R][C] = {
      { 1, 2, 3},
      { 4, 5, 6},
      { 7, 8, 9}
   };
   cout<<"The prefix Sum Matrix is :\n";
   printPrefixSum(mat);
   return 0;
}

Đầu ra

The prefix Sum Matrix is :
1   3   6
5   12   21
12   27   45