6

免责声明：这不是一个家庭作业问题。我什至不上学。

#include <stdio.h>
void printIntersect(float, float, float, float);

int main(){
   int x, y, z, a;
   float slopes[] = {5, 9, 4/3.0f, 2/3.0f, 3};
   float inter[] = {3, 2, 1, 0, 5/3.0f};  

   for(x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++)
       for(y = 1; y < (sizeof(slopes) / sizeof(slopes[0])); y++)
           for(z = 0; z < sizeof(inter) / sizeof(inter[0]); z++)
                  for(a = 0; a < sizeof(inter) / sizeof(inter[0]); a++)
                      if(slopes[x] != slopes[y])
                          printIntersect(slopes[x], slopes[y], inter[z], inter[a]);

   return 0;
}

void printIntersect(float m_one, float m_two, float b_one, float b_two){
    float m_final, b_final, x_intersect;

    m_final = m_one - m_two;
    b_final = b_two - b_one;

    if(m_final < 0 && b_final < 0)
        m_final *= -1.0f, b_final *= -1.0f;

    if (b_final != 0)
        x_intersect = b_final / m_final;
    else
        x_intersect = 0;  

        printf("The intersection of y = %.2fx %c %.2f and y = %.2fx %c %.2f is x = %.2f\n",
            m_one, (b_one < 0) ? '-' : '+', b_one, m_two, (b_two < 0) ? '-' : '+', b_two, x_intersect);


    return;
}

情景：在我的一本 C 书籍中有一个我不确定的练习。我得到的问题是我有两个数组：一个代表一条线的可能斜率，另一个代表所有可能的 y 截距。目标是使用两条线的所有可能的斜率和截距组合来找到它们的交点。我要忽略平行线和重复线（考虑到它们是否不能平行，无论如何都会隐含地忽略它们，那么它们就不可能是同一条线）。

假设这是前提（此时我真的不在乎，这只是一个练习），我编写的程序使用了 4 个嵌套的 for 循环。你可以明白为什么这让我担心，但话又说回来，也许他们中的 4 个是必要的。

因为我不能有平行线，所以我从第一条线的斜率开始迭代斜率，然后遍历数组中的所有其他斜率作为第二条线的斜率。正是这种方式，我得到了所有可能的斜坡组合。

截距是不同的，因为我可以有一行相同的截距，但它们仍然不同。因此，它们之间的迭代不需要考虑重复。话虽如此，我遍历截距数组的方式应该考虑这两行中的每一个可能对。

如果线不平行，我会调用一个函数来打印 x 截距。

我的问题是，是否可以避免或至少简化这种 O(n^4) 解决方案？你对处理这样的数组有什么技巧吗？

4

3 回答 3

3

