перестановки в с ++

Question

У меня есть массив с некоторыми значениями, например,

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 из других массивов.

/ Заранее спасибо

Answer 1

Возможно, так (если вы действительно хотите добавить и 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) против 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]);
}

Answer 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];
        }
    }
}

Answer 3

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] + ...;

Answer 4

опробуйте код:

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;
}

Answer 5

Код посетителя может быть дополнительно упрощен:

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 );

Answer 6

Я бы использовал более короткие циклы:

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. </p>

Answer 7

Вот решение, которое торгует 9 ifs за 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];
}