A41026. 计算直线的交点数
填空题
较难
知识点
题目描述
计算直线的交点数
题目描述
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
输入格式
输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.
输出格式
每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。
样例输入
2
3
样例输出
0 1
0 2 3
参考答案
#include <stdio.h>
int main()
{ // n条直线最多可有(n-1)*n/2个交点，20条直线最多190个交点
int a[21][191] = {0}; //初始化数组全为0
for (int i = 0; i < 21; i++)
{
a[i][0] = 1; //令列坐标为0的值都为1（全平行）
}
for (int x = 2; x <= 20; x++) //总直线数x的循环
{
for (int n = 0; n <= x; n++) //不平行部分n的循环
{
for (int j = 0; j <= (n - 1) * n / 2; j++) // n的列下标循环【0，(n-1)*n/2】
{
if (a[n][j] == 1) //若存在n条直线j个交点
{
a[x][(x - n) * n + j] = 1; //则存在x条直线(x-n)*n+j个交点
}
}
}
}
int n;
while (scanf("%d", &n) != EOF) //输入n
{
for (int i = 0; i <= (n - 1) * n / 2; i++) //循环列下标i【0,(n-1)*n/2】
{
if (a[n][i] == 1) //a[n][i]==1表示n条直线可以存在i个交点
{
printf("%d ", i);
}
}
putchar('\n');
}
return 0;
}
上一题
下一题