文档介绍：该【动态规划】是由【相惜】上传分享，文档一共【37】页，该文档可以免费在线阅读，需要了解更多关于【动态规划】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。ACM程序设计
计算机学院刘春英
*
1
精选ppt
今天,
你了吗?
AC
Date
2
精选ppt
每周一星(3):
05059127陈谦益
Date
3
精选ppt
第四讲
动态规划(1)(Dynamicprogramming)
Date
4
精选ppt
先热身一下——
Date
5
精选ppt
(1466)计算直线的交点数
问题描述:
平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。
输入:n(n<=20)
输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。
样例输入
4
样例输出
03456
Date
6
精选ppt
初步分析:
我们知道:

n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,
但本题不这么简单,因为问题问的是:这些直线有多少种不同的交点数?
Date
7
精选ppt
思考2分钟:如何解决?
Date
8
精选ppt
容易列举出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个不同交点数。
Date
9
精选ppt
从上述n=4的分析过程中,我们发现:
m条直线的交点方案数
=(m-r)条平行线与r条直线交叉的交点数
+r条直线本身的交点方案
=(m-r)*r+r条之间本身的交点方案数(1<=r<=m)
Date
10
精选ppt