найти все комбинации, которые имеют ту же сумму более эффективно - PullRequest
Новая
       2

найти все комбинации, которые имеют ту же сумму более эффективно

0 голосов
/ 14 апреля 2019

Я хочу найти все комбинации из четырех чисел в диапазоне от -n до n, которые складываются в нули.Есть ли эффективные алгоритмы для решения этой проблемы?

#include <iostream>
using namespace std;

int main()
{
    int i, j, k, l;
    int size = 20;

    for (i = -size; i <= size; i++)
    {
        for (j = -size; j <= size; j++)
        {
            for (k = -size; k <= size; k++)
            {
                for (l = -size; l <= size; l++)
                {
                    if (i + j + k + l == 0)
                    {
                        cout << i << " " << j << " " << " " << k << " " << l << endl;
                    }
                }
            }

        }
    }
    return 0;

}

Ответы [ 2 ]

1 голос
/ 14 апреля 2019

Вероятно, существует множество методов для оптимизации этого алгоритма, но вот пара простых:

Во-первых, вам не нужен окончательный цикл по числам вообще: 

for (l = -size; l <= size; l++)
    ...

Это потому, что первые три числа уже определены, поэтому существует только одно возможное число, которое может сделать все 4 сложенными в ноль.Все, что вам нужно сделать, это выяснить, что это за число, и проверить, находится ли оно в диапазоне от -n до + n.

int l = 0 - (i+j+k);
if (-l >= -size && l <= size)
     ....

Во-вторых, третий цикл во многих случаях может быть сокращен, например, если i и j оба имеют одинаковый размер, то единственное возможное значение k, которое может привести к добавлению всех нулей к четырем, это+ размер.Используя эту идею, мы можем наложить дополнительные ограничения на этот цикл, сократив его в значительном числе случаев.

Эти две оптимизации должны привести к очень значительному ускорению этого алгоритма.

0 голосов
/ 14 апреля 2019

Смотрите мой код и комментарии.Эффективность алгоритма равна O (N ^ 3), а общее количество решений также равно O (N ^ 3). 

#include <cstdio>
#include <algorithm>


int main(){
      int size = 20;
       for(int a = -size; a <= size; ++a){
            for(int b = -size; b <= size; ++b ) {
                 int c_min, c_max, d, c;
                 //1.  a + b + c +d = 0.
                 //2.  d = -(a+b+c)   
                 //3.   -size <= d <= size
                 //4.  -size <= -(a+b+c) <= size
                 //5.  size >= a +b + c >= -size
                 //6.  -size - (a+b) <= c <= size - (a+b)
                 //7. but,    -size <= c <= size.
                c_min = std::max(-size, -size - (a+b) ) ;
                c_max = std::min(size, size - (a+b) ) ;
                for(c = c_min ; c <= c_max; ++c){
                      d = -(a+b+c);
                      printf("a = %d b = %d  c = %d  d= %d\n", a,b,c,d);                          
                }
            }
       }

   return 0;
}
...