#c #combinations
#c #комбинации
Вопрос:
Я хочу найти все комбинации из четырех чисел в диапазоне от 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;
}
Комментарии:
1. Да, такого рода проблемы обычно решаются с помощью какой-либо формы динамического программирования. Я бы сказал, что этот вопрос относится к cs.stackexchange.com
2. Это сложная проблема np?
3. вам не нужно считать все числа положительными или все числа отрицательными
4. @learning_cpp В каком смысле np сложно? Это не проблема решения. Я бы предположил, что количество комбинаций может быть экспоненциальной функцией от n . Так что нет, полиномиального решения быть не может.
5. @Quimby вы правы, поэтому кажется, что проблемы дорого решать в природе
Ответ №1:
Вероятно, существует множество методов оптимизации этого алгоритма, но вот несколько простых.
Во-первых, вам вообще не нужен заключительный цикл по числам:
for (l = -size; l <= size; l )
...
Это связано с тем, что первые три числа уже определены, поэтому существует только одно возможное число, которое может привести к тому, что все 4 будут равны нулю. Все, что вам нужно сделать, это выяснить, что это за число, и проверить, находится ли оно в диапазоне от -n до n .
int l = 0 - (i j k);
if (-l >= -size amp;amp; l <= size)
....
Во-вторых, третий цикл может быть сокращен во многих случаях, например, если i и j имеют одинаковый размер, тогда единственное возможное значение k, которое может привести к тому, что все четыре числа будут равны нулю, равно size . Используя эту идею, мы можем наложить дополнительные ограничения на этот цикл, сократив его в значительном количестве случаев.
Эти две оптимизации должны привести к очень значительному ускорению этого алгоритма.
Комментарии:
1. Это разумное улучшение! Но можно ли решить эту проблему за полиномиальное время? Предположим, у меня больший размер и более глубокий цикл. Я сталкиваюсь с этой проблемой при объединении функции в пространстве Фурье
2. Почти наверняка есть более быстрые способы сделать это, думая об этом. Начиная с простого случая двух чисел, набор решений находится на строке x y = 0. Три числа определяют плоскость, а четыре числа определяют гиперплоскость. Вы должны быть в состоянии вычислить пересечение этой гиперплоскости с гиперкубом, выровненным по началу координат, что ограничивает ваш ввод. Вы должны иметь возможность выполнять итерации по гиперплоскости с тремя циклами, генерируя решения каждый раз.
Ответ №2:
Смотрите Мой код и комментарии. Эффективность алгоритма равна 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= %dn", a,b,c,d);
}
}
}
return 0;
}