[理工] 108交大資演 23小題

看板Grad-ProbAsk作者jacksoncsie (Nov)時間4年前 (2021/12/25 00:48)推噓2(2推 0噓 16→)

留言18則, 3人參與討論串1/1

https://i.imgur.com/3qPTUj3.jpg

https://i.imgur.com/EzJ47yM.jpg

問這題，前情提要答案是 D 而原題答案 X = 91 (4 + 4) + 8 + (5 + 4) + (3 + 5) = (8 + 8) + (9 + 8) = (16 + 17) → 8 + 9 + 8 + 16 + 17 +33 = 91 我是想問演算法實作的部分，看之前上討論只說可以用 matrix chain 類似方式去求解，而 matrix chain 最快可在 O(n lg n )下實作該篇算法 http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf 以下是我的想法 : Find_Small_Intermediate_Sum(int *list, int list_size) Sequential search list, determine the total size is odd or even if(list_size % 2 == 0){ Divide the list into group, which group size is 2 Calculate the sum for the each group, put it into the list Find_Small_Intermediate(list, list_size / 2) }else{ list \ the biggest one // Don't calculate the biggest one Divide the list into group, which group size is 2 Calculate the sum for the each group, put it into the list Find_Small_Intermediate(list, list_size / 2) } # 演算法步驟 1. Split the list // O(log n) 2. 判斷總數為何若為基數先去除最大項, 偶數不變 // O(n) 3. 接下來依剩下儲存值與相臨數值相加之後 merge // O(n) 有問題歡迎指證感恩 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.48.158 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1640364537.A.7E0.html ※ 編輯: jacksoncsie (114.37.48.158 臺灣), 12/25/2021 01:03:47

推

FRAXIS

12/25 12:46, 4年前 , 1^F

12/25 12:46, 1^F

→

FRAXIS

12/25 12:48, 4年前 , 2^F

12/25 12:48, 2^F

→

FRAXIS

12/25 12:49, 4年前 , 3^F

12/25 12:49, 3^F