演算法，西瓜切十刀，最多是多少塊？

12-20

剛出道面試過一到演算法題目，
一個西瓜，保持形狀不變，切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

那些說1024的，都是在中途動了西瓜，或者是十維空間的西瓜。
在不移動西瓜的情況下，第四刀怎麼著也切不出16塊來。

用刀面一拍就完美了，
好吧說笑，接下來是正解。
答主的題目意思不太清楚，沒有限定是否可以在切的過程中移動西瓜
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

用刀背切，塊數比較多，不過不容易算。。

我的第一反應是用『貪心演算法』，不知道對不對。

不懂演算法，
但我感覺，第n刀如果與前n-1刀全部相交，這應該是最多塊的情況，
1+(1/2)(n(n+1))
56
好吧，這似乎是二維的西瓜，

二的十次冪
1024

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塊。

2^10吧，理想情況下，刀是直的，一切兩半。

根據這個問題的高票回答@黃哥我寫了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))

運行結果：

看你用什麼刀

如果刀是直的，且是10維空間的西瓜，答案是1024。三維空間也是么？

難道不是1～2，2～4，3～6，4～8，，，9～18塊，最後橫一刀，36塊嗎？

1024

如果切了可以摞起來繼續切，那就是2^10=1024
如果只能在一個平面上切，就是三角數+1，也就是(10+1)*10／2+1=56

每刀都是直線么

我哪知道你多少塊買的

我就想知道刀有多長，西瓜的半徑又是多少。。。

和編程關係不大啊，你高中學排列組合沒做過這題？

切球，切空間什麼的。

直著切還是彎著切。彎著切。兩刀就可以切成渣

以前有個挺有名的梗，叫三刀八塊，2的三次，每一刀把已有的平分，所以可能是2的10次，1024