作者jacksoncsie (Nov)
看板Grad-ProbAsk
标题[理工] 108交大资演 23小题
时间Sat Dec 25 00:48:55 2021
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1640364537.A.7E0.html
※ 编辑: jacksoncsie (114.37.48.158 台湾), 12/25/2021 01:03:47
1F：推 FRAXIS: 你假设 list size 是 2 的次方数.. 12/25 12:46
2F：→ FRAXIS: 你的方法会考虑最佳解是先加第二元素和第三个吗? 12/25 12:48
3F：→ FRAXIS: 感觉你的方法不会认定第二个和第三个元素会相邻 12/25 12:49
4F：→ jacksoncsie: F大你好，之前也是看你有回复同样问题才想上来问的 12/25 13:17
5F：→ jacksoncsie: 第3项由於是最大值，且总数是基数所以我打算先 12/25 13:19
6F：→ jacksoncsie: 不加此项，有点像merge sort判断说如是基数项，则直 12/25 13:20
7F：→ jacksoncsie: 接mapping到下阶段的阵列 12/25 13:20
8F：→ jacksoncsie: 而关於演算法实作的部分，我是有2个准则 12/25 13:21
10F：→ jacksoncsie: 我的树大概画成这样 12/25 13:27
12F：→ jacksoncsie: root 是 33 写错 12/25 13:28
13F：→ mathtsai: 这题一脸dp（？） 12/26 11:55
14F：推 FRAXIS: 这题如果是用 DP, 你可以很容易说明为什麽所有可能 12/27 11:51
15F：→ FRAXIS: 都会被考虑到 最基本的形式会是 O(n^3) 时间复杂度 12/27 11:51
16F：→ FRAXIS: 如果要加速 你必须要说明你节省的地方是不可能会有最佳解 12/27 11:52
17F：→ jacksoncsie: 了解 之前看讨论也是说用DP 不过我这感觉像Greedy 12/27 22:21
18F：→ jacksoncsie: 霍夫曼树的变形 :( 12/27 22:21