[理工] [DS]-成大97-資工所

[assassin88 (Ace)]

第一題：

(a) MULTIPLYALL(n) 要怎麼在o(n)內完成阿？有n個元素乘不就至少要n了嗎？
                   還是說有什麼技巧..
(b) ZEROALL() 也是一樣的問題..煩請解答了。

第二題：(竟然跟98一樣....但還是不很懂~囧)

(a)、(b)、(d)：可否解釋一下錯在哪裡呢..

第三題：題目是看得懂..可是實在不是很了解該怎麼下筆....

另外還有演算法部分的最後一題，請問SCC應該是多少？

問題有點多..麻煩了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.57.78.40
→ abcde1499:這張超難的...我也都不會... 第二題(a)(b)(d)都是F ??
→ assassin88:我是不確定..只知道C錯而已XD
推 bensome0624:二(a)-x,y有可能是sibling
→ bensome0624:二(b)-可能為loop   二(d)-我覺得是正確的
→ bensome0624:一(a)(b)-加一個參數每次輸出時需乘以它
→ assassin88:這樣有n個元素不是還是要到n？
推 bensome0624:輸出一個元素時只要乘一次就好了,故O(1)
→ bensome0624:而MUTIPLYALL()也只需修改那個參數就好了,還是O(1)
→ assassin88:怪怪的耶..輸出乘一個元素但有n個元素..還是我誤會Orz
推 bensome0624:因為它的read(K)式只讀出位置K的元素,故只有一個元素
→ bensome0624:需要乘以參數
→ assassin88:原來你的意思是要看READ(k)，但題目MUTIPLYALL(n)定義
→ assassin88:不是對所有元素乘n..
→ assassin88:還是因為後面那句..be performed with accumulative..
推 privatewind:這題我是用一個參數去乘   但是如果還要加入一個zero
→ privatewind:all() 而且這個zeroall還要跟其它函式互用, 就不知道
推 b76516:我想MUTIPLYALL()的意思應該是 全部的元素乘起來是多少
→ b76516:所以在每次寫入的時候 順便紀錄現在所有的元素乘積
→ b76516:然後把這個紀錄*n就可以O(1)完成