0

我有一个包含一些值的数组，例如

A=[a,b,c];

c++中计算以下最简单/最快的方法是什么：

int SUM;
SUM= a*b + a*c + b*a + b*c + c*a + c*b;

在这种情况下a*c != c*a

在实际情况下，我有不同大小的大数组，并将从其他数组中获取 a、b 和 c 的值。

/提前致谢

4

7 回答 7

4

也许是这样（假设您实际上想要同时添加 a * b 和 b * a）：

for (int i = 0; i < array_size - 1; ++i) {
    for (int j = i + 1; j < array_size; ++j) {
        sum += a[i] * a[j] * 2;
    }
}

甚至可能是一个更聪明的版本，可以降低算法复杂度（O(n) vs O(n*n)）：

对于数组中的每个成员 a[x]，您要相加：

a[0] * a[x] + a[1] * a[x] + ... + a[n] * a[x] - a[x] * a[x]

将公因式分解后与以下相同：

a[x] * (a[0] + a[1] + ... + a[n] - a[x])

现在可以只计算一次所有数组项的总和：

int array_sum = std::accumulate(a, a + array_size, 0);  //#include <numeric> or use a simple loop
int sum = 0;
for (int i = 0; i < array_size; ++i) {
    sum += a[i] * (array_sum - a[i]);
}
于 2010-02-09T12:29:50.400 回答
2

试用代码：

int sum = 0;

for(int i=0 ; i < size ; i++)
{
    int tmp = 0;
    for(int j=0 ; j < size ; j++)
    {
          if( i != j )
             tmp += a[i] * a[j];
    }
    sum += tmp;
}
于 2010-02-09T11:55:25.587 回答
2 
int SUM = 0;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if (i != j)  {
            SUM += A[i] * A[j];
        }
    }
}

但除非 A 具有可变大小，否则最好将这个公式直接写下来：

int SUM = A[0] * A[1] + ...;
于 2010-02-09T11:55:51.763 回答
2

除非我遗漏了什么，否则它应该很简单：

int sum = 0;

for(unsigned int i = 0; i < ARRAYSIZE; i++){
    for(unsigned int j = 0; j < ARRAYSIZE; j++){
        if(i != j){
            sum += A[i] * A[j];
        }
    }
}
于 2010-02-09T11:59:10.387 回答
1

Visitor 的代码可以进一步简化：

const int array_sum( std::accumulate(a, a + array_size, 0) );
int sum( array_sum * array_sum );
for (int i = 0; i < array_size; ++i) {
    sum -= a[i] * a[i];
}

我想可以使用一个临时的：

const int array_sum( std::accumulate(a, a + array_size, 0) );
int sum( array_sum * array_sum );
for (int i = 0; i < array_size; ++i) {
    const int tmp( a[i] );
    sum -= tmp * tmp;
}

当然，平方步骤也可以使用 STL 完成：

const int array_sum( std::accumulate(a, a + array_size, 0) );
std::transform( a, a + array_size, a, a, std::multiplies<int>() );  // store in a
const int sum( array_sum * array_sum - std::accumulate(a, a + array_size, 0) );

编辑：一个简单的循环，单程：

int array_sum( 0 ), square_sum( 0 );
for( int i(0) ; i < array_size; ++i )
{
   int tmp(a[i]);
   array_sum += tmp;
   square_sum += tmp * tmp;
}
const int sum(  array_sum * array_sum - square_sum );
于 2010-02-09T13:17:52.690 回答
0

这是一个用 9 个 if 换取 3 个乘法和 3 个减法的解决方案。

int sum = 0;
for (int i = 0; i < 3; ++i)
{
    for (int j = 0; j < 3; ++j)
    {
        sum += A[i] * A[j];
    }
    sum -= A[i] * A[i];
}
于 2010-02-09T12:29:18.200 回答
0

我会使用更短的循环：

int SUM = 0;
for (int i = 0; i < 2; i++) {
    for (int j = i+1; j < 3; j++) {
        SUM += A[i] * A[j];
        SUM += A[j] * A[i];
    }
}

然后这消除了对 if (i != j) 检查的需要，并减少了 i++ 和 j++ 以及 i<2 和 j<3 调用。

于 2010-02-09T14:49:58.377 回答