PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[問題] 組裝三角

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (水牛比爾)時間4年前 (2020/08/31 09:02), 4年前編輯推噓10(10推 0噓 18→)
留言28則, 3人參與, 4年前最新討論串1/2 (看更多)
puzzleUp風味題 Vol.5 【組裝三角】 給予50個線段，長度分別為1~50。 組成任意數量的直角三角形。 問這些直角三角形的最大總合面積為？ 線段不能裁接凹折 三角形之間不能共線 若題目給1~20的線段，則答案為162 (3,4,5)(8,15,17)(12,16,20) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1598835756.A.5D3.html
→
08/31 09:03, 4年前 , 1F
長度1跟2是不可能組成直角三角形的，無視就好:)
08/31 09:03, 1F
※ 編輯: buffalobill (60.251.148.94 臺灣), 08/31/2020 09:43:14
推
08/31 09:45, 4年前 , 2F
程式列出畢氏三元數，再用紙筆初步湊出 1932
08/31 09:45, 2F
→
08/31 09:47, 4年前 , 3F
如果不考慮畢氏三元數可能出現的潛在關係
08/31 09:47, 3F
→
08/31 09:47, 4年前 , 4F
programUp 起來是個 weighted independent set 問題
08/31 09:47, 4F
推
08/31 10:03, 4年前 , 5F
要處理的圖是這個 https://imgur.com/VyVurkQ.png
08/31 10:03, 5F
→
08/31 14:09, 4年前 , 6F
1932還差一點點哦
08/31 14:09, 6F
推
08/31 14:44, 4年前 , 7F
上面那張圖多算了 (20, 48, 52)，不過跑起來結果一樣
08/31 14:44, 7F
→
08/31 14:45, 4年前 , 8F
因為沒有用到那組
08/31 14:45, 8F
→
08/31 14:45, 4年前 , 9F
是有沒考慮到的組裝方式嗎(思
08/31 14:45, 9F
推
08/31 15:01, 4年前 , 10F
找到問題了，1944
08/31 15:01, 10F
→
08/31 15:05, 4年前 , 11F
1944正解
08/31 15:05, 11F
推
08/31 15:13, 4年前 , 12F
新的圖要手算感覺麻煩許多
08/31 15:13, 12F
推
08/31 15:13, 4年前 , 13F
我找到 1944, 還不確定是不是最大
08/31 15:13, 13F
→
08/31 15:13, 4年前 , 14F
hmmmm
08/31 15:13, 14F
推
08/31 15:35, 4年前 , 15F
啊, 找到 1932 了...還在想這種 local max 應該要出現的
08/31 15:35, 15F
→
08/31 15:36, 4年前 , 16F
我是整理出 (9,12,15) (12,16,20) (15,20,25) 最多取其一
08/31 15:36, 16F
→
08/31 15:36, 4年前 , 17F
從這裡去找, 1944 是選 (15,20,25) 得到的最大值
08/31 15:36, 17F
→
08/31 15:36, 4年前 , 18F
1932 則是都不選的 local max
08/31 15:36, 18F
→
08/31 15:40, 4年前 , 19F
主要是 (30,40,50) 的位置太尷尬, 取和不取的條件不夠多
08/31 15:40, 19F
→
08/31 15:41, 4年前 , 20F
又被 (14,48,50) (18,24,30) (24,32,40) 兩邊夾
08/31 15:41, 20F
→
08/31 15:42, 4年前 , 21F
從那邊出發的分支完全動不到上五樓提到的那一團
08/31 15:42, 21F
推
08/31 15:43, 4年前 , 22F
我是用 (m^2-n^2, 2mn, m^2+n^2) 找畢氏三元數
08/31 15:43, 22F
→
08/31 15:43, 4年前 , 23F
沒注意到這只保證可以找出互質的，所以才算出 1932 XD
08/31 15:43, 23F
→
08/31 15:44, 4年前 , 24F
那張圖裡列的是用這個公式可以找出的那些
08/31 15:44, 24F
推
08/31 15:46, 4年前 , 25F
哦, 你是找所有 (m, n) 而不是用基本三元數乘 k 倍...
08/31 15:46, 25F
→
08/31 15:46, 4年前 , 26F
對XD
08/31 15:46, 26F
→
08/31 15:47, 4年前 , 27F
所以就正好漏掉了包含 (15,20,25) 的幾個這樣嗎 XD
08/31 15:47, 27F
推
08/31 15:53, 4年前 , 28F
有包含 (12,16,20)，不過找最大值的時候不會取到
08/31 15:53, 28F
‣ 更多 buffalobill 的文章
文章代碼(AID): #1VJ4miNJ (puzzle)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 buffalobill 的文章
文章代碼(AID): #1VJ4miNJ (puzzle)