Re: [問題] 平面切割
※ 引述《cksc10 (cksc10)》之銘言：
: ※ 引述《kunlin999 (max)》之銘言：
: : 傳統中有一個著名的問題是，
: : 用n條直線切割一平面，最多可得到幾塊區域？
: : 答案是C_0^n+C_1^n+C_2^n
: : 其中C_m^n就是n!/(m!(n-m)!)
: : 我們可以換一個角度來思考這個問題，
: : 就是如果要得到m塊區域，最少需要幾條直線？
: : 事實上，所有的m都會被切出，而且只要m-1條
: : （且m-1條平行且不相交的直線即可）
: : 可是m-1並非最小的狀況，
: : 因此如何知道最小的值是我感興趣的問題，
: : 當然我們無須考慮直線重合！！！！
: : 問題一開始可能是要瞭解一些基本的狀況，
: : 如：
: : case 1: 1塊區域，不需任何直線。
: : case 2: 2塊區域，需要1條直線。
: : case 3: 3塊區域，需要2條平行且不相交的直線。
: : case 4: 4塊區域，需要3條平行且不相交的直線，
: : 或是2條不平行的直線。
: : .........
: : 隨著塊數增加，討論的狀況越來越複雜，
: : 我希望至少討論到16塊區域，瞭解其所有狀況，
: : 看看是否能得到一個一般化的結果。
: : 請大家幫忙想想看，
: : 有空的話，請幫我增加case的結果，
: : 如：
: : case 5: 5塊區域，需要4條平行且不相交的直線。
: : case 6: 6塊區域，需要5條平行且不相交的直線，
: : 或2條平行且不相交，再加上1條與他們都不平行的線，
: : 或3條相交於同一點的直線。
: 我是則旻，明年的新生
: 就這個題目來看，正常m條線在中間不相交則有m+1塊區域
: 我發現如果線跟線之間在中間有相交一點就多一塊區域
: 例如：
: case 1: 沒有直線==>1塊區域
: case 2: 1條直線，不會有相交==>2塊區域
: case 3: 2條直線且不相交==>2+1=3塊區域
: 相交一點==>2+1+1=4塊區域
: case 4: 3條直線且不相交==>3+1=4塊區域
: 相交一點==>3+1+1=5塊區域
: 相交兩點==>3+1+2=6塊區域
: 相交三點==>3+1+3=7塊區域
: 同理，4條直線最多11塊
: 結論：
: n條直線最多交點數為C(n,2)，即組合n條線中任2條都有交點
: 所以n條直線，最多之區域為n+1+C(n,2)塊
學長你說的反過來看就可以了吧？
已經知道n條最多有幾塊，反過來就可以知到m塊的話所需要的最少條數
進而推導是那一種相交的狀況
例：8塊：就會知道是在4條然後判斷所需要的交點數應該就可以推算是那一種狀況了
達到8，就是5+3，所以是有三個相交點的狀況
16塊：就先判斷5條時最多是6+C(5,2)=16條
即為任兩條都相交，共相交10點的狀況
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.15.208
討論串 (同標題文章)