首页 > 代码库 > 折线分割平面

折线分割平面

2024-07-30 21:38:42   223人阅读

直线分割：

直线数和平面块数的关系
当没有任何直线时，平面块数记为1。使用->表示直线数和能够产生最多的平面块数的关系：
0 –> 1
1 –> 2
2 –> 4
3 –> 7
4 –> 11
我们对上述平面块数做一个分解：
0 –> 1  = 1
1 –> 2  = 1 + 1
2 –> 4  = 1 + 1 +２
3 –> 7  = 1 + 1 + 2 + 3
4 –> 11 = 1 + 1 + 2 + 3 + 4

直线数为0时，平面分割的最多块数为1；
直线数为1时，原有直线数为0，添加第一条直线后，增加1块，最多块数为1 + 1 = 2；
直线数为2时，原有直线数为1，添加第二条直线后，增加2块，最多块数为1 + 1 + 2 = 4；
直线数为3时，原有直线数为2，添加第三条直线后，增加3块，最多块数为1 + 1 + 2 + 3 = 7；
直线数为4时，原有直线数为3，添加第四条直线后，增加4块，最多块数为1 + 1 + 2 + 3 + 4 = 11；
以此类推，得到最多块数与直线数的关系式为：
Sn = 1 + (1 + 2 + 3 + … + n)  (n为直线数）
使用等差数列求和公式将括号内部分化简得：
Sn = 1+ n(n + 1) / 2=（n*n+n+2）/2

熟悉了线分割平面，现在，我们再来看看，每次增加的不是一条直线，而是两条相互平行的线.

当第N次添加时，前面已经有2N-2条直线了，按我们上面讨论的知道，第N次添加时，第2N-1条直线和第2N条直线各能增加2N-1个平面。
所以第N次添加增加的面数是2[2n-1] = 4n - 2 个。因此，总面数应该是1 + 4n(n+1)/2 - 2n = 2n2 + 1

折线分割：

现在我们再来看如果把每次加进来的平行边让它们一头相交，



我们看到，平面1、3已经合为一个面，既少了一个面。因此，每当一组平行线相交后，就会减少一个面。
因此，本题所要求的折线分割平面，自然就是上面求的的平行线分割平面数减去N。（N组平行线）
即2n2 - n + 1 

折线分割平面最大为：2n2 - n + 1 


实现：
int n;
    cin>>n;
    cout<<2*n*n-n+1<<endl;


折线分割平面


联系
我们