組裝三角 - 拼圖

Ursula avatar
By Ursula
at 2020-09-01T09:28

Table of Contents

答案是1944
由下列直角三角形組成
(5,12,13)(6,8,10)(14,48,50)(15,20,25)(16,30,34)(21,28,35)(24,32,40)(27,36,45)

這題直觀上不難
從畢氏三元數出發
整理出邊長不超過50的直角三角形
共二十個

再將這二十個直角三角形的面積與共線關係
弄成一張圖： https://i.imgur.com/9TQFv9x.png
問題就變成就這張圖裡選出面積總合最大的節點們
且相鄰的節點不得同時被選
也就是 Weighted Independent Set

WIS 是 NP-Complete 問題
意即目前的演算法
尚不存在比暴力更有效率的作法
不過20個節點的變化也就1048576種
對計算機而言是小 Case
甚至直接動手去排也應該不到半天就能找出解了

--
Tags: 拼圖

All Comments

Pintoo 黃金會員

Eden avatar
By Eden
at 2020-08-31T22:27
打擾了~上次沒徵到再徵一次試試看~ 預計去Pintoo實體門市購買拼圖， 希望搭配振興券活動再省一些^^and#34; (活動到9月底) 若有願意借用黃金會員者再麻煩您站內我，謝謝! - ...

小雅畫廊裱框

Suhail Hany avatar
By Suhail Hany
at 2020-08-28T22:45
之前想裱框一直查不到太多價格的資訊，後來上網messenger問了一下施工時間，小雅是從 送去到完成1.5個禮拜，原本也有問拼圖總動員跟研心坊但都要4個禮拜所以後來就選小雅惹 ~ 想說分享一下裱框的價錢給大家參考 因為一次三幅所以老闆娘說有算便宜一點 https://i.imgur.com/yk7HdMX. ...

撲克分堆

Bethany avatar
By Bethany
at 2020-08-28T09:42
puzzleUp風味題 Vol.4 非程式題來了 【撲克分堆】 將52張撲克牌任意分成N堆 使每一堆牌皆組不出鐵支、同花、與順子 問N最小為？ 鐵支：四張同點數牌加上一張其它牌 同花：五張同花色的牌，點數任意 順子：五張點數連續的牌，花色不拘，含10JQKA - ...

皇后騎士

Erin avatar
By Erin
at 2020-08-27T11:52
puzzleUp 風味題 第三發 這題我還沒寫程式去算答案 大家加油 【皇后騎士】 在8x8的棋盤上放置Q個皇后與K個騎士 每個棋子都不在其它棋子可以吃的位置上 問 QxK 的最大可能為？ 若棋盤為4x4，則答案為 1x3 = 3 https://i.imgur.com/18LzqmG.png - ...

擲骰算分

Genevieve avatar
By Genevieve
at 2020-08-26T20:02
※ 引述《buffalobill (水牛比爾)》之銘言： : 想到就po : PuzzleUp風味題 : 先說這題我寫程式算的 : 紙筆的話我還不知道如何列式子…… : 【擲骰算分】 : 擲一枚公正骰子六次，並計算分數 : 分數的計算規則如下： : 第1次擲骰：擲出的點數即為起始分數 : 第2~6次擲骰：與上 ...