104中央 資演第12題

[qwe85158 (xine)]

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
推 AllenPaul: 標題搜尋 104 中央 資結
推 yupog2003: 先對這個程式碼有點感覺，他很像是在求OBST的過程，令k
→ yupog2003: 為root，然後找出最小的search cost
→ yupog2003: 仔細看一下發現遞迴停止條件是i==j，也就是j-i=0
→ yupog2003: q=g(p,i,k)+g(p,k+1,j)+p[i-1,k,j]，每次遞迴下去的時
→ yupog2003: 候j-i的值都會變小，然後k會從i跳到j-1
→ yupog2003: 列出這個式子：T(j-i)=[T(0)+T(j-i-1)]+[T(1)+T(j-i-2)
→ yupog2003: ]+...+[T(j-i-2)+T(1)]+[T(j-i-1)+T(0)]
→ yupog2003: 令x=j-i，可得：T(x)=T(0)+T(x-1)+T(1)+T(x-2)+...+
→ yupog2003: T(x-2)+T(1)+T(x-1)+T(0)，化簡得到：
→ yupog2003: T(x)=2(0)+T(1)+...T(x-2)+T(x-1)]                  *[37m01/24 14:36
→ yupog2003: T(x-1)=T(0)+T(1)+...+T(x-2)
→ yupog2003: 阿上面忘記乘2
→ yupog2003: T(x)-T(x-1)=2*T(x-1) => T(x)=3*T(x-1)，T(x)=3^x
→ yupog2003: 一開始call這個程式是g(p,1,n)，所以x=j-i=n-1
→ yupog2003: T(x)=3^x=T(n-1)=3^(n-1) => T(n)=3^n
3Q~
※ 編輯: qwe85158 (27.247.162.188), 01/24/2017 15:17:46
推 AllenPaul: 這個編輯是..
→ yupog2003: 我已經看不懂我在寫什麼了XD