假设我有一个由 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
到目前为止，我发现我需要通过在每次运行时求和一定数量的元素来遍历这个数组。我不确定是否可以实现我上面解释的算法。可能有更好的解决方案，但这是我能想到的最好的解决方案。
12822 次
6 回答
3
您可以使用它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>()
);
于 2012-10-28T12:07:53.500 回答
2
这是怎么回事。给定一个由 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 [ 0 1 ] 总和 = 12
1 [ 1 2 ] 总和 = 10
2 [ 2 3 ] 总和 = 12
3 [ 3 4 ] 总和 = 13
通行证 2：第 3 组：
0 [ 0 1 2 ] 总和 = 15
1 [ 1 2 3 ] 总和 = 19
2 [ 2 3 4 ] 总和 = 16
第 3 组：第 4 组：
0 [ 0 1 2 3 ] 总和 = 24
1 [ 1 2 3 4 ] 总和 = 23
第 4 组：第 5 组：
0 [ 0 1 2 3 4 ] 总和 = 28
于 2012-10-28T13:01:08.903 回答
2
让我们检查包含 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 sum 数组的每个部分的大小都比原始数组小 (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;
}
于 2012-10-28T12:27:02.397 回答
2
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;
}
于 2012-10-28T12:53:52.023 回答
0
我们将原始数组称为 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];
对每个 k 重复上述代码直到 n ，并在每次传递后将结果数组连接到上一次迭代的结果。（确保检查好角落案例）
于 2012-10-28T12:11:24.583 回答
0
在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;
}
这也应该使用先前计算的总和。
于 2012-10-28T13:20:25.493 回答