Re: [理工] 複雜度, 組合
※ 引述《wsx02 ()》之銘言：
: 1. http://ppt.cc/ti44
: 2
: 請問為什麼這個複雜度是O(V +(V+E)) ?
: 2. http://ppt.cc/DDRV
: 答案是B, E
: 請問這個是怎麼算出來的?
: 謝謝
我來說一下第二題好了。
第一題就留給強者。
關於第二題的第一小題，
首先呢，因為N=10，所以我們要開始"找"答案，我們需要一個策略，
我們應該要從最大的開始找，也就是 a，這樣可以很容易縮小後面 b, c 的範圍 ，
但是其實題目配得很好，發現當 a 等於 5 的時候，Bino(a=5,3)=10 也就是說，
Bino(b,2)+Bino(c,1)=0 因為題目有說只要 m<n 的時候 Bino(m, n)=0 ，
所以我們可以輕易的看出 b<2 , c<1 又 b>c>=0 所以 b=1, c=0 得解 N=510 。
再來第二個小題，也是相同的方法，
代入 a=6 發現 Bino(6, 3)=20>N=18 所以 a=6 不合 所以 a=5 代入找 b ，
因為 a>b 所以我們把 b=4 代進去，結果 Bino(4,2)=6 也還沒超過，
再來 c=2 代入發現符合，所以 N=542 。
最後，其實題目數值設計得不錯，代入法很快就可以得解。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.184.12
推
08/07 21:47, , 1F
08/07 21:47, 1F