[理工] [離散] 95清大數學&資結 對答案

[Lautreamont (Maldoror is dead)]

1.(a) 存在x, 對所有y!=x, M(x,y)
  (b) 對所有y,存在x!=y, [~M(x,y)^T(x,y)] or [M(x,y)^~T(x,y)]
                                   (感謝assassin88指正)
2. 11
3.(a) upper bound: 21
      lower bound: 3
  (b) 3
4.(a) {a屬於R | 0 <= a < 1}
  (b) {a屬於R | -1 <= a < 2}
  (c) null
5.略
6.(a) C(100,20)
  (b) 略
7. 略
8. a(r) = a(r-1) + a(r-2)  , r >= 3
   a(1) = 2, a(2) = 3
9. 略
10. ???
11. (Rear-Front) mod n = n-1
12. O(n)
13.    34
      /  \
     24   5
    /
   17
14.  0    1   2    3    4    5  6  7
     | 14 | 8 | 23 | 18 | 33 |  |  |  |
15. O(|V|+|E|)
    不會，有請強者....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.180.232
推 assassin88:1(b) all y~exist x !=y{[-M(x,y)^T(x,y)]or[M(x,y)^T(
→ assassin88:x,y)]
→ assassin88:後面T前面少了-
推 gsrr:請問一下,有幾個非同構的圖,是怎麼算的?謝謝
→ Lautreamont:不是either or嗎?   我想應該是"或"的意思耶
→ Lautreamont:回g大 邊數0有1個 邊數1有1個 邊數2有2個 邊數3有3個
→ Lautreamont:邊數4有2個  邊數5有1個  邊數6有1個
推 assassin88:either or 不是 只發生一種嗎..?
→ Lautreamont:是的
※ 編輯: Lautreamont     來自: 118.160.180.232      (03/11 17:47)
→ Lautreamont:對了catalan number那題有神人會嗎?
推 gsrr:謝謝L大,不過5,6個點以上還有辦法求嗎?
→ Lautreamont:我是用暴力法  這種題目都是用暴力法吧??
推 ohstar:(11)是不是 n=(r-f) mod n 依題意f是指到首項之前一個位置
→ ohstar:寫錯 是numofelement = (r-f) mod n
→ Lautreamont:是 不過我覺得相減完是n-1
→ bensome0624:13.最後還有一次del max唷
※ 編輯: Lautreamont     來自: 118.160.180.232      (03/11 23:04)
→ Lautreamont:已更正 謝謝
→ bensome0624:15.應該是用97年的4.(8)題方法O(VlogV+E),本題weight
→ bensome0624:限制在1~5,改成priority queue做extract min O(5V)
→ bensome0624:整體O(5V+E)=O(V+E)
→ Lautreamont:用甚麼實作priority queue? 看這複雜度是F heap?