计算直线的交点数

 

主要实现思路

1. 整体流程思路：
   • 程序旨在解决给定平面上不同数量的直线（无三线共点），求出每种直线数量下所有可能的交点数量，并按要求格式输出的问题。整体通过初始化一个二维数组来存储不同直线数量与交点数量对应的存在状态，先基于简单情况（全平行时交点数为 0）进行初始化，然后利用双重嵌套循环逐步推导更多直线数量下的交点情况，最后通过循环读取输入的直线数量，查找并输出对应直线数量下所有可能的交点数量，以此来处理多组测试数据，直到文件末尾结束运行。
2. 具体步骤思路：
   • 数组初始化阶段：
     • 首先定义了一个二维数组 a[21][191]，根据 n 条直线最多可有 (n - 1) * n / 2 个交点（这里考虑 n <= 20 的上限，所以第二维大小设为 191 能涵盖所有可能交点数情况），用于存储不同直线总数（行索引表示）与交点数量（列索引表示）之间的某种状态关系，初始将数组所有元素设为 0，表示初始时都不确定是否存在相应的直线与交点数量组合情况。
     • 接着通过 for (int i = 0; i < 21; i++) { a[i][0] = 1; } 循环将每一行（对应不同直线总数情况）中列坐标为 0 的元素值都设为 1，这是因为所有直线都平行时交点数必然为 0，先把这种基础的、确定的情况在数组中标记好，方便后续基于此推导其他情况。
   • 交点情况推导阶段（动态规划思想体现）：
     • 外层 for (int x = 2; x <= 20; x++) 循环从 2 条直线开始，到 20 条直线为止，遍历不同的总直线数 x，目的是逐步计算每种直线总数下的交点情况。对于每个 x 值：
       • 中层 for (int n = 0; n <= x; n++) 循环遍历不平行部分的直线数量 n（范围从 0 到当前总直线数 x），这里 n 代表在 x 条直线里不平行的那些直线数量，通过改变 n 的值可以考虑各种不同的直线平行、相交组合方式，来推导对于总直线数 x 的交点情况。
       • 内层 for (int j = 0; j <= (n - 1) * n / 2; j++) 循环针对当前不平行直线数量 n 所能产生的交点数量范围（从 0 到 n 条直线最多能产生的交点数 (n - 1) * n / 2）进行遍历，用于检查在这种特定的 n 条不平行直线及其交点数 j 的组合下，能否推导出对于总直线数为 x 的交点情况。
       • 在这个三重循环内部，当发现对于 n 条直线存在 j 个交点（即 a[n][j] == 1）这种已知的有效交点情况组合时，就通过计算 (x - n) * n + j 来得到在 x 条直线中，若有 n 条直线按已有的 j 个交点情况排列，其余 (x - n) 条直线与这 n 条直线相交所能产生的交点数量，然后将数组 a[x][(x - n) * n + j] 的位置标记为 1，表示存在 x 条直线有这么多个交点的情况，通过这样不断利用已知的交点情况去推导更多直线数量下的交点情况，逐步填充数组 a，记录下各种可能的直线与交点数量的存在关系。
   • 结果输出阶段：
     • 定义变量 n 用于接收输入的直线数量，通过 while (scanf("%d", &n)!= EOF) 循环读取多组测试数据，只要没读到文件末尾就持续处理新输入的直线数量情况。
     • 对于每次输入的直线数量 n，通过 for (int i = 0; i <= (n - 1) * n / 2; i++) 循环遍历 n 条直线所能产生的所有可能交点数量范围，检查数组 a[n][i] 的值，如果 a[n][i] == 1，说明对于 n 条直线存在 i 个交点这种情况是存在的，就输出这个交点数量 i，并且每个交点数量之间用一个空格隔开。
     • 当输出完一组直线数量 n 对应的所有交点数量后，通过 putchar('\n'); 输出一个换行符，使每组测试实例的输出结果都换行显示，符合题目要求的输出格式，接着继续循环读取下一组输入的直线数量进行处理，直到文件末尾结束整个程序的运行。

 

#include <stdio.h>int main()
{// n条直线最多可有(n - 1) * n / 2个交点，例如20条直线最多有190个交点，这里根据题目中直线数量上限（n <= 20）确定二维数组第二维的大小为191，以涵盖所有可能的交点数量情况int a[21][191] = { 0 };// 初始化二维数组a的所有元素为0，这个数组用于存储不同直线数量下对应不同交点数量是否存在的状态，后续通过计算来更新这些状态值// 例如a[i][j]中，i表示直线的总数，j表示交点的数量，a[i][j] = 1表示存在i条直线有j个交点这种情况，初始都设为0表示都还未确定是否存在相应情况// 外层循环初始化每一行（对应不同直线总数情况）中列坐标为0的元素值都为1，也就是表示所有直线都平行时（交点数为0）的情况，先将这种基础情况标记好for (int i = 0; i < 21; i++){a[i][0] = 1;}// 外层循环开始遍历不同的总直线数x，从2条直线开始（因为1条直线不存在交点情况已经在初始化时涵盖了平行无交点即a[1][0] = 1的情况），到20条直线为止，这个循环用于逐步推导更多直线数量下的交点情况for (int x = 2; x <= 20; x++){// 中层循环遍历不平行部分的直线数量n，范围是从0到当前总直线数x，这里n表示在x条直线中不平行的那些直线数量，通过改变n的值来考虑不同的直线平行、相交组合情况for (int n = 0; n <= x; n++){// 内层循环遍历当前不平行直线数量n所能产生的交点数量范围，也就是从0到n条直线最多能产生的交点数(n - 1) * n / 2，用于检查在这种特定的不平行直线数量及其交点数组合下，能否推导出对于更多直线（总直线数为x）的交点情况for (int j = 0; j <= (n - 1) * n / 2; j++){// 如果发现对于n条直线存在j个交点这种情况（即数组中对应位置的值为1），说明找到了一种已知的有效交点情况组合if (a[n][j] == 1){// 基于这种已知情况，去更新对于总直线数为x时的交点情况。计算(x - n) * n + j得到在x条直线中，当有n条直线按已有的j个交点情况排列，其余(x - n)条直线与这n条直线相交所能产生的交点数量，将对应的数组位置标记为1，表示存在x条直线有这么多个交点的情况a[x][(x - n) * n + j] = 1;}}}}// 定义变量n，用于接收输入的直线数量，通过循环读取多组测试数据，只要没读到文件末尾（EOF）就持续处理输入的直线数量情况int n;while (scanf("%d", &n) != EOF){// 循环遍历当前输入的直线数量n所能产生的所有可能交点数量范围，也就是从0到(n - 1) * n / 2，去检查哪些交点数量情况是存在的（对应数组位置值为1）for (int i = 0; i <= (n - 1) * n / 2; i++){// 如果发现对于n条直线存在i个交点这种情况（即a[n][i] == 1），就输出这个交点数量if (a[n][i] == 1){printf("%d ", i);}}// 每组输出结束后，输出一个换行符，使每组测试实例的输出结果换行显示，更符合输出格式要求putchar('\n');}return 0;
}