文档介绍：2018/5/3
1
ACM 程序设计
计算机学院刘春英
2018/5/3
2
今天,
你了吗?
AC
2018/5/3
3
每周一星(3):
05059127陈谦益
2018/5/3
4
第四讲
动态规划(1) (Dynamic programming)
2018/5/3
5
先热身一下——
2018/5/3
6
(1466)计算直线的交点数
问题描述:
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
输入:n(n<=20)
输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。
样例输入
4
样例输出
0 3 4 5 6
2018/5/3
7
初步分析:
我们知道:
n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,
但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?
2018/5/3
8
思考2分钟:如何解决?
2018/5/3
9
容易列举出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个不同交点数。
2018/5/3
10
从上述n=4的分析过程中,我们发现:
m条直线的交点方案数
=(m-r)条平行线与r条直线交叉的交点数
+ r条直线本身的交点方案
=(m-r)*r+r条之间本身的交点方案数(1<=r<=m)