计算直线的交点数-题解（C语言代码）

解题思路:

先上图：

假设我们要求x条直线可能存在的交点数，可以把x分为m条平行于轴的线，与n条混乱的线（n=[0,x]，m=x-n）
那么交点也被分为了两个部分，m部分与n部分交叉的m*n个交点，和n条直线可能的交点数

诶，这里是不是有点眼熟，本来要求x条直线可能的交点，现在变成了n条直线可能的交点，不断向下递推的话就会推到只有2条直线时可能的交点数。

那我们不如就从下往上递推，从2条直线开始。

我们需要一个初始化全为0的二维数组a，行下标表示直线的条数，列下标表示可能存在的交点数，假如n条直线可以有k个交点，就让a [n] [k] = 1;

为方便理解，我把前6行15列打印出来，若值为1，则打印列下标，也就是交点数，只不过第0列下标本就为0

参考代码：

#include <stdio.h>
int main()
{                                       // n条直线最多可有(n-1)*n/2个交点，20条直线最多190个交点
    int a[21][191] = {0};               //初始化数组全为0
    for (int i = 0; i < 21; i++)
    {
        a[i][0] = 1;                    //令列坐标为0的值都为1（全平行）
    }
    for (int x = 2; x <= 20; x++)                       //总直线数x的循环
    {
        for (int n = 0; n <= x; n++)                    //不平行部分n的循环
        {
            for (int j = 0; j <= (n - 1) * n / 2; j++)  // n的列下标循环【0，(n-1)*n/2】
            {
                if (a[n][j] == 1)                       //若存在n条直线j个交点
                {
                    a[x][(x - n) * n + j] = 1;          //则存在x条直线(x-n)*n+j个交点
                }
            }
        }
    }

    int n;
    while (scanf("%d", &n) != EOF)                      //输入n
    {
        for (int i = 0; i <= (n - 1) * n / 2; i++)      //循环列下标i【0,(n-1)*n/2】
        {
            if (a[n][i] == 1)                           //a[n][i]==1表示n条直线可以存在i个交点
            {
                printf("%d ", i);
            }
        }
        putchar('\n');
    }
    return 0;
}