锐客网

  1. 首页 > it技术 > >

暑假编程训练---G（计算直线的交点数）

问题描述
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
Input
输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.
Output
每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。
Sample Input
2
4
Sample Output
0 1
0 3 4 5 6 （表示在4条直线的情况下，可能有0，3，4，5，6个交点）


问题分析


由上图可以知道：
n = 1时有0个交点
n = 2时有0， 1个交点
n = 3时有0， 2， 3个交点
n = 4时有0， 3， 4， 5， 6个交点


从n = 4的情况出发，可以看到是在减少平行线的数量。假设有n条直线，那么这n条直线的交点数可以看作是（n-i）*i与j的和，这里（n-i）表示平行线的条数，i表示自由线的条数，j表示i条自由线的交点数。因为1条自由线与（n-i）条平行线必定有（n-i）*1个交点，这里申明下自由线与平行线不会平行，否则自由线与平行线就没有区分的必要了。那么i条自由线与平行线的交点总数就为（n-i）*i，由于i条自由线可能互相平行也可能相交，故需要加上i条自由线自身的交点数j。其实这个j与计算n条直线的交点数的方法是一样的，只不过规模缩小了。
这道题在最初分析后觉得可以用动态规划的方法来做，但细看之后，这题不涉及最优子结构的问题，所以只是单纯的递归思想而已。
M条直线的交点方案数=(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案=
(m-r)*r +r条直线之间的交点数。


#include


int main ()
{
//不浪费内存原则下，由于m的值最大为20，i的值最大为19，j的值最大为190
//再加上数组只存储0或者1，故用unsigned char类型足矣
intm, i, j, x[21][191] = {0};


//0个交点的情况是无论几条线都有的方案
for (i = 1; i <= 20; i++)
x[i][0] = 1;


for (m = 2; m <= 20; m++)//总共有20条直线
for (i = 1; i < m; i++)//i为自由直线条数，最多m-1条
for (j = 0; j <= 190; j++)//j表示交点数，最多190个
if (x[i][j] == 1)//如果i条线j个交点为真
x[m][(m - i) * i + j] = 1;
//那么m - i条平行线 * i条自由线
//的交点 + j个交点也为真


while (scanf ("%d", &m) != EOF)
{
printf ("0");
j = (m * (m - 1) / 2);
for (i = 1; i <= j; i++)
if (x[m][i])
printf (" %d", i);
printf ("\n");
}


return 0;
【暑假编程训练---G（计算直线的交点数）】}

    推荐阅读


    上一篇：终端改字体颜色，非终端背景色

    下一篇：任务|任务 6.2 云笔记 - 云端存储数据（2）