資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中矩陣（或二維陣列）的字首和
此題中，給定一個包含整數值的 2D 陣列 mat[][]. 我們的任務是列印 mat 的字首和矩陣。
字首和矩陣：矩陣中的每個元素都為其上方和左側元素的和。即
prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].
讓我們舉個例子來理解這個問題
Input: arr =[ [4 6 1] [5 7 2] [3 8 9] ] Output:[ [4 10 11] [9 22 25] [12 33 45] ]
為了解決這個問題，一個簡單的解決辦法是遍歷到 i,j 位置的所有元素並對其求字首和。但這對系統來說有點複雜。
一個更有效的解決辦法是使用一個公式來找到字首和矩陣的元素值。
元素在 i,j 位置的通用公式為
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]
一些特殊情況是
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]
展示我們解決方案實現的程式碼
示例
#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;
}輸出
The prefix Sum Matrix is : 1 3 6 5 12 21 12 27 45
更新於： 2020 年 2 月 4 日
4K+ 觀看
廣告