给定a斜率和b相交，您可以制作a*b线条。有a*b choose 2成对的线。这大约是a*b*a*b(它是 ( a*b*(a*b-1)/2) 的一半。鉴于没有其他信息，您似乎必须检查所有这些信息 - 所以是的，您的算法确实是O(a*a*b*b).

编辑：让我们从答案的角度来看待这个问题。给定a斜率和b相交，并a*b通过组合它们来制作线，我们将有多少个相交？为简单起见，我们假设这组斜率是不同的。

这是一个不同于询问我们给出了多少相交n线的问题，因为线的构造方式。给定一个斜率，我们创建b平行线。鉴于下一个，我们创建另一条b平行线，其中没有一条与第一组线平行。重复a次数。

在一组中，我们没有交叉点，因为它们都是平行的。

在两组之间，我们有多少个交叉点？一组中的线都不平行于另一组中的线，因此一组中的每条线将与第二组中的每条线相交一次。由于每组都有b线，因此b*b任何两组之间都会有交叉点。

在这里，我们注意到所有这些线集也共享相同的b相交集。因此，对于您与当前相交线集相交的每组额外线，您将添加(b*b - b)*c=b*c*(b-1)交叉点，其中c是已经包含的线组数，因为by 截距处的交叉点已经被考虑在内，所以我们只b*(b - 1)为已经存在的每组线添加交点。

所以我们有b^2两个集合的初始值，加上b*(b - 1)*2第三个，加上b*(b - 1)*3第四个等等，直到b*(b-1)*(a-1)添加第ath 个集合。即交叉点的数量I为：

I = b^2 + 2b(b-1) + 3b(b-1) + ... + (a-1)b(b-1)

我们可以重写b^2为b + b(b-1)：

I = b + b(b-1) + 2b(b-1) + ... + (a-1)b(b-1)

b(b-1)在最后一个a-1术语中分解出共同点：

I = b + b(b-1)[1 + 2 + ... + (a-1)]

1我们注意到从到的数字之和x是x*(x+1)/2：

                (a-1)*a 
I = b + b(b-1)  ------- 
                   2

        a*(a-1)*b*(b-1)
  = b + ---------------
               2

        (a^2 - a)(b^2 - b)
  = b + ------------------
                2

    a^2*b^2 - a^2*b - a*b^2 + a*b + 2b
  = ----------------------------------
                    2

因此，无论您使用哪种算法，您都将不得不生成许多单独的输出，这些输出确实小于a^2*b^2，但数量不多。

于 2013-07-16T02:28:53.993 回答
2

好吧，我们已经可以通过更改第二个循环的起始索引来将循环减半。

for (y = 1, ...)

至

for (y = x + 1; ...)

给予

for (x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++)
    for (y = x + 1; y < (sizeof(slopes) / sizeof(slopes[0])); y++)
        for (z = 0; z < sizeof(inter) / sizeof(inter[0]); z++)
            for (a = 0; a < sizeof(inter) / sizeof(inter[0]); a++)
                printIntersect(slopes[x], slopes[y], inter[z], inter[a]);

我还删除了相等性检查，即使正如 jxh 指出的那样，slopes可能包含重复的条目。好吧，我这样做是因为您可以删除 O(n) 中的重复项。

当然，这不会改变算法的整体时间复杂度，但它应该有助于运行时。

于 2013-07-16T02:22:10.080 回答
0

我不相信你可以摆脱 O(M 2 x Y 2 ) （M 个不同的斜率和 Y 个不同的截距），但你可以过滤你的数组，使它们首先是不同的。这允许您的程序在输入包含许多重复项的情况下运行得更快。此外，在不删除重复的 y 截距的情况下，您还可能会生成和打印重复的线交点。

因此，使用qsort您可以对输入进行排序，然后删除重复项。由于排序是 O(N x log 2 N)，它不会影响算法的整体复杂性（并且在有很多重复的情况下会加快它的速度）。使用哈希表可以更快地消除重复，但标准 C 库没有提供一个（您必须自己找到一个或实现一个）。

#define ARRAY_SZ(x) (sizeof(x)/((void *)x == &x ? sizeof(x[0]) : 0))

static int is_equal_float (float a, float b) { /*...*/ }

static int cmp_float (const void *a, const void *b) {
    float af = *(const float *)a;
    float bf = *(const float *)b;
    if (is_equal_float(af, bf)) return 0;
    return (af > bf) - (af < bf);
}

/* ... */
qsort(slopes, ARRAY_SZ(slopes), sizeof(slopes[0]), cmp_float);
qsort(inter, ARRAY_SZ(inter), sizeof(slopes[0]), cmp_float);

for (x = 0, y = 1; y < ARRAY_SZ(slopes) - 1; y++) 
    if (slopes[y] != slopes[x]) slopes[++x] slopes[y];
for (z = 0, a = 1; a < ARRAY_SZ(inter) - 1; a++) 
    if (inter[z] != inter[a]) inter[++z] slopes[a];
M = x+1;
Y = z+1;

for (x = 0; x < M - 1; x++) 
    for (y = x + 1; y < M; y++)
        for (z = 0; z < Y; z++)
            for (a = 0; a < Y; a++)
                printIntersect(slopes[x], slopes[y], inter[z], inter[a]);

我忽略了如何比较floats，但您可以参考最有效的浮动和双重比较方法，以获取有关如何以符合您的应用程序需求的方式进行比较的答案。

于 2013-07-16T02:58:08.687 回答