递推寻解

递推求解

去参加UC的笔试出现了一道题目，没有做出来，郁闷就跟朋友聊聊，没想到最后还是跑回到算法那里去~~~+_+

问题：10个平面最多可以将空间分割几部分

 

 

解法一：递推思想
设用n个平面去切割空间的时候是f(n)块。
 首先，理解一下，当变为二维的时候，也就是一个平面被N条边最多可以分为几部分:p(n)=1/2[n*(n+1)]+1,这个比较好理解，原理：第N条边可以将p(n)中的n-1条直线相交，从而增加了n部分，于是可推到而出。
现在，当变为三维时，n-1个平面后，放上第n个平面，那么第n个平面上最多有n-1条线，这n-1条线能把第n个平面分为多少部分，那么空间就多了多少部分。
于是，可得推导式：
f(n)=f(n-1)+1/2[n*(n+1)]+1，于是可得f(n)=(n^3+5n+6)/2

 

 

 

解法二：数学方程求解
由上面所知，一个平面被N条边最多可以分为几部分:p(n)=1/2[n*(n+1)]+1，可以推测出二维的分割n的最高次幂为2，当为一维的时候，也就是点分割线的时候，n的最高次幂为1,由此可以推测，当为三维的时候，n的次幂是3；
于是可以设n个平面可以将空间分割为f(n)部分，f(n)=a*n^3+b*n^2+c*n+d,
而且知f(0)=1; f(1)=2; f(2)=4; f(3)=8代入，
可求得：f(n)=(n^3+5n+6)/2