2847人阅读
计算直线的交点数
Problem Description
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
将n条直线排成一个序列，直线2和直线1最多只有一个交点，直线3和直线1，2最多有两个交点,……，直线n 和其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线共点的最多交点数：
Max = 1 +2 +……+（n-1）=n(n-1)/2;
这些直线有多少种不同的交点数
&当n = 1， 2， 3时情况很容易分析。当n = 4 时，我们可以按如下分类方法，逐步计算。
&1. 四条直线全部平行，无交点。
&2. 其中三条平行，交点数: 3*(n-3)+0 = 3；
&3. 其中两条平行，而另外两条直线的交点既可能平行也可能相交，因此交点数据分别为：
& &2*(n-2) + 0 = 4
& &2*(n-2) + 1 = 5
4. 四条直线互不平行， 交点数为1*(n-1) + {3条直线的相交情况}：
&& 1*(n-1)+0=3&
&& 1*(n-1)+2=5&
&& 1*(n-1)+3=6
即n=4时，有0, 3, 4, 5, 6个不同的交点数.所以有5种可能。
从上述n=4的分析过程中，发现：
m条直线的交点数=r条平行线与m-r条直线交叉的交点数+ m-r条直线本身的交点数 =r*(m-r) + m-r条直线之间的交点数。(1&=r&=m)
{m条直线的交点数集合} = U {& r条平行线与m-r条直线交叉的交点数 + {m-r条直线本身的交点数集合}& } =& U {& r*(m-r) + {m-r条直线之间的交点数集合}& }。(1&=r&=m)
&注意：数和集合相加 = 数和集合中每个元素相加组成的新集合。
&如何编写程序？
&程序框架如下：
//Ui表示i条直线的交点数集合
初始化U0= {0}, U1= {0}
For n = 2 to N
&& Un = {}&&&&&&&&&&&&&&&&&&&&&&&&&&& //初始化Un
&& For i = 1 to n&&&&&& //i表示平行线个数
&&&&&&&&&&&&&&&&&& Un =Un &U &{ i*(n-i) + Un-i}&&&&&&& //并运算
&注意：数和集合相加 = 数和集合中每个元素相加组成的新集合。
&用C++代码实现，我们可以用set集合，最简单的方法是用数组表示交点数集合。
二维数组 p[i][j] 表示i条直线，j个交点数是否存在。存在值为1，不存在值为0.
#include &stdio.h&
int main()
&int p[21][200], //200为交点数的上限，交点数为1+2+3+…(n-1)
&memset(p, 0, sizeof(p));
&for(int i=0; i&21; i++)
&p[i][0]=1; //不管多少直线都存在0个交点的情况，即所有直线平行
&for(int n=2; n&21; n++) //动态规划p[i][j]表示i条直线，交点数为j.当& p[i][j]=1,则表示i条直线中，存在交点数为j的情况
&&&& for(int i=1; i & i++) //n条直线平行的情况已经考虑了，无需重复
&&&& &&& &for(int j=0; j&200; j++)
&&&&&&&& &&& &{
&&&&&&&&&&& &&& &if(p[n-i][j]==1)
&&&&&&&&&&&&&&& &&& p[n][j+i*(n-i)]=1;&&
&&&&&&&&&&&&& }
&while (scanf(&%d&, &n) != EOF)
&& &for (j=0; j &= n*(n-1)/2; j++)&& //n*(n-1)/2能形成的最大交点数
&&&& if (f[n][j])
&&&&&& & &&& printf(&%d &,j);
&&&& printf(&\n&);
&& return 0;
这个是转载别人的，感觉好强大，我一直在想：我怎么当我知道i(n-i)条直线平行时，我又怎么可以把n-i条剩余的直线的所有可能加上去呢。加上去后我怎么存储呢？
而这个程序他运用了逆向的思想，从头到尾做出了所有可能的表格 。要不然怎么叫做规划呢？而且还是动态的？
首先他用i行表示多少条线，用数组元素为1表示该元素的j为可能存在的交点个数。
然后从数组2行开始往后规划，规划的方法是：i条线平行。n-i条线得出行数存在的交点情况加上i(n-i)，然后在相应得到交点数赋值为1
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：14233次
排名：千里之外
原创：15篇
转载：11篇
(2)(4)(2)(9)(9)HDU1466 计算直线的交点数 [DP]+[经典题]
计算直线的交点数
Time Limit:
MS (/Others) Memory Limit:
K (Java/Others) Total Submission(s): 7923 Accepted Submission(s): 3529
Problem Description 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
Input 输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n&=20）,n表示直线的数量.
Output 每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。
Sample Input
Sample Output
**n条直线时，交点数情况存到arr[n]中。分成两组，选任意一条A作为代表，与A平行的都在A组，其他的放到B组，
**则交点数为a * b + arr[b];
bool arr[22][200];
//标记法某种程度上具备排序的性质
int main(){
arr[0][0] = arr[1][0] = 1;
for(int i = 2; i & 21; ++i){
arr[i][0] = 1; //0一定有，有则标记
for(int j = 1; j & ++j){
a = b = i -
for(int k = 0; k &= (b-1) * b / 2; ++k)
if(arr[b][k]) arr[i][a * b + k] = 1;
while(scanf(&%d&, &n) == 1){
for(int i = 0; i &= (n-1) * n / 2; ++i)
if(i == 0) printf(&%d&, i);
else if(arr[n][i]) printf(& %d&, i);
printf(&\n&);
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'Hi~亲，欢迎来到题谷网,新用户注册7天内每天完成登录送积分一个，7天后赠积分33个，购买课程服务可抵相同金额现金哦~
意见详细错误描述：
教师讲解错误
错误详细描述：
当前位置：>>>
我们知道，两条直线相交，一共有两对对顶角，那么三条直线、四条直线、甚至是n条直线相交于一点或两两相交，有几组对顶角呢？为了解决这一问题，请思考如下的问题：(1)如图，算一算图①、图②中各个图形的对顶角的组数． (2)填写下表：
最多交点个数
6＝1＋2＋3
________＝________
由上可发现结论1∶n条直线两两相交，最多有________个交点．(3)由于对顶角是两条直线相交而构成的，每个交点有两组对顶角，因此可知对顶角的组数为直线交点个数的2倍，结合(1)、(2)可发现结论2：n条直线相交于一点，共有________组对顶角．
主讲：赵秀辉
【思路分析】
根据图表的规律：n条直线两两相交，最多有1+2+3+4+……+(n-1); 每个交点有两组对顶角，因此可知对顶角的组数为直线交点个数的2倍.
【解析过程】
(2)1+2+3+4+……+(n-1)=;(3)2×=n(n-1)
(1)6,12.;(2) ;(3) n(n-1)
找规律的题目从特殊到一般，注意规律的总结.
给视频打分
招商电话：010-
地址：北京市西城区新街口外大街28号A座4层409
扫一扫有惊喜！
COPYRIGHT (C)
INC. ALL RIGHTS RESERVED. 题谷教育 版权所有
京ICP备号 京公网安备我们知道相交的两直线的交点个数是1，记两平行直线的交点个数是0；这样平面内的三条平行线它们的交点个数就是0，经过同一点的三直线它们的交点个数就是1；依次类推，…（1）请你画图说明同一平面内的五条直线最多有几个交点？（2）平面内的五条直线可以有4个交点吗？如果有，请你画出符合条件的所有图形；如果没有，请说明理由；（3）在平面内画出10条直线，使交点数恰好是31．
（1）一平面内的五条直线最多有10个交点．画图即可；（2）平面内的五条直线可以有4个交点，有3种不同的情形；（3）可使5条直线平行，另3条直线平行且都与这5条相交，再有2条直线平行且都与这5条相交，且3条和2条也有相交．
解：（1）如下图，最多有10个交点．（2）可以有4个交点，有3种不同的情形，如下图示．（3）如下图所示．}