n個の要素で構成される配列があるとします。
1 2 3 4 5 6 ... n
C ++を使用して、この配列内の連続する要素の合計を抽出する方法を見つける必要があります。このような：
1, 2, 3,...n, 1+2, 2+3, 3+4,...(n-1)+n, 1+2+3, 2+3+4,...(n-2)+(n-1)+n,...1+2+3...n
これまでのところ、実行ごとに特定の数の要素を合計して、この配列を反復処理する必要があることがわかりました。上で説明したアルゴリズムを実装できるかどうかはわかりません。より良い解決策があるかもしれませんが、これは私が思いつくことができる最高のものです。
これを行うために使用できますstd::transform：
std::transform(
v.begin(), v.end()-1,
v.begin()+1,
std::ostream_iterator<int>(std::cout, "\n"),
std::plus<int>()
);
もちろん、出力としてostream_iteratorを使用する必要はありません。また、別のコンテナーイテレーター、またはstd::back_inserterコンテナーやその他のコンテナーを使用することもできます。OutputIterator
http://en.cppreference.com/w/cpp/algorithm/transform
http://en.cppreference.com/w/cpp/utility/functional/plus
http://en.cppreference.com/w/cpp/container/vector
編集：
std::vector<int> v(100), t;
//this just populates v with 1,2,3...100
std::iota(v.begin(), v.end(), 1);
std::transform(
v.begin(), v.end()-1, v.begin()+1,
std::back_inserter(t),
std::plus<int>()
);
std::transform(
t.begin(), t.end()-1, v.begin()+2,
std::ostream_iterator<int>(std::cout, "\n"),
std::plus<int>()
);
4つの要素でケースを調べてみましょう。
{1,3,4,5, // from original array
4,7,9, // sum of 2 consecutive elements
8,12, // sum of 3
13} // sum of 4
ご覧のとおり、N合計配列のすべての部分は、元の配列より（N-1）小さいサイズです。したがって、次のサイズのターゲット配列が必要です：N +（N-1）+（N-2）+ ...1-これはN*（1 + N）/2です
int* createSumArray(int* arr, int size)
{
int ti = 0; // target index
int* ta = new int[size*(size+1)/2];
for (int s = 1; s <= size; ++s) // how many elements to sum
{
for (int si = 0; si < size + 1 - s; ++si)
{
ta[ti] = 0;
for (int i = si; i < si + s; ++i)
ta[ti] += arr[i];
++ti;
}
}
return ta;
}
ideoneのテストを参照してください
int main()
{
int ptr=0,i,j,k;
int Ar[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
int n=13;
int *Res;
Res=(int*)calloc(n*(n+1)/2,sizeof(int));
for(i=1;i<=n;i++) //tells about how many element's sum we need
for(j=i;j<=n;j++)
{
for(k=0;k<i;k++)
{
Res[ptr]+=Ar[j-i+k];
}
ptr++;
}
for(int x=0;x<ptr;x++)
cout<<Res[x]<<"\t";
return 0;
}
これはどう。5つの整数の配列が与えられた場合：5、7、3、9、4
void DoMaths (void)
{
int iArray [] = { 5, 7, 3, 9, 4 } ;
int iSize = 5 ;
int iGroup ;
int iIndex ;
int iPass ;
int iResults ;
int iStart ;
int iSum ;
// Init
iGroup = 1 ;
iResults = iSize ;
// Repeat for each pass
for (iPass = 0 ; iPass < iSize ; iPass ++)
{
printf ("\n") ;
printf ("Pass %d : Group %d :\n", iPass, iGroup) ;
// Repeat for each group of integers in a pass
for (iStart = 0 ; iStart < iResults ; iStart ++)
{
iSum = 0 ;
printf (" %d [ ", iStart) ;
for (iIndex = iStart ; iIndex < (iStart + iGroup) ; iIndex ++)
{
printf ("%d ", iIndex) ;
iSum += iArray [iIndex] ;
}
printf ("] sum = %d \n", iSum) ;
}
iGroup ++ ;
iResults -- ;
}
return ;
}これにより、次の結果が得られます...
パス0：グループ1：
0[0]合計=5
1[1]合計=7
2[2]合計=3
3[3]合計=9
4[4]合計=4
パス1：グループ2：
0[01]合計=12
1[12]合計=10
2[23]合計=12
3[34]合計=13
パス2：グループ3：
0 [012]合計=15
1 [123]合計=19
2 [234]合計=16
パス3：グループ4：
0 [0 123]合計=24
1 [1 234]合計=23
パス4：グループ5：
0 [0 1 234]合計=28
元の配列をAと呼びましょう。
k個の連続する要素の合計の配列をBと呼びましょう。
k+1個の連続する要素の合計の配列をCと呼びましょう。
各配列のサイズはnです。
Cの最初のk-2セルは無関係です。
for(int i = k-1; i < n; i++)
C[i] = A[i-1] + B[i];
nまでのkごとに上記のコードを繰り返し、各パスの後に、結果の配列を前の反復の結果に連結します。（コーナーケースをよく確認してください）
ideone.comで動作することを確認してください：
std::vector<std::vector<int> > sums(int array[], int size)
{
std::vector<std::vector<int> > result(size - 1);
//build the two element sums
for(int *p = array; p - array < size - 1; ++p)
result[0].push_back(std::accumulate(p, p + 2, 0));
//build the rest of the sums
for(int i = 1; i < size - 1; ++i)
for(int j = 0; j < size - (i + 1); ++j)
result[i].push_back(result[i - 1][j] + array[i + j + 1]);
return result;
}
これは、以前に計算された合計も使用する必要があります。