Re: [問題] 平面切割
※ 引述《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)塊
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.15.208
推
12/12 09:26, , 1F
12/12 09:26, 1F
推
12/12 11:52, , 2F
12/12 11:52, 2F
討論串 (同標題文章)