[請益] 智力測驗題目

看板logic作者 (鋒哥開砲囉......)時間15年前 (2009/03/10 00:51), 編輯推噓5(5推 0噓 6→)
留言11則, 5人參與, 最新討論串1/1
朋友的小孩(國中)拿一題智力測驗裡的考題來問我 沒錯....我被問倒了...... Q: 給定N個正整數, 請將此N個正整數分成 兩群, 讓這兩群的正整數總合相等, 如果 無解, 則回答"無此種分法", 舉例來說 2, 4, 6, 12 就是分成(2,4,6),(12) 2, 4, 6, 11 就是無此種分法, 請問這有什麼規則可循嗎 ? 譬如說題目是 : 27 3 12 76 100 59 93 16 64 6 38 21 98 43 100 39 58 10 39 71 44 72 93 44 77 34 10 49 69 47 這要怎麼分呢 ? THX. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.160.96.82
推
03/10 01:56, , 1F
這好像是個NP-complete的問題說...@@
03/10 01:56, 1F
推
03/10 02:41, , 2F
這是partition problem, 是NP-complete沒錯
03/10 02:41, 2F
→
03/10 02:43, , 3F
不過我想國中智力測驗這題肯定不是要求通解, 應該只是
03/10 02:43, 3F
→
03/10 02:47, , 4F
要學生根據給定的set (or multiset)找出一組解, 考考算
03/10 02:47, 4F
→
03/10 02:48, , 5F
術與簡單的思考吧... 假如題目真的如原po給的有那麼多個
03/10 02:48, 5F
→
03/10 02:48, , 6F
數字.. 看起來真是不太簡單...
03/10 02:48, 6F
→
03/10 22:27, , 7F
acm好像有類似題
03/10 22:27, 7F
推
03/15 03:10, , 8F
全部和是奇數一定無解
03/15 03:10, 8F
→
03/15 03:12, , 9F
所以有奇數個奇數一定無解
03/15 03:12, 9F
推
03/18 19:47, , 10F
一樣的可以先劃掉......吧？
03/18 19:47, 10F
推
03/20 17:41, , 11F
......不行
03/20 17:41, 11F
‣ 更多 lalawul 的文章
文章代碼(AID): #19jKaaVX (logic)