1003 - 切義大利餅問題

bac

簡單來說
就是問n條線最多能把一個平面切成幾塊

什麼形狀並不重要
不管你是切餅切紙切螢幕(?
只要它是凸多邊形
基本上都和切無限延伸的平面沒什麼差別

或許你已經知道這是一個簡單的方程式
然後代前幾項進去就能算出來，那問題就輕鬆解決了~

如果不知道的話呢~
我想平面應該還能直觀的下去分析它吧

如果一條線切下去和別的線平行，或是經過其它交點，必然不會是最多的
也就是說~
要讓交點最多~
然後第n+1條線最多只能和第n條線相交
然後然後~

把一個部分切成兩塊的時候
切開的這條線一定會經過兩條不同的直線(兩個交點)
像這樣

可得知兩兩交點之間會+1塊

那最邊緣呢?

兩種想法
一個是當做無限延伸的平面
反正兩邊切出去的一定各+1塊
或者把邊界算進來
依照兩交點間+1塊

反正算起來都一樣

所以可以輕鬆獲得一個遞迴式
f(n+1) = f(n) + n+1
或
f(n) = f(n-1) + n

然後直接遞迴 or 換成一般式

至於怎麼換一般式嘛~~~
基於對數字的敏感度直覺的感受到+1+2+3....好像和 (1/2)n^2 有關
然後快速得到公式
or
慢慢換~慢慢代~慢慢算~
or
憑著數學課學到的東西~


這題我想CODE就不貼了~