0

有没有办法克服 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，但它要么转储垃圾值，要么执行“Segmentation Core Fault”错误。long longunsigned

对于绝对值公式，我最初尝试使用硬编码的方法（已注释掉），但它似乎输出了垃圾值。我也尝试使用abs()函数优化 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] 是对）。

旁注：我也尝试只使用多维数组，但我在某处读到一维数组位于 CPU 缓存中，而多维数组分散在内存中并且速度较慢。

4

1 回答 1

1

这个问题可以用另一种方式得出：你在等式中寻找 c 和 d （都是正z=c*d的） （当然是c is |a-b|and d is |x-y|）。

所以首先订购你的阵列。然后寻找解决方案，z=c*d然后找到哪个 a 和 b 为c == a - b真，x 和 y 为d == x - y真。

完成后，您将获得使方程式成立的所有值，因为 abs(ab) 与 abs(ba) 相同

于 2015-05-06T08:53:27.203 回答