几何分割问题

    最近做了一些几何分割的问题,觉得需要总结一下。

单点分割直线

    这是最简单的,但是也是所有题目的基础,结论很显然,n个点可以把线段分为n+1个小段,画画图就知道。记其为

f1(n)=n+1

直线分割平面

    然后是直线分割平面的问题,我们知道,当新增一条直线时,当其与之前所有直线相交时,一定可以新增最多的小块,假设之前为n-1条线,那么新增的就是n个区域,为了下面的说明,我们换一种思路思考,问题可以转化为,新加入的直线可以被之前的直线与该直线相交形成的单点分为几段,那么用回单点分割线段的结论,如记n条直线最多分平面为f2(n)块,则:

f2(n)=f2(n-1)+f1(n-1)=n*(n+1)/2+1

折线分割平面

    根据直线分平面可知,由交点决定了射线和线段的条数,进而决定了新增的区域数,则折线的两边的线段要和n-1条折线的边,即2*(n-1)条线段相交。那么新增的线段数为4*(n-1),射线数为2。但要注意的是,折线本身相邻的两线段只能增加一个区域。所以由数学归纳法可得公式:

f3(n)=2n*n-n+1

平面分割空间

    这种题目就是要用之前在直线分割平面中说到的第二种思考方法了,每次新加入的平面要想产生最多新的区域,就要与之前所有平面相交,且与之前所有平面交线在该平面上形成最多的区域,那么,求新增的区域就回归到直线分割平面的问题了,所以公式就是:

f4(n)=f4(n-1)+f2(n-1)=(n*n*n+5n)/6+1

空间分割时空

    最后还是这种思考方法,可以解决这道看似不可能的问题,当平面分割空间时,或许我们还可以用画图来解决问题,那么时空呢,我想,基本在目前的科技条件下还是无法完成这点的绘图的,所以沿用之前的思考方法,当新加入一个空间时,要与之前所有的空间相交,而且使其与之前的空间的交平面在新加入的空间上分割出最多的区域,然后,就回归到上一个问题,公式就不化简了:

f5(n)=f5(n-1)+f4(n-1)

    当然由以上的公式,你可能可以得出一个规律:

n个点最多把直线分成C(n,0)+C(n,1)份; 

n条直线最多把平面分成C(n,0)+C(n,1)+C(n,2)份;

n个平面最多把空间分成C(n,0)+C(n,1)+C(n,2)+C(n,3)份; 

n个空间最多把“时空”分成C(n,0)+C(n,1)+C(n,2)+C(n,3)+C(n,4)份……

所以说,总结归纳很重要。

 

总结:对于一些难解的问题,可以先从一些简单的基本问题着手,

 

然后逐步扩展,最后解决一些复杂的问题。                                    

 

几何分割问题

上一篇:MOSS 2013安装图文教程


下一篇:iptables实战系列:通过NAT转发实现私网对外发布信息