[理工] 108交大資演

看板Grad-ProbAsk作者 (knah1321)時間6年前 (2019/02/18 18:29), 編輯推噓26(27推 1噓 22→)
留言50則, 21人參與, 6年前最新討論串1/1
想問一題minimal intermediate sum的 好像是第21題，題組題 題目大概是說，4+1+2+3可以插入3組括號變成((4+1)+(2+3))=((5)+(5))=10 然後5+5+10= 20 但也可以寫成(4+((1+2)+3)) 會跑出3,6,10,sum=19 19就比20小 然後問題是要找4,4,8,5,4,3,5的最小解 我算是 (((4+4)+8)+(5+((4+3)+5))) =(((8)+8)+(5+((7)+5))) =((16)+(5+(12))) =(16+(17)) =(33) 分別跑出8,7,16,12,17,33，相加起來是93 可是答案好像是給91 不知道自己盲點到底在哪裡... 有大大可以提供一下解出91的想法嗎 感恩 一題就整題組爆 好痛嗚嗚 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.92.113 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1550485751.A.557.html
→
02/18 18:35, 6年前 , 1F
用哈輔慢呢
02/18 18:35, 1F
推
02/18 18:36, 6年前 , 2F
4+4 8 5+4 3+5
02/18 18:36, 2F
→
02/18 18:37, 6年前 , 3F
我是想讓局部盡量小 且數大小平均一點
02/18 18:37, 3F
推
02/18 18:37, 6年前 , 4F
用huffman作法
02/18 18:37, 4F
推
02/18 18:50, 6年前 , 5F
那時候想好久是Huffman還是像matrix chain那樣還是想不出
02/18 18:50, 5F
→
02/18 18:50, 6年前 , 6F
來QQ
02/18 18:50, 6F
推
02/18 18:54, 6年前 , 7F
不能huffman吧 最小的兩個又不一定相鄰
02/18 18:54, 7F
推
02/18 18:57, 6年前 , 8F
要用dp
02/18 18:57, 8F
推
02/18 18:57, 6年前 , 9F
同2樓作法 這樣91沒錯 我忘了加最後一次...
02/18 18:57, 9F
推
02/18 18:59, 6年前 , 10F
第二行5跟5合阿 就是用ㄏ夫曼= =
02/18 18:59, 10F
推
02/18 19:05, 6年前 , 11F
我以為數字不能對調…
02/18 19:05, 11F
推
02/18 19:11, 6年前 , 12F
也想知道91怎麼出來的
02/18 19:11, 12F
推
02/18 19:12, 6年前 , 13F
8+9+8+16+17+33
02/18 19:12, 13F
推
02/18 19:14, 6年前 , 14F
不是插括號 可以任選兩個加
02/18 19:14, 14F
推
02/18 19:16, 6年前 , 15F
題目沒有說要相鄰吧
02/18 19:16, 15F
→
02/18 19:16, 6年前 , 16F
現場完全來不及做 在家算的方法跟2樓一樣
02/18 19:16, 16F
→
02/18 19:18, 6年前 , 17F
我覺得不能動吧
02/18 19:18, 17F
推
02/18 19:18, 6年前 , 18F
等等 我又看了一次題目 好像是插括號沒錯
02/18 19:18, 18F
→
02/18 19:20, 6年前 , 19F
只是剛好huffman答案一樣就是了
02/18 19:20, 19F
推
02/18 19:23, 6年前 , 20F
不能換位置吧
02/18 19:23, 20F
推
02/18 19:42, 6年前 , 21F
這題就是霍夫曼啦
02/18 19:42, 21F
推
02/18 19:43, 6年前 , 22F
不能換位子答案還會一樣嗎？
02/18 19:43, 22F
推
02/18 19:45, 6年前 , 23F
2樓應該是對的 我現場也是算93 QQQ
02/18 19:45, 23F
→
02/18 19:56, 6年前 , 24F
題目是4.4.8.5.4.3.5
02/18 19:56, 24F
→
02/18 19:57, 6年前 , 25F
(((4+4)+8)+ ((5+4)+(3+5)))
02/18 19:57, 25F
→
02/18 19:57, 6年前 , 26F
8+9+8+16+17+33=91
02/18 19:57, 26F
推
02/18 20:43, 6年前 , 27F
02/18 20:43, 27F
→
02/18 20:45, 6年前 , 28F
題目應該讓霍夫曼出來的答案不一樣..這樣就被某些人撿到
02/18 20:45, 28F
→
02/18 20:45, 6年前 , 29F
了==
02/18 20:45, 29F
推
02/18 21:46, 6年前 , 30F
真的==撿到一題 那個turnaround time*4也撿到
02/18 21:46, 30F
推
02/18 23:48, 6年前 , 31F
辣基= =
02/18 23:48, 31F
噓
02/18 23:52, 6年前 , 32F
不知道多少人用huffman賺分
02/18 23:52, 32F
推
02/19 00:50, 6年前 , 33F
這用赫夫曼的話第一步是3+4 不會對 例如我QQ
02/19 00:50, 33F
→
02/19 02:11, 6年前 , 34F
這運氣真的有點屌..錯錯得正
02/19 02:11, 34F
→
02/19 02:12, 6年前 , 35F
哦 原來是偷換了位子會對....
02/19 02:12, 35F
→
02/19 08:18, 6年前 , 36F
沒說不能換吧==
02/19 08:18, 36F
→
02/19 08:19, 6年前 , 37F
不過我沒換算91 第二次算81 直接失智
02/19 08:19, 37F
→
02/19 08:23, 6年前 , 38F
喔對 剛剛又看了一下 不能換 答案真根霍夫曼一樣==
02/19 08:23, 38F
推
02/19 08:44, 6年前 , 39F
霍夫慢到底怎麼選，我一開始用霍夫曼想沒辦法選點就用DP
02/19 08:44, 39F
→
02/19 08:44, 6年前 , 40F
了，但試了一下覺得太麻煩就跳過最後來不及用猜的><
02/19 08:44, 40F
推
02/19 11:28, 6年前 , 41F
Sky葛格錯誤的方法不要學>\\\\<
02/19 11:28, 41F
推
02/19 13:10, 6年前 , 42F
抱歉借串問，資演有一題算 array memory address 的，
02/19 13:10, 42F
→
02/19 13:10, 6年前 , 43F
大家都算的跟解答一樣？人在外沒帶考卷
02/19 13:10, 43F
→
02/19 13:33, 6年前 , 44F
樓上 一樣
02/19 13:33, 44F
→
02/19 14:14, 6年前 , 45F
一樣
02/19 14:14, 45F
推
02/19 16:14, 6年前 , 46F
用dp解
02/19 16:14, 46F
推
02/19 19:45, 6年前 , 47F
02/19 19:45, 47F
→
02/19 19:45, 6年前 , 48F
想詢問一下我想錯了哪邊 QQ
02/19 19:45, 48F
推
02/19 20:54, 6年前 , 49F
跟ekid大一樣寫E 不懂為啥錯QQ
02/19 20:54, 49F
→
02/19 21:06, 6年前 , 50F
題目要16進位 68是10進位
02/19 21:06, 50F
‣ 更多 hank1321 的文章
文章代碼(AID): #1SQeZtLN (Grad-ProbAsk)