Interact


私信TA

用户名:Interact

访问量:15601

签 名:

等  级
排  名 306
经  验 3207
参赛次数 0
文章发表 31
年  龄 0
在职情况 学生
学  校 哈尔滨理工大学
专  业

  自我简介:

组 合 数 学 靠 运 气 计 算 几 何 瞎 暴 力 图 论 一 顿 套 模 板 模 拟 只 会 猜 题 意 贪 心 只 能 过 样 例

TA的其他文章

解题思路:

分析:

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分

2 人评分

  评论区