104中央 資演第12題

看板Grad-ProbAsk作者 (xine)時間7年前 (2017/01/24 14:19), 7年前編輯推噓3(3推 0噓 14→)
留言17則, 2人參與, 最新討論串1/1
http://i.imgur.com/Tmj7lxu.jpg
http://i.imgur.com/XVDJQye.jpg
麻煩各位了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.162.188 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485238792.A.44D.html
推
01/24 14:29, , 1F
標題搜尋 104 中央 資結
01/24 14:29, 1F
推
01/24 14:30, , 2F
先對這個程式碼有點感覺，他很像是在求OBST的過程，令k
01/24 14:30, 2F
→
01/24 14:30, , 3F
為root，然後找出最小的search cost
01/24 14:30, 3F
→
01/24 14:31, , 4F
仔細看一下發現遞迴停止條件是i==j，也就是j-i=0
01/24 14:31, 4F
→
01/24 14:32, , 5F
q=g(p,i,k)+g(p,k+1,j)+p[i-1,k,j]，每次遞迴下去的時
01/24 14:32, 5F
→
01/24 14:32, , 6F
候j-i的值都會變小，然後k會從i跳到j-1
01/24 14:32, 6F
→
01/24 14:33, , 7F
列出這個式子：T(j-i)=[T(0)+T(j-i-1)]+[T(1)+T(j-i-2)
01/24 14:33, 7F
→
01/24 14:34, , 8F
]+...+[T(j-i-2)+T(1)]+[T(j-i-1)+T(0)]
01/24 14:34, 8F
→
01/24 14:34, , 9F
令x=j-i，可得：T(x)=T(0)+T(x-1)+T(1)+T(x-2)+...+
01/24 14:34, 9F
→
01/24 14:35, , 10F
T(x-2)+T(1)+T(x-1)+T(0)，化簡得到：
01/24 14:35, 10F
→ yupog2003: T(x)=2(0)+T(1)+...T(x-2)+T(x-1)] *[37m01/24 14:36
→
01/24 14:36, , 11F
T(x-1)=T(0)+T(1)+...+T(x-2)
01/24 14:36, 11F
→
01/24 14:36, , 12F
阿上面忘記乘2
01/24 14:36, 12F
→
01/24 14:37, , 13F
T(x)-T(x-1)=2*T(x-1) => T(x)=3*T(x-1)，T(x)=3^x
01/24 14:37, 13F
→
01/24 14:39, , 14F
一開始call這個程式是g(p,1,n)，所以x=j-i=n-1
01/24 14:39, 14F
→
01/24 14:41, , 15F
T(x)=3^x=T(n-1)=3^(n-1) => T(n)=3^n
01/24 14:41, 15F
3Q~ ※ 編輯: qwe85158 (27.247.162.188), 01/24/2017 15:17:46
推
01/24 15:19, , 16F
這個編輯是..
01/24 15:19, 16F
→
01/24 15:42, , 17F
我已經看不懂我在寫什麼了XD
01/24 15:42, 17F
‣ 更多 qwe85158 的文章
文章代碼(AID): #1OXl88HD (Grad-ProbAsk)