C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C ++での行列(または2D配列)のプレフィックス合計


この問題では、整数値mat[][]の2D配列が与えられます。私たちの仕事は、マットの接頭辞合計行列を印刷することです。

プレフィックス合計マトリックス: 行列のすべての要素は、その上下の合計要素です。つまり

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]
]

この問題を解決するための簡単な解決策の1つは、i、jの位置まですべての要素をトラバースしてprefixSumを見つけ、それらを追加することです。ただし、システムにとっては少し複雑です。

より効果的な解決策は、prefixSum行列の要素の値を見つけるための式を使用することです。

ij位置の要素の一般式は次のとおりです

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

  1. C++合計配列パズル

    配列 同じデータ型の複数の要素を格納するデータ構造です。値のセット全体を一度に保存できます。ただし、その長さは事前に定義する必要があります。 この合計配列パズルでは、nと言う明確なサイズの配列A1が与えられます。このパズルを解くために、位置が使用されている要素を除く配列のすべての要素の合計を格納するS1という配列を作成します。たとえば、S1 [3]が計算されている場合、位置4の要素を除くA1のすべての要素の合計が求められます。 例- Array A1 = {1,2,3,4,6} Output S1 = {15,14,13,12,10} 説明 −合計配列を計算するには、初期配列の各要素を合計

  2. C ++の合計配列パズル?

    ここでは、配列に関連する1つの興味深い問題を確認します。 n個の要素を持つ配列があります。 n個の要素の別の配列を作成する必要があります。ただし、2番目の配列のi番目の位置は、i番目の要素を除く最初の配列のすべての要素の合計を保持します。そして、1つの制約は、この問題では減算演算子を使用できないことです。 減算演算を使用できれば、すべての要素の合計を取得し、最初の配列のi番目の要素を減算して、2番目の配列のi番目の場所に格納することで、この問題を簡単に解決できます。 ここでは、毎回要素を追加することでこれを解決し、0..n-1のiについては、位置iの要素を無視します。ポイントを得るためのア