递归算法-线的交叉点

 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

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

int g[10000];
void s(int n,int j){
    if(n>0)
      for (int i = 1; i <=n; i++)s(n-i,(n-i)*i+j);
    else g[j]=1;
}

int main(){
    int i,j,k,n;
    cin>>n;
    s(n,0);
    int maxn=n*(n-1)/2;
    for(i=0;i<=maxn;i++)
       if(g[i])cout<<i<<' ';

}

 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;
}