递归算法-线的交叉点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/****************************************************************
 * 代码作者: Alex Li
 * 创建时间: 2024-02-21 11:15:32
 * 最后修改: 2026-04-21 13:16:37
 * 文件描述: 平面上有 n 条直线，且无三线共点，问这些直线能有多少种不同交点数。
 ****************************************************************/

#include <iostream>
using namespace std;

// g[x] = true 表示：x 这个交点数是可以构造出来的
bool g[10000];

// s(n, j) n = 还有 n 条直线没有分组  j = 当前已经累计出的交点数
void s(int n, int j) {
    // 所有直线都已经分组完成，记录这种交点数
    if (n == 0) {
        g[j] = true;
        return;
    }
    // 枚举：这次取出 i 条直线，作为“同一组平行线”, 这一组中的 i 条线彼此平行，所以组内不会产生交点。
    // 但它们会与剩下的 n-i 条直线分别相交：当前组的每一条线，都会与另外 n-i 条线各交一次，
    // 因此新增交点数是 i * (n - i),然后递归处理剩下的 n-i 条直线。
    for (int i = 1; i <= n; i++) {
        s(n - i, j + (n - i) * i);
    }
}

int main() {
    int n;
    cin >> n;
    s(n, 0); // 从“还没有分组、交点数为 0”开始递归

    // n 条直线最多形成 n*(n-1)/2 个交点, 任意两条都相交时达到最大值
    int maxn = n * (n - 1) / 2;
    for (int i = 0; i <= maxn; i++) {
        if (g[i]) cout << i << ' ';
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**************************************************************** 
 * Description: 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
 * Author: Alex Li
 * Date: 2024-02-20 21:30:26
 * LastEditTime: 2024-02-20 23:25:05
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;

// 定义一个动态规划数组，dp[n][j]表示有n条线时，能产生j个交点的情况是否存在（1代表存在，0代表不存在）
//int dp[20][190];
vector<vector<bool> > dp;

int main(){
    int n,b,maxn;// n表示线的数量，b是一个用于计算的辅助变量，maxn表示n条最多的交点数 
    cin>>n;
    dp.resize(n+1);
    maxn=n*(n-1)/2;//n条线最多n*(n-1)/2个交点 
//初始化dp数组
    for (int i = 0; i <=n; i++){
        dp[i].resize(maxn+1,false);
    }
    

    dp[0][0]=1; // 初始化，0条线时0个交点的情况显然存在
    dp[1][0]=1; // 初始化，1条线时0个交点的情况也显然存在
    for(int i=2;i<=n;i++){ // 从2条线开始，逐步计算到n条线的情况
        dp[i][0]=1;  // 初始化，任何数量的线都有0个交点的情况（即它们都是平行）
        for (int j = 1; j <=i; j++){// 在i条直线中有j条直线是平行的
            for (int k = 0; k <=i*(i-1)/2; k++){// 遍历所有可能的交点数
                b=i-j;  //b为i条直线减去j条平行线
                if(dp[b][k]==1)  //// 如果存在b条线产生k个交点的情况
                    dp[i][b*j+k]=1; //i条直线的交点方案数 = b*j+b条之间本身的交点方案数（1<=b<=i）
            }
            
        }
        
    }

    for (int i = 0; i <=maxn; i++){
        if(dp[n][i]==1)cout<<i<<" ";
    }

   return 0;
}