pythonTip 58 切西瓜

题目描述： 小Py要吃西瓜，想知道切了n刀后，最多能切出多少块？请你们帮助下小Py.给你一个正整数n（0 < n < 10^3),你输出一个数字，代表最多能切多少块。如n=1, 输出2。

示例：

输入：n = 1

输出：2

分析:

这个问题的本质是n个平面最多可以把空间划分成多少块.我们来看如下三个问题：

1) n个点最多可以把一条直线划分成多少段，通项公式记为A(n)。 2) n条直线最多可以把平面划分多成个区域，通项公式记为B(n)。 3) n个平面最多可以把空间划分多少块，通项公式记为C(n)。

第一个问题,很简单,A(n) = n+1

第二个问题,假设平面上已有n条直线它们把平面划分成最多的区域,那么第n+1条直线下去的时候,为了保证获得最多的区域,那么要求这条直线和之前的n条直线都相交,并且新产生的交点不和之前的交点重合.显然第n+1条直线和之前的n条直线产生n个交点,这n个交点把第n+1条直线划分成A(n)段,每一段都将原来的区域一分为二,于是B(n + 1) = B(n) + A(n),将B(1) = 2,A(n) = n + 1带入很容易求得B(n) = [n(n + 1) / 2] + 1

第三个问题,同理考察第n+1个平面下去多增加了多少块.前面的n个平面都和第n+1个平面相交,在第n+1个平面上留下n条交线,这n条交线最多将第n+1个平面划分成B(n)个区域,每个区域都将原来的块一分为二,于是C(n+1) = C(n) + B(n),将C(1) = 2,B(n) = [n(n + 1) / 2] + 1带入可以求得C(n) = [(n^3 + 5n) / 6] + 1

我现在把这个公式推导一下，辅助大家理解C(n)的运算。 B(n) 如果不理解，可以搜一搜 等差数列求和。

C(1) = 2 C(2) = C(1) + B(1) C(3) = C(2) + B(2) = C(1) + B(1) + B(2) C(4) = C(3) + B(3) = C(1) + B(1) + B(2) + B(3) … C(n+1) = C(1) + B(1) + B(2) +…+B(n)

对于 B(n) = [n(n+1)/2] + 1, 变形一下： B(n) = 1/2(n² + n) + 1 好的，我们再分析一下 C(n+1): C(n+1) = C(1) + B(1) + B(2) +…+B(n) = 1/2[(1² + 2² + 3² + …+n²) + (1 + 2 + 3+….+n)] + n（这个n就是n个1相加的和）

现在来看看 1² + 2² + 3² +…+n² 和 1+2+3+….+n 。第 1 个是 数列平方和， 第2个是等差数列求和。

实际上是两个公式，需要记忆一下：

1² + 2² + 3² +…+n² = n(n+1)(2n+1)/6

1+2+3+….+n = n(n+1)/2

把这几个公式联合在一起，就有了 C(n) = [(n^3 + 5n) / 6] + 1。 有兴趣的可以自己算一下，注意，我这里是 一直加到 n, 而这题应该是加到 n-1。

小声BB： 分析一大堆，代码就一行。

代码:

1

print(int((n**3 + 5*n + 6)/6))