Re: [其他] 對平面上的點分群
※ 引述《Darkflame (遙遠的距離)》之銘言：
: 大家好，想請教一下基本的machine learning問題~
: 問題描述:
: 假設平面上有四個點ABCD，想要將這四個點分成兩群，可是分群的方法只能用直線
: 決定，請問在平面上任意選四點的情況下，最多可以形成的群數是多少?
: Ans:最好的情況如圖:
: A D
: B C
: 注意在圖上不能將AC分成一群，因為沒有辦法用一條直線分成AC一群及BD一群
: ,所以用直線可以分群的方法有
: ( ,ABCD) (線在ABCD之外)
: (A ,BCD ) (將A分成一群，剩下的分成一群)
: (B ,ACD )
: (C ,ABD )
: (D ,ABC )
: (AB ,CD ) (AB與CD之間的垂直線)
: (BC ,AD ) (AD與BC之間的水平線)
: 共七種
: 那現在的問題是:
: 請問如果在平面上選定任意n點的情況，最多可以形成的群數是多少?
: 謝謝!
n=2k(n是偶數)
群數=1+n(n/2-1)+n/2=1+2k(k-1)+k=2k^2-k+1
n=2k+1(n是奇數)
群數=1+n[(n-1)/2]=1+(2k+1)k=2k^2+k+1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.37.84
推
10/26 02:03, , 1F
10/26 02:03, 1F