当前位置:Gxlcms > Python > 算法,西瓜切十刀,最多是多少块?

算法,西瓜切十刀,最多是多少块?

时间:2021-07-01 10:21:17 帮助过:131人阅读

刚出道面试过一到算法题目,
一个西瓜,保持形状不变,切10刀最多切多少块!

回复内容:

帮你搜到一个答案:
一个西瓜切100刀最多能分成多少块?说明为什么.

你这个问题的本质是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
提示:利用以下求和公式:
1+2+...+n=n(n+1)/2
1^2+2^2+...+n^2=n(n+1)(2n+1)/6
将n=100带入C(n)得C(100)=166751 如果刀是直的,且是10维空间的西瓜,答案是1024。三维空间也是么? 用刀背切,块数比较多,不过不容易算。。 那些说1024的,都是在中途动了西瓜,或者是十维空间的西瓜。
在不移动西瓜的情况下,第四刀怎么着也切不出16块来。 不懂算法,
但我感觉,第n刀如果与前n-1刀全部相交,这应该是最多块的情况,
1+(1/2)(n(n+1))
56
好吧,这似乎是二维的西瓜, 10刀在各个维度下最多能切出的块数:
1维:11
2维:56
3维:176
4维:386
5维:638
6维:848
7维:968
8维:1013
9维:1023
10+维:1024
一般地:
n刀在k维空间下最多可以切出的块数为n次二项式展开的前k+1项系数和(没有的项补0)。
比如3刀在二维空间下最多切出1+3+3=7块。 我的第一反应是用『贪心算法』,不知道对不对。 二的十次幂
1024 用刀面一拍就完美了,
好吧说笑,接下来是正解。
答主的题目意思不太清楚,没有限定是否可以在切的过程中移动西瓜
1.可以。
那答案前面各路大仙已经说了,10^10=1024

2.不可以。
这个时候就需要小学奥数发功了(小学入坑,考过杭州市34,但对于各路大神来说太差了)
0刀:1块
1刀:2块(废话)
2刀:4块
3刀:8块(切成二阶魔方的形状)
看到这而是不是很惊奇,因为似乎恰好事2^n?,这是因为3刀之内可以保证和每一个之前的平面切出的小块再切成两块
4刀:15块(可以自己试试,但是可以发现就是切不出16块)
这就是因为不能把之前的每个小块都一分为二。那么数列出来了
1,2,4,8,15
咳咳,我们来做个差
1,2,4,7
诶,这个好像也没有什么规律咋办?继续做差
1,2,3没错,这个数列就很完美了,差是1.

那么这样可以递推了
1,2,4,8,15,26,42,64,93,130,176
1,2,4,7,11,16,22,29,37,46,56,67
1,2,3,4,5,6,7,8,9,10
1,1,1,1,1,1,1,1,1,1
(下面一列作为上面一列的公差,并且依次向上)[经知友提醒,把最后一列1111111补上去了]
所以答案应该是176 根据这个问题的高票回答@黄哥 我写了Python的算法实现。
代码如下:
def A(n):
    return n+1

def B(n):
    if n==1:
        return 2
    return B(n-1)+A(n-1)

def C(n):
    if n==1:
        return 2
    return B(n-1)+C(n-1)

print str(C(10))

人气教程排行