解题思路:
分析:
1,
将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1和直线2最多有两个交点......直线n和其他n-1条直线最多有n-1个交点,由此得出n条直线互不平行且无三线共点的最多交点数:
max=1+2+...+(n-1)=n(n-1)/2;
2,
假设一共有n=a+b条直线
(即n条直线分成2组,分别为a条和b条)
则总的交点数= a内的交点数
+b内的交点数
+a,b之间的交点数
3,
m条直线的交点方案数
=(m-r)条平行线与r条直线交叉的交点数
+ r条直线本身的交点方案
=(m-r)*r+r条之间本身的交点方案数(0<=r<m)
m-r条平行线无交点
注意事项:
参考代码:
#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<21;i++)
{
dot[i][0]=1;
for(j=1;j<=i*(i-1)/2;j++)
{
dot[i][j]=0;
}
for(j=1;j<i;j++)
{
m=i-j;//j条直线平行,i-j条直线不平行于j条直线
for(k=0;k<=m*(m-1)/2;k++)
{
if(dot[m][k])//寻找i-j条直线内部交点种类
{
dot[i][k+j*m]=1;//k+j*m为总的交点种类
}
}
}
}
for(;scanf("%d",&n)==1;)
{
printf("0");
for(i=1;i<=n*(n-1)/2;i++)
{
if(dot[n][i])
{
printf(" %d",i);
}
}
printf("\n");
}
return 0;
}
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题8.2 (Java代码)浏览:2269 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:698 |
C二级辅导-同因查找 (C语言代码)浏览:585 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:422 |
兰顿蚂蚁 (C++代码)浏览:1091 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:743 |
字符逆序 (C语言代码)浏览:646 |
1050题解(结构体数组与结构体指针的使用)浏览:1108 |
整除问题 (C语言代码)浏览:526 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:681 |