看板 [ Prob_Solve ]
討論串[問題] 繩子圍石頭
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 繩子圍石頭
推噓1(1推 0噓 2→)留言3則，0人參與, 7年前最新作者obelisk0114 (追風箏的孩子)時間7年前 (2017/11/18 19:36), 編輯資訊
1
0
0
內容預覽:
之前看到一題十分困難的題目,大致長這樣:. 平面上有許多點,要用一條固定長度的繩子圈住最多點. 繩子需要頭尾相連. 由於題目並未提到其他限制,所以任意形狀的圈法都可以. 目前只有想到用凸多邊形去圍. 但是實際做法沒有頭緒. 各位大大有何想法 ?. --. 肝不好 ▁▁ ● ◤ 肝若好. 人生是黑白的
(還有77個字)
#2
Re: [問題] 繩子圍石頭
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者cocoyan (摳摳厭)時間7年前 (2017/12/09 18:11), 編輯資訊
1
0
0
內容預覽:
先把所有點用一個凸多邊形包住. 凸多邊形的每一個角都至少代表一個點. 由於三角形的兩邊長必大於第三邊. 所以拿掉其中一個角後. 再用新的凸多邊形把剩下來的點包住. 新凸多邊形的周長會小於或等於原本的周長. 每次都拿掉周長能夠減少最多的那個點. 直到周長小於或等於繩子的長度. --. ※ 發信站: 批
#3
Re: [問題] 繩子圍石頭
推噓1(1推 0噓 0→)留言1則，0人參與, 7年前最新作者iago2007 (柔)時間7年前 (2017/12/10 15:43), 6年前編輯資訊
0
0
0
內容預覽:
反例:. 四個點分別為. A (-0.9,0). B (0,0). C (sqrt(3)/2,1/2). D (sqrt(3)/2,-1/2). 給定長度1.8的繩子，理論上要圍出AB兩點. 不過按照這個方法會找到BCD之後發現任兩點周長都是2而找不到兩點的圍法。. 本質在於圍兩點的最小圍法(AB)
(還有39個字)
首頁
上一頁
1
下一頁
尾頁