一、问题描述
洛谷P2789题目要求计算n条直线在平面上所有可能的交点数。这是一个经典的组合数学问题，考察的是对平行线关系的理解以及递归算法的应用能力。
二、算法核心思想
1. 平行线性质
一组平行线之间不会产生任何交点
不同组平行线之间会产生i*j个交点（i和j分别为两组平行线的数量）
2. 递归搜索策略
采用深度优先搜索(DFS)递归枚举所有可能的平行线分组方案：
将n条直线划分为若干平行线组
计算不同组之间的交点数
累加所有可能的交点数组合
三、完整代码实现
#include <iostream>#include <algorithm>// 全局变量int sum = 0; // 总交点数之和int p, n, r; // p为剩余线数，n为总直线数，r为平行线数bool A[100000] = {0}; // A[i]=1表示i个交点已存在，避免重复统计// 递归函数：计算交点数// p：剩余线数（当前待处理的线数）// m：当前已计算的交点数void plan(int p, int m) {
// 终止条件：当剩余线数为0时，记录当前交点数
if (p == 0) {
if (A[m] == 0) { // 若该交点数未出现过，计入sum
sum++;
}
A[m] = 1; // 标记为已存在
} else {
// 枚举平行线数量r（从p到1）
for (int r = p; r >= 1; r--) {
// 计算r条平行线与剩余p-r条线的交点数：r*(p-r)
int newM = m + r * (p - r);
// 递归处理剩余p-r条线
plan(p - r, newM);
}
}}int main() {
std::cin >> n; // 输入总直线数n
plan(n, 0); // 从n条线开始递归，初始交点数为0
std::cout << sum << std::endl; // 输出总交点数之和
return 0;}来源：洛谷P2789直线交点数问题终极解析：从递归到优化的完整指南
點擊查看更多內(nèi)容
為 TA 點贊
評論
評論
共同學(xué)習(xí)，寫下你的評論
評論加載中...
作者其他優(yōu)質(zhì)文章
正在加載中
感謝您的支持，我會繼續(xù)努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進(jìn)行掃碼打賞哦