sum=n(n-1)/2 (n是直线的个数)
 
视频讲解

递归算法的简单运用 
 
// n条直线最多几个交点
/*******************
减而治之，把第n条直线单独拿出来
1.定义问题，考虑几个参数
	f(n)表示n条直线 最多交点数
2.找相似性(试探)
	f(n) = f(n-1) + (n-1)
3.确定递归出口(特殊情况)
	f(1) = 0 
******************/
#include<bits/stdc++.h>
using namespace std;
int f(int n);
int main(){
	int n;
	while(cin>>n){
		cout<<f(n)<<endl;
	}
	return 0;
}
int f(int n){
	if(n==1)
		return 0;
	else return f(n - 1) + (n - 1);
}
 
 

import java.util.Scanner;

//2. 计算n条直线最多能把平面分成多少部分？ n >= 1
//一条:2
//两条:2 + 2 = 4;
//三条:4 + 3 = 7;
//四条:7 + 4 = 11;
//...
public class Test02 {
    public static void main(String[] args) {
        System.out.println("请输入直线数n:");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int part = cut(n);
        System.out.println(n + "条直线最多能把平面分成" + part + "份");
    }
    private static int cut(int n) {
        int part = 0;
        if (n == 1) {
            part = 2;
        } else {
            part = cut(n - 1) + n;
        }
        return part;
    }
}

看了一道水题，发现这个两个问题值得记录一下。
 

 
 

 
 
一，直线分割平面：
 

 
 

 
 
首先考虑 n条直线最多把平面分成an部分
 
 
于是a0=1 a1=2 a2=4
 
 
对于已经有n条直线 将平面分成了最多的an块
 
 
那么加一条直线 他最多与前n条直线有n个交点 于是被它穿过的区域都被一分为二 那么增加的区域数就是穿过的区域
 
数 也就是这条直线自身被分成的段数 就是n+1 故 a(n+1) = an+n+1
 
 
an = n+(n-1)+...+2+a1 = n(n+1)/2 +1
 
 

 
 

 
 
二，平面分割空间：
 

 
 

 
 
设n个平面最多把空间分成bn个部分
 
 
于是b0=1 b1=2 b2=4
 
 
对于已经有n个平面 将空间分成了最多的bn块
 
 
那么加入一个平面 它最多与每个平面相交 在它的上面就会得到至多n条交线 
 
 
同时被它穿过的空间区域也被它一分为二 那么增加的区域数仍旧是它穿过的区域数 也就是这个平面自身被直线分割
 
成的块数 就是an
 
 
于是b(n+1)=bn+an
 
 
bn=a(n-1)+b(n-1)=...=a(n-1)+a(n-2)+...+a1+b1
 
 
=(n-1)n/2 +(n-2)(n-1)/2+...+1*(1+1)/2+n+2
 
 
=求和[1方到(n-1)方]/2 + 求和[1到(n-1)]/2 +n+1
 
 
=n(n-1)(2n-1)/12 +n(n-1)/4 +n+1
 
 
=n(n+1)(n-1)/6 +n+1
 
 
=(n^3+5n+6)/6
 

 
 

 
 
三，直线分割空间：
 

 
 
由上所述，直接可以得到公式： an = (n*(n+1)/2+1) * (n^3+5n+6)/6
 
                                                        = (n^5+n^4+7*n^3+11*n^2+16*n)/12+1
 

 
 
四，折线分割平面：
 

 
 
 根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，即2*（n-1）条线段相交。那么新增的线段数为4*（n-1），射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。
 
 

 
 
 故：f(n)=f(n-1)+4(n-1)+2-1
 
                       =f(n-1)+4(n-1)+1
 
                      =f(n-2)+4(n-2)+4(n-1)+2
 
                      ……
 
                      =f(1)+4+4*2+……+4(n-1)+(n-1)   
 
                      =2n^2-n+1