Преодоление программы выполнения n ^ 2

Есть ли способ преодолеть рекурсию вложенного цикла в C ++ 11? Моя программа работает медленно. Или, скорее, есть более эффективный способ решения для следующей формулы z=|a-b|*|x-y|, где a, b, x и y являются элементами в массиве целых 10000?

Вот код:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream in("int.in");

int main()
{
long long n, n1, z, x, y, in2=0;
in>>n
long long l[n], p[n];
for(x=0;x!=n;x++)
in>>l[x]>>p[x];
for(x=0;x!=n;x++)
{
for(y=x+1;y<n;y++)
{
ineq+=(abs(l[x]-l[y])*abs(p[x]-p[y]))); //executes slow
/*n1=l[x]-l[y]; //Alternative algorithm
if(n1<0)
n1*=-1;
z=p[x]-p[y];
if(z<0)
z*=-1;
in2+=n1*z;*/
}
}
cout<<in2<<"\n";
}

Я пытался изменить типы данных на short int, long, long long а также unsigned, но он либо сбрасывает значения мусора, либо выполняет ошибки « Сегментация ядра ».

Для формулы абсолютного значения я изначально пытался использовать жестко закодированный подход (закомментированный), но он, похоже, выдает значения мусора. Я также пытался оптимизировать решение пресса с abs() функция ineq+=abs(l[x]-l[y])*abs(p[x]-p[y]));, но, кажется, выполняется медленнее. Я не знаю каких-либо других оптимизаций, которые я могу реализовать, поэтому, пожалуйста, порекомендуйте их.

Linux-дружественное решение предпочтительнее. Спасибо.

Примечание: все значения a, b, x и y находятся в пределах диапазона 1<=a,b,x,y<=10000,

Примечание: эта программа читает из файла «int.in», берет первое целое число (количество элементов) и читает каждую новую строку парой (l [x] и p [x] — пары).

Примечание: я также пытался использовать только многомерный массив, но где-то читал, что одномерный массив находится в кеше ЦП, в то время как многомерные данные разбросаны в памяти и работают медленнее.

0

Решение

Проблема может быть нарисована по-другому: вы ищете c и d (оба положительные) в уравнении z=c*d (конечно c is |a-b| а также d is |x-y|).

Итак, сначала закажите ваши массивы. Тогда ищите решение z=c*d затем найдите, какие а и б делают c == a - b правда и х и у, которые делают d == x - y правда.

Как только это будет сделано, вы получите все значения, которые делают ваше уравнение верным, так как abs (a-b) совпадает с abs (b-a)

1

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector