原题是这样的:

Description
一个蛋糕切N刀,最多能得到多少块?切的过程中不能改变任意一块蛋糕的位置。
Sample Input
2
3
4
Sample Output
4
8
15

不会所以去搜了一下,结果发现这是个挺有意思的问题。可以递归也可以直接套公式。。。

这个问题实际上转换成n个平面最多可以把空间分成多少块。
首先,第n个平面必须要与前面的任何一个平面都相交,才可能出现最大分割空间。
其次,假设与前n-1个平面有相交,于是第n个平面上出现了n-1条直线,要让这n-1条直线把平面分割的最多,这个是可以算出来的,n-1条最多分成 n(n-1)/2+1 块区域,可以这么理解,对于第n个平面,被分割出来的每一个小平面,都把以前的空间分成了2部分。
于是 f(n) = f(n-1) + n(n-1)+2;
f(n) = (n*n*n+5*n+6)/6

评论

电子邮件地址不会被公开。 必填项已用*标注

你可以使用以下 HTML 标签和属性:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">