每天一篇好文章网站,外贸推广的几种方式以及效果排行,网站建设相关的工作,微商代理怎么做主要实现思路
整体流程思路#xff1a; 程序旨在解决给定平面上不同数量的直线#xff08;无三线共点#xff09;#xff0c;求出每种直线数量下所有可能的交点数量#xff0c;并按要求格式输出的问题。整体通过初始化一个二维数组来存储不同直线数量与交点数量对应的存在… 主要实现思路
整体流程思路 程序旨在解决给定平面上不同数量的直线无三线共点求出每种直线数量下所有可能的交点数量并按要求格式输出的问题。整体通过初始化一个二维数组来存储不同直线数量与交点数量对应的存在状态先基于简单情况全平行时交点数为 0进行初始化然后利用双重嵌套循环逐步推导更多直线数量下的交点情况最后通过循环读取输入的直线数量查找并输出对应直线数量下所有可能的交点数量以此来处理多组测试数据直到文件末尾结束运行。具体步骤思路 数组初始化阶段 首先定义了一个二维数组 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.hint 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去检查哪些交点数量情况是存在的对应数组位置值为1for (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;
}
