【计算直线的交点数】 （C语言代码）

解题思路:

容易列举出N=1,2,3的情况：
0
0，1
0，2，3
如果已知<N的情况，我们来分析加入第N条直线的情况(这里N=4)：
1.第四条与其余直线全部平行 => 无交点；
2.第四条与其中两条平行，交点数为(n-1)*1+0=3;
3.第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为：
（n-2）*2+0=4 或者 (n-2)*2+1=5
4. 第四条直线不与任何一条直线平行，交点数为：
(n-3)*3+0=3 或者 (n-3)*3+2=5 或者 (n-3)*3+3=6
即n=4时，有0个，3个，4个，5个，6个不同交点数。
从上述n=4的分析过程中，我们发现：

m条直线的交点方案数
=（m-r）条平行线与r条直线交叉的交点数 + r条直线本身的交点方案
=（m-r）*r+r条之间本身的交点方案数（1<=r<=m）

我们设置一个二维数组dot[i][j]代表i条直线有j个交点的情况，若存在等于1，否则为0；
可以推出：只要dot[j][k]=1（j条直线有k个交点是成立的），那么肯定有dot[i][(i-j)*j+k]=1；
参考代码:

#include <stdio.h>
int main()
{
	int m,n,k,dot[21][200],i,j;
	for(i=0;i<200;i++)
		dot[0][i]=0;
	for(i=1;i<=20;i++)
	{
		dot[i][0]=1;  //不管多少直线都存在0个交点的情况，即所有直线平行
		for(j=1;j<=i*(i-1)/2;j++)
			dot[i][j]=0;
		for(j=0;j<i;j++)  //(i-j)*j+k表示当有i条直线时，交点存在的值（在0到200这200个数（坐
    		for(k=0;k<=(j-1)*j/2;k++)  //标）中，当有交点值时，将交点值所在坐标的值置为1）
     			if(dot[j][k]==1)
      				dot[i][(i-j)*j+k]=1;		
	}
	while(scanf("%d",&n)!=EOF)
	{
		printf("0");
		for(i=1;i<=n*(n-1)/2;i++)
		{
			if(dot[n][i])
				printf(" %d",i);
		}
		printf("\n");
	}
	return 0;
}