Posts pythonTip 58 切西瓜
Post
Cancel

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(n2 + n) + 1 好的,我们再分析一下 C(n+1): C(n+1) = C(1) + B(1) + B(2) +…+B(n) = 1/2[(12 + 22 + 32 + …+n2) + (1 + 2 + 3+….+n)] + n(这个n就是n个1相加的和)

现在来看看 12 + 22 + 32 +…+n21+2+3+….+n 。第 1 个是 数列平方和, 第2个是等差数列求和。

实际上是两个公式,需要记忆一下:

12 + 22 + 32 +…+n2 = n(n+1)(2n+1)/6

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

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

\[C[n] = 1/2[n(n-1)(2n-1)/6 + n(n-1)/2] + n-1 + 2 = 1/2[(2n^3 - 2n)/6] + n+1 = (n^3+5n)/6 + 1\]

小声BB: 分析一大堆,代码就一行。

代码:

1
print(int((n**3 + 5*n + 6)/6))
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 57 那些年我们集过的卡片

pythonTip 59 换位置

Trending Tags